Ассимптотическая сходимость алгоритмов имитации отжига

1 Асимптотическая сходимость алгоритмов имитацииотжигаНесмотря на недетерминированный характер алгоритма имитации отжига, для неговозможно строгое обоснование сходимости в терминах теории вероятностей. Для этогоиспользуется теория цепей Маркова.Последовательность дискретных случайных величин {} называется цепьюМаркова, если(|)(|)Иначе говоря, цепь Маркова – это последовательность случайных величин, в которойзначение каждой случайной величины зависит только от значения предыдущей.Если указанная выше вероятность не зависит от номера шага n, то цепь Марковаявляется однородной.Множество всех значений случайных величин { }также называют состояниями.Цепь Маркова описывает систему со счетным числом состояний, переходы междукоторыми осуществляются случайным образом с известными вероятностями.

Так какмножество состояний счетно (по определению дискретной случайной величины), цепьМаркова можно представить конечной либо бесконечной матрицей, где элемент напересечении i-й строки и j-го столбца есть вероятность перейти из состояния i в состояниеj.Схему работы алгоритма имитации отжига можно рассматривать как цепь Маркова,где состояния – это все возможные расписания. По построению алгоритма вероятностьвыполнить ту или иную операцию зависит только от текущего расписания.Построенная цепь Маркова обладает двумя свойствами: неразложимостью иацикличностью.(Неразложимость означает, что), то есть из любогосостояния можно перейти в любое за конечное число шагов с ненулевой вероятностьюАцикличность означает, что(|()).

Для неразложимойцепи достаточно, чтобы это условия выполнялось хотя бы на одном решении.У цепи Маркова {(|} существует стационарное распределение, если предел { }) не зависит от j.Пусть цепь Маркова неразложима и апериодична. Тогда у нее существуетединственное стационарное распределение, определяемое формулами:∑Следствием данной теоремы является то, что вектор стационарного распределенияможно определить из системы уравнений детального баланса:Для стандартного алгоритма имитации отжига, представленного цепью Маркова,вероятность перехода из состояния A в состояние B есть произведение вероятностигенерации решения B, если текущее решение – А, и вероятности принять B в качественового приближения.( )( )Если температура не меняется, то эти вероятности всегда одинаковые, то есть цепьМаркова однородна.

Если вероятность генерации любого из решений в окрестноститекущего одинакова, а вероятность принятия нового решения определяется стандартнымиформулами, то вероятности перехода в цепи Маркова при заданной температуреопределяются следующей формулой.( )()(( ))Здесь N – размер окрестности решения, f(i) – значение целевой функции на решении i.При фиксированном значении температуры стационарной распределение длязаданной таким образом цепи Маркова будет иметь следующий вид, определяемый изуравнений детального баланса.()(( )∑()())Устремляя температуру к нулю и переходя к пределу, получим, что вероятность послебесконечного числа шагов получить неоптимальное решение равна 0, а вероятностиполучения каждого из оптимальных решений одинаковы.

Следовательно, имеет местоследующая теорема.Теорема. При стремлении температуры к нулю стационарное распределениеприближается к распределению, допускающему только оптимальные решения.На практике данное утверждение не согласуется с реальным применением алгоритмаимитации отжига: теорема содержит два предельных перехода, что означает, что нужнопри каждом значении температуры делать бесконечное число итераций, и затемпереходить к пределу по значениям температуры. В реальности число итераций сфиксированным значением температуры сильно ограничено, поэтому требуется болееточная модель.Пусть значение температуры на n-й итерации алгоритма равно tn, а матрица переходовцепи Маркова непостоянна и зависит от текущего значения температуры. Такая цепьназывается неоднородной.

Для рассматриваемого в данной работе алгоритма имитацииотжига, значения элементов матрицы переходов имеют следующий вид.( )(Пусть(∏))( ( )(()| (())( ))), то есть матрица U определяется как( ).Неоднородная цепь Маркова называется слабо эргодической, если(()()). Неформально это означает, чтоX(k) перестает зависеть от X(m) с ростом k, независимо от номера итерации m.Неоднородная цепь Маркова называется сильно эргодической, если(()).

