Для чего нужен этот шаг в алгоритме имитации отжига?

И Википедия, и этот сайт описывает аналогичный шаг в алгоритме имитации отжига, который я выбрал здесь:

Википедия:

  if P(e, enew, temp(k/kmax)) > random() then   // Should we move to it?
    s ← snew; e ← enew                          // Yes, change state.

Юваль Барор о головоломке с восемью королевами:

If moving the queen to the new column will reduce the number of attacked 
queens on the board, the move is taken. Otherwise, the move is taken only 
with a certain probability, which decreases over time. 
Hence early on the algorithm will tend to take moves even if they 
don't improve the situation. Later on, the algorithm will only make moves 
which improve the situation on the board.

Мой вопрос: чего достигает этот случайный ход?


language-agnostic simulated-annealing
person PizzAzzra    schedule 09.06.2010    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Цель состоит в том, чтобы не останавливаться на локализованном лучшем решении, а вместо этого попытаться найти глобальное лучшее решение См. здесь: http://en.wikipedia.org/wiki/Local_minimum

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

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

person Paolo    schedule 09.06.2010
comment
Ах, вот что они имеют в виду! В противном случае это как, эм, выиграть битву, но проиграть войну, верно? - person PizzAzzra; 09.06.2010
comment
@Az - в этом суть :) - person Paolo; 09.06.2010

arrow_upward
0
arrow_downward

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

person Will    schedule 09.06.2010