Начальная температура в алгоритме имитации отжига

14

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

Есть ли способ расчета хорошей начальной температуры?

Неопределенный
источник
2
Начальная температура имеет много общего с проблемной областью и другими параметрами, которые вы используете для алгоритма градиентного спуска. Можете ли вы дать больше контекста?
dhj

Ответы:

9

0.8Tmin t δ t E max t - E min t π min t 1МаксимумTминTδTЕМаксимумT-ЕминTTπmint1|N(mint)|t

N(i)i

πязнак равно|N(я)|ехр(-Ея/T)ΣJ|N(J)|ехр(-ЕJ/T)
, где обозначает множество соседей .N(я)я

Наконец, - это вероятность принятия положительного перехода . Теперь мы можем получить оценку вероятности принятия на основе "случайного" набора положительных переходов:т х х ( Т ) Sехр(-δT/T)Tχ^χ(T)S

χ^(T)=tSπminT1|N(минT)|ехр(-δT/T)ΣTSπминT1|N(минT)|знак равноΣTSехр(-ЕМаксимумT/T)ΣTSехр(-ЕминT/T),

Мы хотим найти температуру такую, что , где - это вероятность принятия, которую мы желаем. χ ( T 0 ) = χ 0 χ 0] 0 , 1 [T0χ(T0)знак равноχ0χ0]0,1[

T0 вычисляется итерационным методом. Некоторые состояния и сосед для каждого состояния генерируется. Это дает нам множество переходов . Энергии и соответствующие состояниям подмножества , сохраняются. Затем выбирается значение для , которое может быть любым положительным значением. затем определяется с помощью рекурсивной формулыE max t E min t S T 1 T 0SЕМаксимумTЕминTST1T0

TN+1знак равноTNпер(χ^(TN))пер(χ0)1/п
, где - действительное число .п1

Когда приближается к мы можем остановиться. теперь является хорошим приближением к искомой начальной температуре . Более подробные объяснения, доказательства и обсуждение см. В первом разделе оригинальной статьи [1].χ^(TN)χ0TNT0


[1] Бен-Амер, Валид. «Расчет начальной температуры моделируемого отжига». Оптимизация вычислений и приложения 29, нет. 3 (2004): 369-385.

Юхо
источник
3

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

однако есть хотя бы одна статья, которая изучает только начальную температуру. [1] Суть в том, что если вы не выполняете очень продвинутую работу, то рассмотрение начальной температуры как параметра проблемы и повторение различных начальных температур как части общей оптимизации [после обнаружения, что она действительно влияет на результаты] является очень разумным и вероятно, широко распространенная практика.

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

[1] Вычисление начальной температуры имитации отжига Бен-Амера 2004

[2] Эффективный график имитации отжига: производная Lam & Delosme

[3] Контроль температуры для имитации отжига Munakata & Nakamura

ВЗН
источник