Описание метода имитации отжига

'Я сейчас, только помогу им', - шепнула Эрно и вернулась к магам. Любимый поймёт и подождёт, а пока нужно поблагодарить тех, кто сделал невозможное возможным. И я таки поцелую Иствана, даже не один раз: заслужил. После перевяжу, наложу на обоих обезболивающее и с пристрастиям допрошу. Станут молчать или врать - Эрно всё расскажет.

Описание метода имитации отжига

Метод отжига служит для решения задачи глобальной оптимизации — поиска глобального минимума некоторой функции , заданной из некоторого пространства , дискретного или непрерывного. Элементы множества S представляют собой состояния воображаемой физической системы («энергетические уровни»), а значение функции в этих точках используется как энергия системы ).

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

Итак, конкретная схема метода отжига задается следующими параметрами:

1. выбором закона изменения температуры , где — номер шага;

2. выбором вероятностного распределения ;

3. выбором функции вероятности принятия .