Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное автономное образовательное учреждение высшего профессионального образования

«Уральский федеральный университет

имени первого Президента России Б.Н. Ельцина»

Физико-технический факультет

Кафедра вычислительной техники

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

Отчет по дисциплине «Современные проблемы науки и производства в интеллектуально-информационных технологиях»

Руководитель Г.Б. Смирнов

Студент гр. ФтМ-150803 Асоев М.А

Екатеринбург - 2016

Содержание

Введение

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

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

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

Реализация отжига в рассматриваемой задаче

Заключение

Список использованных источников

Введение

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

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

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

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

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

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

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

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

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

Вероятностное распределение Q(x; T) выбирается как нормальное распределение (рис. 3) с математическим ожиданием м = t(x) и дисперсией у 2 = T,тоестьзадаетсяплотностью:

где D - размерность пространства состояний.

Рис. 1 -- Плотность нормального распределения

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

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

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

без потери гарантии нахождения глобального минимума. Это достигается за счет использования в качестве распределений Коши с плотностью

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

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

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

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

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

Реализация отжига в рассматриваемой задаче

Для простоты рассматривалось одномерное пространство состояний, в котором в качестве формулы расстояния между автоматами |x l x| использовалось количество различных переходов в двумерном масссиве transitions. Нормальное распределение моделировалось с помощью центральной предельной теоремы [3]. Распределение Коши моделировалось как частное двух нормальных распределений [5]. Для моделирования убывания температуры использовались непосредственно формулы для отжига Коши или Больцмановского отжига. Для вычисления вероятности принятия нового состояния использовалась формула, подробнее описанная в [6] h(ДE ; T )=e (ДE/T ) Из формулы видно, что если E l E > 0 (новая функция приспособленности больше старой), то функция вероятности принятия h > 1, следовательно, новый автомат обязательно заменит старый. Если же E l E < 0 (то есть старый автомат лучше), то новый автомат имеет шанс заменить старый с тем меньшей вероятностью, чем больше разность функций приспособленности.

Функция приспособленности

В качестве функции приспособленности использовалась следующая формула f(n, t) = n - t/200, где n -- количество яблок съеденных муравьем за 200 ходов, а t -- номер хода на котором муравей съел последнее яблоко.

Результаты

По итогам измерений отжиг Коши показал лучший результат, достигнув максимального результата в 89 яблок. Лучшим результатом Больцмановского отжига было 88 съеденных яблок, то есть Больцмановский отжиг не нашел решения поставленной задачи.

Результаты измерений функции приспособленности

Ниже представлен усредненный по ста запускам график зависимости числа съеденных яблок от числа поколений метода имитации отжига (рис. 2). В каждом запуске число итераций равняется полумиллиону

Рис.2 -- Усредненный график функции приспособляемости, 100 запусков, 500 000 итераций

Из графика видно, что в среднем Отжиг Коши дает результаты лучше, чем Больцмановский отжиг. На последующих графиках (рис. 1 и рис. 2) показаны отдельные графики максимума, минимума и среднего значения функции приспособляемости для каждого из отжигов по отдельности

Рис. 3 -- Отжиг Коши, 100 запусков, 500 000 итераций

Рис. 4-- Больцмановский отжиг, 100 запусков, 500 000 итераций

Как видно из графиков, в данной задаче Отжиг Коши дает лучший средний и максимальный результаты. Но наихудший результат работы Отжига Коши хуже, чем наихудший результат работы Больцмановского отжига.

Заключение

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

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

Список использованных источников

1. Тяхти А. С., Чебатуркин А. А. Описание виртуальной лаборатории на языке C# // НИУ ИТМО, кафедра компьютерных технологий, 2010. http://is.ifmo.ru/genalg/labs_2010-2011/GlOpt_instruction.pdf

2. Поликарпова Н. И., Шалыто А. А. Автоматное программирование // СПб.: Питер, 2009. http://is.ifmo.ru/books/_book.pdf

3. Метод имитации отжига. Конспект лекций А. Лопатина. http://rain.ifmo.ru/~buzdalov/lab-2011/books/annealing.pdf

4. Luke Sean “Essentials of Metaheuristics” // Online Version 1.0, 2010. http://rain.ifmo.ru/~buzdalov/lab-2011/books/metaheuristics.pdf

5. Wolfram MathWorld, Cachy Distribution http://mathworld.wolfram.com/CauchyDistribution.html

Размещено на Allbest.ru