Применение метода модельного отжига( имитации отжига) для изучения зависимости длины минимального пути Е от количества точек N для случайн

  МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ

(ГОСУДАРСТВЕННЫЙ  ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

 

Факультет «Прикладная  математика и физика»

Кафедра 806

 

Курсовая   работа

по  дисциплине  численные  методы

 

Тема: Применение метода модельного отжига( имитации отжига) для изучения зависимости длины минимального пути Е от количества точек N для случайного распределения их на плоскости ( в трехмерном пространстве).

 

Вариант:11

Студент: Ерохин А. И.     Подпись:

Группа:  08-404

Руководитель работы: Абгарян К. К.

 

Оценка:

Дата:

Подпись преподавателя:

 

 

Москва, 2012.

Теоретические сведения.

Задача.

Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр — разъездной сбытовой посредник) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.

Существует несколько частных  случаев общей постановки задачи, в частности геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.

В данной работе используется один из методов Монте-Карло.

Ме́тод Мо́нте-Ка́рло (методы Монте-Карло, ММК) — общее название группы численных методов, основанных на получении большого числа реализаций стохастического (случайного) процесса, который формируется таким образом, чтобы его вероятностные характеристики совпадали с аналогичными величинами решаемой задачи.

В данной работе используется метод имитации отжига.

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

Огромным преимуществом  метода является возможность избежать «ловушки» в локальных минимумах  исследуемой функции, и продолжить поиск глобального минимума.

Алгоритм работы метода.

 

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

Далее на каждом k-ом шаге мы 

1. Сравниваем текущее значение энергии с наилучшим найденным. Если текущее значение лучше — меняем глобальное наилучшее
2. Случайным образом генерируем новое состояние. Распределение вероятности для него должно зависеть от текущего состояния и текущей температуры
3. вычисляем значение функции для сгенерированной точки
4. принимаем или не принимаем сгенерированное состояние в качестве текущего; вероятность этого решения должна зависеть от разности функций сгенерированного и текущего состояний и, конечно, от температуры (чем выше температура, тем больше вероятность принять состояние хуже текущего)
5. если новое состояние не принято, генерируем другое и повторяем действия с третьего пункта, если принято — переходим к следующей итерации, понизив температуру (но чаще переход к следующему шагу производят в любом случае, чтобы избежать долгого зацикливания)

 

Процесс останавливается  по достижении определённой температуры. Вещество остыло в точке с минимальной  энергией. 

 

 

 

 

 

 

 

Блок-схема.

 

 

 

 

 

 

 

 

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

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

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

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

Основным недостатком  Больцмонавского отжига является очень медленное убывание температуры. Например, для того, чтобы понизить исходную температуру в 40 раз, требуется ~итераций, что уже вряд ли приемлемо для решения каких-либо задач. Ввиду этого,  Цу и Хартли предложили алгоритм, который позволяет использовать для изменения температуры схему без потери гарантии нахождения глобального минимума. Это достигается за счет использования в качестве семейства распределений – распределения Коши.

3.Методы «тушения».

Далеко не всегда хватает  вычислительных ресурсов для поиска глобального минимума. Кроме того, зачастую, достаточно не глобально  оптимального решения задачи, а достаточно близкого к нему. Методы «тушения» (simulated quenching) не гарантирует нахождения глобального минимума, но, как правило, быстро находят близкое решение, а на практике зачастую и сам оптимум. Основная идея этих методов заключается в том, чтобы скомбинировать семейство распределений одного из методов с более быстрым законом убывания температуры. Например, можно рассматривать нормальные распределения из Больцмановского отжига, но при этом уменьшать температуру по закону . Как правило, в этом случае, c выбирается между 0.7 и 0.99. Такой метод очень быстро сходится и для конкретных задач может давать весьма неплохое решение, близкое к оптимальному, в условиях реального времени.

График для зависимости  расстояния от количества вершин (n=1 – 12) при координатах, принадлежащих квадрату 0-20:

При 1000 проходов:

При 5000 проходов:

При координатах, принадлежащих  квадрату 0-100:

При 100 проходов:

При 5000:

При координатах, принадлежащих 0-1000:

1000 проходов:

5000 проходов:

 

 

И, наконец, при количестве городов (2-50), координатах (0-1000) и 5000 проходов:

Для всех вычислений выбирались и .

 

 

 

 

 

 

 

 

 

 

 

 

Вывод:

Данный метод показал  себя