Неформально это означает сходимость по распределению квектору q*.Для однородных цепей Маркова слабая и сильная эргодичность тождественны, но длянеоднородных в общем случае это не так.Дальнейшие рассуждения опираются на следующие две теоремы.Теорема. Цепь Маркова слабо эргодична, если следующий ряд расходится длянекоторых значений {∑| |(}: ∑(( ( ) )), где коэффициент эргодичности:( )).Теорема.

Цепь Маркова сильно эргодична, если 1) Она слабо эргодична, 2) Накаждой итерации у матрицы ( ) есть собственное значение, равное 1 и собственныйвектор q(k), 3) Для этих собственных векторов сходится числовой ряд ∑(‖ ( ))‖Сформулируем основную теорему об асимптотической сходимости алгоритмаимитации отжига.Теорема. Пусть значения температуры таковы, что(.)Тогда цепь Маркова, соответствующая алгоритму имитации отжига, сходится кстационарному распределению вида( ) , где| |– множество оптимальныхрешений.Доказательство. Сначала докажем сильную эргодичность цепи Маркова.

Какнесложно видеть, условие (2) из теоремы означает существование собственного вектора q,удовлетворяющего уравнению ( ), или построчно,∑, чторавносильно уравнениям детального баланса. Проверим, что значения()(∑(( )(( ))() ))удовлетворяют этим уравнениям.Обозначим(()( )). Заметим, что для этой функции верно тождество.Запишем уравнение детального баланса для q и проверим, что они выполняются.∑(∑ ()∑()∑ (∑()∑ ()))∑(∑ ())Получили тождество.Проверим выполнение условия (3).∑‖ ( )()‖∑ ∑ ||∑∑|∑(∑|∑ (( ))( )( )( ))∑(Очевидно, выражение ∑ (∑ ∑| ( )( )( )()|∑ (((|) |))∑(()( ))∑(( )(( ))))||( )) строго больше 0, так как в нем по крайнеймере есть ненулевое слагаемое, соответствующее i=j, поэтому вся сумма ряда конечна.Для проверки условия (1) воспользуемся достаточным условием слабой эргодичности.Нужно доказать, что ряд ∑( )( ( ) )) расходится.

Оценим P(k) снизу.(()( ( ) ))∑(Учитывая, что(((()( )))∑, получаем ряд вида)∑, который расходится.Осталось определить предел вектора q при стремлении температуры к нулю. Дляэтого рассмотрим предел(∑((()( )( )())))Если решение i – оптимальное, то знаменатель дроби всегда будет равен 1. Числительбудет равен 1, если j – тоже оптимальное решение, то есть f(i)=f(j), если же f(i)<f(j), то()( ). Получается, что слагаемое в сумме стремится к 1, если оно соответствуетоптимальному решению, и к 0 в противном случае.

То есть весь предел равен | |, исоответственно.| |Если решение i – не оптимальное, то в знаменателе одной из дробей f(j)-f(i)>0, то есть()( )последовательность, а соответствующееОбъединяя все значения qi, получаем| |.( ), что и требовалось доказать.Что касается скорости сходимости, приведем основные результаты без доказательств.Пусть a(k) – распределение вероятностей оказаться в том или ином состоянии на шагеk. Сравнив это распределение со стационарным q(c) по норме, получим следующуюоценку:‖ ( )Здесь‖ ( )( )‖(| ( )| )- второе по модулю собственное значение матрицы P(c) кратности( )‖.если((| |(()) ))| |Из данной оценки на k следует, что чтобы достичь заданной наперед точности, нужносовершить число итераций, пропорциональное квадрату от размера пространства поиска,то есть для достижения абсолютной точности алгоритм имитации отжига подходит хуже,чем полный перебор..