Алгоритм спуска с горы

Случайное апробирование решений очень неэффективно, потому что пренебрегает выгодами, которые можно получить от анализа уже найденных хороших решений. В нашем примере можно предположить, что расписание с низкой полной стоимостью похоже на другие расписания с низкой стоимостью. Но алгоритм случайной оптимизации беспорядочно прыгает с места на место и не пытается автоматически просмотреть похожие расписания, чтобы найти среди них хорошие. Альтернативный метод случайного поиска называется алгоритмом спуска с горы (hill climbing). Он начинает со случайного решения и ищет лучшие решения (с меньшим значением целевой функции) по соседству. Можно провести аналогию со спуском с горы (рис. 5.1), отсюда и название.

Представьте, что человечек на рисунке – это вы и оказались в этом месте по воле случая. Вы хотите добраться до самой низкой точки, чтобы найти воду. Для этого вы, наверное, осмотритесь и направитесь туда, где склон самый крутой. И будете двигаться в направлении наибольшей крутизны, пока не дойдете до точки, где местность становится ровной или начинается подъем.

Применим этот подход к решению задачи об отыскании наилучшего расписания путешествия для семейства Глассов. Начнем со случайно

Рис. 5.1. Поиск минимума стоимости на горе

выбранного расписания и просмотрим все расписания в его окрестности. В данном случае это означает просмотр таких расписаний, для которых один человек выбирает рейс, вылетающий чуть раньше или чуть позже. Для каждого из соседних расписаний вычисляется стоимость, и расписание с наименьшей стоимостью становится новым решением. Этот процесс повторяется и завершается, когда ни одно из соседних расписаний не дает улучшения стоимости.

Реализуется алгоритм следующей функцией, которую нужно добавить в файл optimization.py:

def hillclimb(domain,costf):

#       Выбрать случайное решение sol=[random.randint(domain[i][0],domain[i][1])

for i in range(len(domain))]

#       Главный цикл while 1:

#       Создать список соседних решений neighbors=[]

for j in range(len(domain)):

# Отходим на один шаг в каждом направлении if sol[]]>domain[]][0]:

neighbors.append(sol[0:]]+[sol[]]+1]+sol[]+1:]) if sol[]]<domain[]][1]: neighbors.append(sol[0:j]+[sol[]]-1]+sol[]+1:])

#       Ищем наилучшее из соседних решений current=costf(sol)

best=current

for j in range(len(neighbors)): cost=costf(neighbors[j]) if cost<best: best=cost sol=neighbors[j]

#       Если улучшения нет, мы достигли дна if best==current:

break

return sol

Для выбора начального решения эта функция генерирует случайный список чисел из заданного диапазона. Соседи текущего решения ищутся путем посещения каждого элемента списка и создания двух новых списков, в одном из которых этот элемент увеличен на единицу, а в другом уменьшен на единицу. Лучшее из соседних решений становится новым решением. Выполните эту функцию в интерактивном сеансе и сравните результаты с теми, что были найдены случайным поиском: >>> s=optimization.hillclimb(domain,optimization.schedulecost) >>> optimization.schedulecost(s)

3063

optimization.printschedule(s)

Seymour

BOS

12

34-15

02

$109 10

33-

12

03

$ 74

Franny

DAL

10

30-14

57

$290 10

51-

14

16

$256

Zooey

CAK

10

53-13

36

$189 10

32-

13

16

$139

Walt

MIA

11

28-14

40

$248 12

37-

15

05

$170

Buddy

ORD

12

44-14

17

$134 10

33-

13

11

$132

Les

OMA

11

08-13

07

$175 18

25-

20

34

$205

Работает эта функция быстро и, как правило, находит лучшее решение, чем при случайном поиске. Однако у алгоритма спуска с горы, есть один существенный недостаток. Взгляните на рис. 5.2.

Рис. 5.2. Застряли в точке локального минимума

Из рисунка видно, что, спускаясь по склону, мы необязательно отыщем наилучшее возможное решение. Найденное решение будет локальным минимумом, то есть лучшим из всех в ближайшей окрестности, но это не означает, что оно вообще лучшее. Решение, лучшее среди всех возможных, называется глобальным минимумом, и именно его хотят найти все алгоритмы оптимизации. Один из возможных подходов к решению проблемы называется спуском с горы со случайным перезапуском. В этом случае алгоритм спуска выполняется несколько раз со случайными начальными точками в надежде, что какое-нибудь из найденных решений будет близко к глобальному минимуму. В следующих двух разделах мы покажем другие способы избежать застревания в точке локального минимума.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100