|
96 фигурации е ^ ставит в соответствие оценку (в простейшем случае действительное число). АИО может быть сформулирован как некоторая последовательность смены цепей Маркова. Каждая цепь представляет собой последовательность конфигураций Н, а вероятность перехода к новой конфигурации (от I к ]) определяется следующим образом: Рк = Ьу0)рв, если /* у 0,1 {^ ЬЛ^Р'Г сс/ш issj М=1 (3.1) где ру вероятность получения конфигурации НУиз № в результате воздействия "теплового шума", Ьу вероятность принятия конфигурации; I управляемый параметр отжига (аналог уровня теплового шума), начальное значение которого задается априорно и изменяется в процессе работы алгоритма по определенному закону. Для каждой конфигурации 1П подпространство конфигураций ЕМ определяется как множество возможных Н), которые достижимы из 1в результате одного возмущения системы. В этом случае вероятность перехода к новой конфигурации вычисляется как: 1/ П , если ¡1] е О Р«= 1О, если Н & О (3.2). Величина Ьу, определяется следующим образом: ехр(-А/^ //), если АР^ > О, если АР 5=О 9 , (3.3) АР = Р(Н .) Р(Н .) где '■> > , приращение определяемой пользователем стоимостной функции. При этом предполагается, что вероятности возмущений симметричны, а также, что из данной конфигурации № любая другая 1Ц может быть достигнута посредством конечного числа возмущений. |
ности попадания в более глубокие минимумы. Этот процесс Кирпатрик назвал "имитацией отжига" (по аналогии с процессом отжига металла, в результате которого появляются его новые свойства). Рассмотрим организацию процедуры оптимизации на основе имитации отжига. Пусть задано конечное множество возможных конфигураций £>. Обозначим через Я/ возможную конфигурацию; Я число конфигураций; 1=1, ... , О . Пусть также задана стоимостная функция Р(Н), которая каждой конфигурации Я, е Яставит в соответствие оценку (в простейшем случае действительное число). АИО может быть сформулирован как некоторая последовательность смены цепей Маркова [120]. Каждая цепь представляет собой последовательность конфигураций Я, а вероятность перехода к новой конфигурации (от / кУ) определяется следующим образом: Рк Ь„(0Ру, если Ю,1 1 2 *,(О *. если / = / (4.5) /,у=1 где ру вероятность получения конфигурации Ну из Я,в результате воздействия "теплового шума", Ьу вероятность принятия конфигурации; / управляемый параметр отжига (аналог уровня теплового шума), начальное значение которого задается априорно и изменяется в процессе работы алгоритма по определенному закону. Для каждой конфигурации Я,подпространство конфигураций Я, определяется как множество возможных Ну, которые дос201 тижимы из / в результате одного возмущения системы. В этом случае вероятность перехода к новой конфигурации вычисляется как: Рч \j\D\, если Н} е.О О, если Н . £ D Величина Ьу, согласно [119], определяется следующим образом ехр(-Д/^ //), если Д ^ > о , 1, если < О V (4.6) где Д/^ = /7( # /) / г(///)приращение определяемой пользователем стоимо-] стной функции. При этом предполагается, что вероятности возмущений симметричны, а также, что из данной конфигурации //, любая другая может быть достигнута посредством конечного числа возмущений. В [120] было доказано, что для цепей Маркова с бесконечной длиной при постепенном уменьшении / от некоторого, априорно заданного значения, до нуля система достигает оптимальной конфигурации с вероятностью, равной 1. На практике невозможно реализовать цепи Маркова бесконечной длины [122] и поэтому используются приближенные алгоритмы АИО. Суть метода оптимизации по алгоритму АИО состоит в том, что процесс формирования конфигураций начинается при некотором начальном значении затем процедура уменьшения Гповторяется до тех пор, пока / не будет равно минимальному значению, при котором система достигает оптимального состояния [121]. На эту процедуру влияют следующие факторы 202 |