Алгоритм имитации отжига

навеян физическими аналогиями. Отжигом называется процесс нагрева образца с последующим медленным охлаждением. Поскольку сначала атомы заставляют попрыгать, а затем постепенно «отпускают вожжи», то они переходят в новую низко- энергетичную конфигурацию.

Алгоритмическая версия отжига начинается с выбора случайного решения задачи. В ней используется переменная, интерпретируемая как

температура, начальное значение которой очень велико, но постепенно уменьшается. На каждой итерации случайным образом выбирается один из параметров решения и изменяется в определенном направлении. В нашем случае Сеймур (Seymour) может лететь обратно не вторым, а третьим рейсом. Вычисляются и сравниваются стоимости до и после изменения.

Тут есть важная деталь: если новая стоимость ниже, то новое решение становится текущим, как и в алгоритме спуска с горы. Но, даже если новая стоимость выше, новое решение все равно может стать текущим с некоторой вероятностью. Так мы пытаемся избежать ситуации скатывания в локальный минимум, изображенной на рис. 5.2.

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

p _ ^((-высокая стоимость – низкая стоимость) / температура)

Поскольку температура (готовность принять худшее решение) вначале очень высока, то показатель степени близок к 0, поэтому вероятность равна почти 1. По мере уменьшения температуры разность между высокой стоимостью и низкой стоимостью становится более значимой, а чем больше разность, тем ниже вероятность, поэтому алгоритм из всех худших решений будет выбирать те, что лишь немногим хуже текущего.

Добавьте в файл optimization.py новую функцию annealingoptimize, реализующую описанный алгоритм:

def annealingoptimize(domain,costf,T=10000.0,cool=0.95,step=1): # Инициализировать переменные случайным образом vec=[float(random.randint(domain[i][0],domain[i][1])) for i in range(len(domain))]

while T>0.1:

#       Выбрать один из индексов i=random.randint(0,len(domain)-1)

#       Выбрать направление изменения dir=random.randint(-step,step)

#       Создать новый список, в котором одно значение изменено vecb=vec[:]

vecb[i]+=dir

if vecb[i]<domain[i][0]: vecb[i]=domain[i][0] elif vecb[i]>domain[i][1]: vecb[i]=domain[i][1]

#       Вычислить текущую и новую стоимость ea=costf(vec)

eb=costf(vecb)

p=pow(math.e,(-eb-ea)/T)

#       Новое решение лучше? Если нет, метнем кости if (eb<ea or random.random( )<p):

vec=vecb

#       Уменьшить температуру T=T*cool

return vec

Для выполнения отжига эта функция сначала генерирует случайное решение в виде вектора нужной длины, все элементы которого попадают в диапазон, определенный параметром domain. Параметры temperature и cool (скорость охлаждения) необязательны. На каждой итерации в качестве i случайно выбирается одна из переменных решения, а dir случайно выбирается между step и step. Вычисляется стоимость текущего решения и стоимость решения, получающегося изменением переменной i на величину step.

В строке, выделенной полужирным шрифтом, вычисляется вероятность, которая уменьшается с уменьшением T. Если величина, случайно выбранная между 0 и 1, оказывается меньше вычисленной вероятности или если новое решение лучше текущего, то новое решение становится текущим. Цикл продолжается, пока температура почти не достигнет нуля, причем каждый раз температура умножается на скорость охлаждения.

А теперь попробуйте выполнить оптимизацию методом имитации отжига:

>>> reload(optimization)

>>> s=optimization.annealingoptimize(domain,optimization.schedulecost) >>> optimization.schedulecost(s)

2278

>>> optimization.printschedule(s)

Seymour

Boston

12

34

15

02

$10Q

10

33

12

03

$ 74

Franny

Dallas

10

30

14

R7

57

$2Q0

10

51

14

16

$256

Zooey

Akron

10

53

13

36

$18Q

10

32

13

16

$13Q

Walt

Miami

11

28

14

40

$248

12

37

15

05

$170

Buddy

Chicago

12

44

14

17

$134

10

33

13

11

$132

Les

Omaha

11

08

13

07

$175

15

07

17

21

$12Q

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

Вы можете следить за любыми ответами на эту запись через 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