получения результата и саму возможность получения результата за
реальное время. Такими аспектами являются оптимальное расписание
отжига, т.е. режим понижения температуры, и свойства генератора,
определяющие оптимальность пробных шагов.
На сегодняшний день разработано множество модификаций алго-
ритма имитации отжига. Далее остановимся на одном из вариантов,
разработанном Г. Форбсом и Э. Джонсом специально для нужд проек-
тирования ОС, так называемом алгоритме адаптивной имитации от-
жига (АИО) [8–10].
Вслед за авторами будем использовать три основных понятия:
— плотность распределения
p
i
(
X
)
определяется таким образом,
что произведение
p
i
(
X
)
dV
X
равно вероятности нахождения базовой
точки после итерации
i
в объеме
dV
X
в районе точки
X
, соответствен-
но
Ω
p
i
(
X
)
dV
X
= 1
;
— генератор
g
(
Y, X,
Ψ)
определяется так, что
g
(
Y, X,
Ψ)
dV
Y
равно
вероятности генерации пробной точки в объеме
dV
Y
в районе точки
Y
при условии, что базовая точка имеет координату
X
, при этом
Ψ
обозначает совокупность свойств генератора;
— функция принятия шага
a
(
Y, X, β
)
, определяемая как вероят-
ность принятия перехода из точки
X
в точку
Y
, при данном значении
обратной температуры
β
=
1
T
имеет вид
a
(
Y, X, β
) =
⎧⎨
⎩
1
, f
(
Y
)
< f
(
X
)
,
e
−
β
[
f
(
Y
)
−
f
(
X
)]
, f
(
Y
)
> f
(
X
)
=
e
−
β
·
max[0
,
(
f
(
Y
)
−
f
(
X
))]
.
Используя приведенные понятия, один цикл алгоритма имитации
отжига можно смоделировать следующим образом:
p
i
+1
(
X
) =
p
i
(
X
) +
Ω
p
i
(
Y
)
a
(
X, Y, β
)
g
(
X, Y,
Ψ)
dV
Y
−
−
Ω
−
p
i
(
X
)
a
(
Y, X, β
)
g
(
Y, X,
Ψ)
dV
Y
,
где первый интеграл обозначает увеличение плотности распределе-
ния за счет вероятности прихода базовой точки в район точки
X
,
а второй интеграл обозначает уменьшение плотности распределения
вследствие вероятности ухода базовой точки из района точки
X
.
В силу природы алгоритма для любых фиксированных значе-
ний
β
и
Ψ
с ростом числа шагов
i
распределение
p
i
(
X
)
стремится
к некоторому фиксированному распределению, называемому равно-
весным распределением
π
(
X, β,
Ψ)
, и определяемому из условия
90 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012. № 1
