го, уподобив различные перестройки оптимизируемой системы пере-
стройкам системы частицохлаждаемого вещества, а оптимизируемую
функцию — энергии системы частиц этого вещества. При этом осно-
вой подхода была принята имитация ключевого свойства процесса
отжига, гарантирующего в пределе получение системы с минимально
возможной энергией и заключающегося в том, что в состоянии те-
плового равновесия (из которого система при отжиге практически не
выходит) допускается с некоторой вероятностью существование кон-
фигураций с энергией
E
, превышающей энергию некоторого текуще-
го рассматриваемого состояния (при этом вероятность существования
конфигурации с энергией
E
равна
∼
exp(
−
E/
(
k
B
T
))
, где
k
B
— посто-
янная Больцмана,
T
— температура). Другими словами, при оптими-
зации должны с некоторой вероятностью допускаться шаги, ухудша-
ющие целевую функцию, причем вероятность принятия таких шагов
постепенно уменьшается с уменьшением “температуры”. Для имита-
ции этого ключевого свойства С. Киркпатрик использовал так назы-
ваемый алгоритм Метрополиса [23], предложенный М. Розенблютом,
Н. Метрополисом и другими, для моделирования равновесных состо-
яний систем атомов при заданных температурах.
Алгоритм имитации отжига для оптимизации функции, таким
образом, сводится к следующим шагам.
1. “Нагрев” системы, т.е. присваивание температуре
Т
начального
высокого значения.
2. Выбор начальной базовой точки
X
b
= (
x
b
1
;
x
b
2
. . . x
bN
)
и вычи-
сление начального значения целевой функции
f
b
=
f
(
X
b
)
.
3. Выбор случайного шага
S
= (
s
1
;
s
2
. . . s
N
)
из распределения,
называемого генератором, и получение пробной точки
X
t
=
X
b
+
S
,
вычисление
f
t
=
f
(
X
t
)
.
4. Сравнение текущего значения целевой функции с начальным
значением:
— если
f
t
< f
b
, пробная точка принимается,
f
b
и
X
b
присваиваются
значения
f
t
и
X
t
соответственно;
— если
f
t
> f
b
, пробная точка принимается с вероятностью
exp
−
1
T
(
f
t
−
f
b
)
.
5. Обновление параметров: присваивание новых значений темпе-
ратуре
T
и параметрам генератора.
6. Проверка критерия остановки. Если критерий не удовлетворен,
возврат к шагу 3.
Легко видеть, что алгоритм имитации отжига в основе своей до-
статочно прост. Однако за пределами этой основы существуют два
важных и далеко не столь простых аспекта, определяющие скорость
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012. № 1 89
