Метод отжига (стр. 1 из 3)

Содержание

1. Введение……………………………………………………………………3

2. Постановка задачи…………………………………………………………4

3. Алгоритм имитации отжига………………………….……………………5

4. Общие схемы метода отжига……………………………………………...7

5. Анализ результатов……………………………………………………….12

6. Литература………………………………………………..……………….17

7. Приложение……………………………………………………………….18

Введение

Метод отжига – это техника оптимизации, использующая упорядоченный случайный поиск на основе аналогии с процессом образования веществом кристаллической структуры с минимальной энергией при охлаждении. В настоящее время метод отжига применяется для решения многих оптимизационных задач – финансовых, компьютерной графики, комбинаторных, в телекоммуникационных сетях, и многих других. Зачастую метод отжига используют для обучения нейронных сетей. Несмотря на такую широкую область применения, скорость сходимости метода отжига все еще мало изучена. История метода отжига начинается с 1953 года. В этом году Н. Метрополисом был разработан алгоритм симуляции установления равновесия в системе с множеством степеней свободы при заданной температуре. В начале 80-х у С. Киркпатрика впервые появилась идея использовать этот алгоритм не только для моделирования физических систем, но и для решения некоторых задач оптимизации. Огромным преимуществом метода отжига является свойство избежать “ловушки” в локальных минимумах оптимизируемой функции, и продолжить поиск глобального минимума. Это достигается за счет принятия не только изменений параметров, приводящих к уменьшению значения функции, но и некоторых изменений, увеличивающих ее значение, в зависимости от т.н. температуры характеристики моделируемого процесса. Чем выше температура, тем больше “ухудшающие” изменения допустимы, и больше их вероятность. Еще одним преимуществом является то, что даже в условиях нехватки вычислительных ресурсов для нахождения глобального минимума, метод отжига, как правило, выдает весьма неплохое решение. Л. Ингбером показано, что метод отжига и его модификации являются одним из наиболее эффективных методов случайного поиска оптимального решения для большого класса задач. К настоящему времени разработано множество различных вариантов метода отжига, как общих так и их специализаций для конкретных задач.

Постановка задачи

Задача данной курсовой работы:

1. Применить алгоритм имитационной нормализации к решению оптимизационных задач. Применение рассматривается на примере решения задачи компоновки рюкзака: пусть имеется n предметов, каждый из которых имеет ценность

и объем , . Имеется ранец (рюкзак), объем которого есть V , при этом , то есть все предметы в ранец положить невозможно. Необходимо положить в ранец набор предметов с максимальной суммарной ценностью.

2. Провести сравнительный анализ с другими подходами к решению оптимизационных задач.

Алгоритм имитации отжига

Алгоритм основывается на имитациифизического процесса, который происходит при кристаллизациивещества из жидкого состояния в твёрдое, в том числе при отжигеметаллов. Предполагается, что атомы уже выстроились в кристаллическую решётку, но ещё допустимы переходы отдельных атомов из одной ячейки в другую. Предполагается, что процесс протекает при постепенно понижающейся температуре. Переход атома из одной ячейки в другую происходит с некоторой вероятностью, причём вероятность уменьшается с понижением температуры. Устойчивая кристаллическая решётка соответствует минимумуэнергии атомов, поэтому атом либо переходит в состояние с меньшим уровнем энергии, либо остаётся на месте. (Этот алгоритм также называется алгоритмом Н. Метрополиса, по имени его автора).

При помощи моделирования такого процесса ищется такая точка или множество точек, на котором достигается минимум некоторой числовой функции

, где . Вводится последовательность точек пространства X. Алгоритм последовательно находит следующую точку по предыдущей, начиная с точки , которая является начальным приближением. Алгоритм останавливается по достижении точки .

Точка

по алгоритму получается на основе текущей точки следующим образом. К точке применяется оператор Α, который случайным образом модифицирует соответствующую точку, в результате чего получается новая точка . Точка становится точкой с вероятностью , которая вычисляется в соответствии с распределением Гиббса:

Здесь

> 0 - элементы произвольной убывающей, сходящейся к нулю положительной последовательности, которая задаёт аналог падающей температуры в кристалле. Скорость убывания и закон убывания могут быть заданы по желанию создателя алгоритма.

Алгоритм имитации отжига похож на градиентный спуск, но за счёт случайности выбора промежуточной точки должен будет попадать в локальные минимумы реже, чем градиентный спуск. Алгоритм имитации отжига не гарантирует нахождения минимума функции, однако при правильной политике генерации случайной точки в пространстве X, как правило, происходит улучшение начального приближения.

Общие схемы метода отжига

Больцмановский отжиг

Исторически первой схемой метода отжига является схема Больцмановского отжига. Именно эта схема использовалась Н. Метрополисом для вычисления многомерных интегралов пути в задачах статистической физики, а также с Киркпатриком для решения задачи нахождения оптимальной разводки микросхем. В Больцмановском отжиге изменения температуры задается формулой

Семейство распределений

выбирается как семейство нормальных распределений с математическим ожиданием и дисперсией, т.е. задается плотностью

где D - размерность пространства состояний. Пространство состояний предполагается метрическим. Для Больцмановской схемы доказано, что при достаточно больших

и общем количестве шагов k, выбор такого семейства распределений гарантирует нахождение глобального минимума.

Отжиг Коши (быстрый отжиг)

Основным недостатком Больцмановского отжига является очень медленное убывание температуры. Например, чтобы понизить исходную температуры в 40 раз, требуется

итераций, что уже вряд ли приемлемо при решении каких-либо задач. Ввиду этого Цу и Хартли предложили алгоритм, который позволяет использовать для изменения температуры схему (1) без потери гарантии нахождения глобального минимума. Это достигается за счет использования в качестве Qраспределений Коши с плотностью

соответствующим образом нормированных. Например, в случае D = 1 приходим к плотности

.

К сожалению, это распределение не очень удобно моделировать в пространстве размерности больше 1. Этого можно избежать, например, с помощью перемножения Dодномерных распределений Коши:

но в этом случае нахождении глобального минимума гарантируется только при законе изменения температуры не быстрее чем:

что гораздо медленнее схемы (1).

Сверхбыстрый отжиг

Недостатки двух предыдущих методов привели к тому, что в 1989 году американским исследователем Л. Ингбером был разработан метод сверхбыстрого отжига. В нем пространство Sсчитается состоящим из D-мерных векторов

где . Кроме этого, температура по каждой из координат может различаться, таким образом, Tтакже является вектором размерности D.