УДК 004.023 НОВЫЙ РЕЖИМ ОХЛАЖДЕНИЯ В АЛГОРИТМЕ СИМУЛЯЦИИ ОТЖИГА П. М. <...> А. А. Дородницына Российской академии наук Поступила в редакцию 10.02.2016 г. Аннотация. <...> В работе предложен новый режим охлаждения для алгоритма симуляции отжига. <...> Его аналитическая форма получена при помощи эмпирической модели поведения симуляции отжига и условия постоянной термодинамической скорости. <...> Тесты на множестве задач глобальной оптимизации показывают, что новый режим по эффективности обычно превосходит наиболее распространённое геометрическое охлаждение. <...> A novel simulated annealing cooling schedule is proposed. <...> Its analytic form is derived from the empiric model of the simulated annealing dynamics and the constant thermodynamic speed condition. <...> ВВЕДЕНИЕ Симуляция отжига (СО) – алгоритм оптимизации, предложенный Киркпатриком [1] и независимо Черны [2], являющийся адаптацией алгоритма выборки Метрополиса [3]. <...> Сформулируем задачу оптимизации: найти решение ,x максимизирующее или минимизирующее целевую функцию (ЦФ) ( ). <...> Ex Допустим также, что имеется метод генерации случайных ходов, переводящих решение x в соседнее решение иногда принимает ходы, ухудшающие значение ЦФ, что позволяет ей выходить из локальных оптимумов. <...> В классическом алгоритме СО используется критерий Метрополиса: вероятность принятия хода, приводящего к изменению энергии (ЦФ) ( ) ( ) ∆− есть ( E= E x' E x P E T=∆ / ) min exp − ∆ E ,1 , T где T – параметр по аналогии с оригинальным процессом называемый температурой и имеющий ту же размерность, что и ЦФ. <...> Все ходы, приводящие к улучшению ( ∆E 0)≤ принимаются, но вероятность принятия ухудшающих ходов ( ∆> зависит от темE 0) x . <...> ' На каждом шаге рассмотрению подвергается новое соседнее решение. <...> Лишь ходы с E∆ порядка T имеют значительный шанс принятия, в то время как ходы с ET∆ скорее всего будут отвергнуты. <...> Изменяя параметр ,T можно контролировать свойства поиска: при очень высоких температурах принимаются почти все ходы (случайный поиск, жидкое состояние), в то время как при очень низких температурах <...>