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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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 следует, что чтобы достичь заданной наперед точности, нужносовершить число итераций, пропорциональное квадрату от размера пространства поиска,то есть для достижения абсолютной точности алгоритм имитации отжига подходит хуже,чем полный перебор..

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов учебной работы