Метод имитации отжига. Метод отжига задача оптимизации
Метод отжига
Содержание
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 -мерных векторов
mirznanii.com
Метод отжига
Содержание
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.
Семейство распределений сроится следующим образом. Вводится функция
В качестве y для получения плотности распределений используется , таким образом, новое значение вычисляется по формуле где - случайная величина с плотностью на
При этом выходящие за границы интервала значения параметра генерируются заново или приравниваются соответствующим границам. Такую случайную величину легко промоделировать:
(2)
где - независимые случайные величины, распределенные равномерно на
Доказано, что закон изменения температуры дает статистическую гарантию нахождения глобального минимума. Для вероятности принятия также используется отдельная шкала температуры, изменяющаяся по такому же закону. Как правило, при реализации этого метода управляется двумя параметрами:
Преимущество такого методы очевидны. Во-первых, экспоненциальное убывание температуры гораздо быстрее достижимого в предыдущих методах. Во-вторых, разделение размерностей может дать большой выигрыш, как и благодаря отдельным температурам, так и благодаря ускорению процесса, в случае, если не нужно менять все координаты одновременно.
Кроме того, в отличие от отжига Коши, сверхбыстрый отжиг, как было показано, допускает очень быстрое моделирование распределения независимо от размерности S.
Среди недостатков этого метода можно назвать то, что ввиду большого количества параметров иногда требуется несколько месяцев, чтобы хорошо настроить его для решения конкретной задачи.Алгоритм Ксин Яо
Алгоритм Ксин Яо был повторным применением идеи предыдущего алгоритма. В качестве выбирается
Утверждается, что при изменении температуры по закону
достигается статистическая гарантия нахождения глобального минимума.
Однако, как показано, увеличение скорости убывания температуры вовсе не означает ускорения в решении задачи. Более того, “размазанность” распределения приводит к тому, что метод генерирует огромное число “длинных” переходов, которые отвергаются в силу низкой вероятности их принятия.
Таким образом, несмотря на то. Что этот процесс итерировать до бесконечности, получая законы изменения температуры, ценность таких “улучшений” представляется сомнительной. Более того, легко видеть, что в пределе это приводит к тривиальному методу случайного поиска, которым является метод отжига при T = 0.
Это в небольшой степени применимо и к методу сверхбыстрого отжига, так что вопрос о скорости сходимости этих методов, а также о других методах, обеспечивающих не такое быстрое убывание температуры, но большую скорость сходимости, остается открытым. Вполне возможны задачи, на которых вторая итерация вышеописанного процесса может давать не плохие результаты.Метод “тушения”
Далеко не всегда хватает вычислительных ресурсов на поиск глобального минимума. Кроме того, зачастую достаточно достигнуть не глобального оптимального решения задачи, а достаточно близкого к нему. Методы “тушения” не гарантируют нахождения глобального минимума, но, как правило, быстро находят близкое решение, а на практике зачастую и сам оптимум.
Основная идея этих методов заключается в том, чтобы скомбинировать семейство распределений одного из предыдущих четырех методов с более быстрым законом убывания температуры.
Например, можно рассматривать нормальное распределение из Больцмановского отжига, но при этом уменьшать температуру по закону .
Как правило, в этом случае c выбирается между 0.7 и 0.99. Такой метод очень быстро сходится, и для конкретных задач может давать весьма неплохое решение, близкое к оптимальному, в условиях реального времени.
Зачастую они основаны либо на нормальном распределении, либо на распределении для сверхбыстрого отжига. Кроме того, встречаются специальные распределения, подобранные опытным путем для решения конкретных задач.
Анализ результатов
Программа была запущенна с разными исходными данными большое количество раз. Результаты эксперимента занесены в таблицу.
N – количество предметов; R – объём рюкзака.
| N | R | α | Стоимость | Вес предметов | МДП | МИО |
| 10 | 10 | 0,1 | 6 5 2 3 4 5 4 8 7 3 | 2 2 2 1 2 2 3 3 1 | 27/0,17с | 27/0,0156с |
| 20 | 10 | 0,1 | 6 5 2 3 4 5 4 8 7 3 6 5 2 3 4 5 4 8 7 3 | 2 2 2 1 2 2 3 3 1 2 2 2 1 2 2 3 3 1 | 29/0,18с | 29/0,0156с |
| 20 | 20 | 0,1 0,5 0,9 | 2 4 10 12 6 8 11 3 4 7 2 4 10 12 6 8 11 3 4 7 | 13 19 8 6 10 8 4 9 8 5 13 19 8 6 10 8 4 9 8 5 | 46/0,21с | 45/0,0156с 45/0,0572с 46/0,109с |
| 30 | 20 | 0,1 0,5 0,9 | 2 9 1 10 5 7 1 12 3 4 2 9 1 10 5 7 1 12 3 4 2 9 1 10 5 7 1 12 3 4 | 5 6 2 3 7 2 5 12 5 2 2 3 7 2 5 2 5 12 5 2 2 3 7 2 5 6 8 7 3 3 | 66/0,23с | 64,7/0,014с 65,3/0,0218с 66/0,115с |
| 40 | 10 | 0,1 | 6 5 2 3 4 5 4 8 7 3 6 5 2 3 4 5 4 8 7 3 6 5 2 3 4 5 4 8 7 3 6 5 2 3 4 5 4 8 7 3 | 2 2 2 1 2 2 3 3 1 2 2 2 1 2 2 3 3 1 2 2 2 1 2 2 3 3 1 2 2 2 1 2 2 3 3 1 | 30/0,23с | 30/0,0156 |
| 40 | 20 | 0,1 0,5 0,9 | 1 4 6 8 2 4 3 9 7 10 3 1 2 6 3 7 5 4 5 5 7 1 10 3 2 2 6 8 3 9 1 10 9 5 2 3 6 7 4 2 | 2 6 8 10 12 4 6 6 8 9 2 3 10 4 6 8 2 5 15 2 1 4 2 5 6 7 9 3 2 8 5 6 4 5 2 3 5 7 8 1 | 54/0,23с | 52/0,0156с 52/0,031с 52/0,468с |
| 50 | 10 | 0,1 0,5 | 3 4 3 5 4 4 2 6 3 1 6 7 5 6 4 3 3 5 6 2 2 7 7 8 5 6 3 2 5 4 6 6 5 4 6 4 5 3 2 4 7 3 2 1 2 3 8 5 6 5 | 2 3 4 1 2 5 4 4 3 1 2 2 2 1 3 2 4 3 3 1 4 2 3 5 4 1 1 2 3 4 2 1 2 2 1 3 2 1 4 3 5 3 4 4 2 2 2 3 3 1 | 49/0,21с | 48,8/0,0652с 49/0,35с |
| 50 | 20 | 0,1 | 1 4 6 8 2 4 3 9 7 10 3 1 2 6 3 7 5 4 5 5 7 1 10 3 2 2 6 8 3 9 1 10 9 5 2 3 6 7 4 2 1 4 6 8 2 4 3 9 7 10 | 2 6 8 10 12 4 6 6 8 9 2 3 10 4 6 8 2 5 15 2 1 4 2 5 6 7 9 3 2 8 5 6 4 5 2 3 5 7 8 1 1 8 7 5 3 2 5 4 6 5 | 57/0,24с | 57/0,125с |
| 5050 | 2030 | 0,1 0,5 0,90,1 | 4 5 4 4 6 3 7 6 5 6 8 7 7 8 6 5 7 3 4 5 6 6 5 4 7 6 6 5 7 4 5 5 6 3 4 5 8 7 6 5 5 6 7 6 5 4 4 5 3 4 | 5 10 2 5 7 12 9 5 2 2 7 1 1 8 2 13 1 1 8 5 6 9 3 1 7 4 8 10 2 9 1 3 1 5 5 5 3 12 5 6 3 2 2 10 11 5 4 7 10 9 | 79/0,2398/0,21 | 77,8/0,0249с 78/0,0769с 78,8/0,503с98/0,0156с |
| 5050 | 3020 | 0,10,1 0,5 0,9 | 9 8 7 6 7 5 10 7 5 11 9 3 4 3 3 8 6 12 5 12 11 6 5 3 5 8 10 6 3 3 5 5 15 4 6 7 8 10 9 10 11 7 5 4 5 2 7 8 10 8 | 8 10 8 7 2 5 4 5 7 11 10 9 10 8 7 6 4 15 5 5 3 3 6 10 8 5 3 5 6 11 12 5 12 6 8 3 3 4 3 9 11 5 7 10 5 7 6 7 8 9 | 84/0,21с59/0,21с | 84/0,0262с57/0,0512с 57,8/0,07с 58/0,61с |
| 50 | 30 | 0,1 | 9 8 7 6 7 5 10 7 5 11 9 3 4 3 3 8 6 12 5 12 11 6 5 3 5 8 10 6 3 3 5 5 15 4 6 7 8 10 9 10 11 7 5 4 5 2 7 8 10 8 | 9 10 8 15 11 20 9 7 7 10 22 9 9 8 10 21 9 8 8 7 8 20 16 17 14 8 5 7 20 10 11 7 17 15 2 5 9 5 10 6 9 10 13 9 10 10 7 8 10 20 | 55/0,20с | 55/0,0124с |
| 50 | 50 | 0,1 0,5 0,9 | 3 4 3 5 4 4 2 6 3 1 6 7 5 6 4 3 3 5 6 2 2 7 7 8 5 6 3 2 5 4 6 6 5 4 6 4 5 3 2 4 7 3 2 1 2 3 8 5 6 5 | 25 21 20 30 21 19 31 32 20 15 23 20 15 23 20 15 21 33 33 21 18 34 20 15 22 16 34 25 20 14 15 30 21 19 31 20 23 15 23 20 14 21 15 30 21 34 18 20 15 16 14 22 25 | 21/0,21с | 18,5/0,017с 19/0,0311с 19,8/0,565с |
| 50 | 50 | 0,1 | 3 4 3 5 4 4 2 6 3 1 6 7 5 6 4 3 3 5 6 2 2 7 7 8 5 6 3 2 5 4 6 6 5 4 6 4 5 3 2 4 7 3 2 1 2 3 8 5 6 5 | 25 3 20 15 5 23 30 35 6 2 2 29 31 7 31 8 25 3 2 2 30 33 24 20 19 10 15 35 7 1 2 33 34 25 20 21 25 22 2 33 31 15 10 11 10 5 3 30 31 5 | 66/0,20с | 66/0,0156с |
На основе данных, приведенных в таблицах, можно построить следующие графики.
Сравнение по среднему значению целевой функции
α = 0,9
Сравнение по среднему времени работы программы
Сравнение по среднему значению целевой функции
α = 0,5
Сравнение по среднему времени работы программы
Сравнительный анализ работы алгоритмов
Для решения задачи компоновки рюкзака на плоскости использовались два алгоритма: имитации отжига и метод динамического программирования.
В результате тестирования программы были получены данные, представленные в таблице. По этим данным легко увидеть, что при α = 0,9 алгоритм имитации отжига дает оптимальное решение задачи или достаточно близкого к нему, но время выполнения программы превышает время выполнения метода динамического программирования при большом количестве предметов; при α = 0,5 алгоритм имитации отжига имеет наиболее высокую скорость нахождения решения по сравнению с метод динамического программирования и дает решение, близкое к оптимальному.
www.coolreferat.com
Метод имитации отжига : Нейронные сети. Основные модели : Экономико-правовая библиотека
При обучении НС, как и в и в других задачах многомерной оптимизации, одна из проблем — останов алгоритма в точке локального, а не глобального минимума целевой функции. При использовании градиентного алгоритма с точным выбором длины шага останов в локальном минимуме неизбежен. Обратное распространение ошибки страдает меньше, т.к. длина шага выбирается "некорректно" (без одномерной оптимизации вдоль вектора градиента), и на любой итерации возможно увеличение функции ошибки.
Метод имитации отжига позволяет преодолеть локальные минимумы и искать глобальный минимум целевой функции. "Плата" за это преимущество — медленная работа алгоритма в случае большой размерности целевой функции. Метод применим и к нейронным сетям, и к любым другим задачам многомерной оптимизации.
В 50-х годах был исследован процесс отжига металла и построена его математическая модель. Если раскалить кусок металла, то его внутренняя энергия достигнет высокого значения. Кристаллическая решетка при этом будет наименее упорядочена, т.к. тепловые флуктуации атомов решетки будут велики. Это соответствует начальному состоянию "необученной" нейронной сети. Если затем быстро охладить металл, то атомы будут "пойманы" в энергетически невыгодных состояниях. Энергия
системы снизится, но не достигнет глобального минимума. Кристаллическая решетка будет иметь множество дефектов, т.е. отклонений в расположении атомов от оптимального значения, а металл будет иметь высокую твердость (закаливание). Если охлаждение проводить медленно (отжиг), то с плавным уменьшением температуры тепловые колебания узлов решетки около состояния минимума энергии будут плавно уменьшаться, и в результате охлаждения решетка будет иметь высокую упорядоченность, а энергия системы достигнет глобального минимума.
В применении к задаче оптимизации модель выглядит так.
1. Выбирается смысл параметра "температуры" системы. Размерность его может быть различной и связана с размерностью целевой функции данной задачи. Целевая функция в данной модели означает энергию системы.
2. Выбирается большое начальное значение "температуры".
3. Независимые переменные, от которых зависит функция энергии, испытывают "тепловые флуктуации", т.е. случайные изменения. Обычно вероятность флуктуации независимой переменной химеет гауссовское распределение:
4. Рассчитывается изменение энергии (т.е. целевой функции), полученное за счет флуктуаций независимых переменных. Если энергия уменьшилась, то изменения шага 3 принимаются. Если энергия увеличилась, то изменения переменных сохраняются с вероятностью, зависящей от того, насколько увеличилась энергия, и каково текущее значение температуры:
где Ѳ — значение температуры. Вероятность р убывает с ростом д£ и с уменьшением Q.
5. Шаги 3,4 повторяются до тех пор, пока не будет достигнуто "тепловое равновесие". На практике это означает, что температура должна меняться очень медленно.
6. Температура уменьшается на малое значение, и шаги 3,4 повторяются для нового значения температуры.
7. Шаги 3-6 повторяются до тех пор, пока не будет достигнута малая температура, принятая за ноль. В этом состоянии энергия системы примет глобальное минимальное значение, если процесс охлаждения проводился бесконечно медленно. На практике скорость охлаждения конечна, и значение глобального минимума бывает неточным.
В результате такого алгоритма устанавливается тепловое равновесие, при котором вероятность обнаружить систему в состоянии с энергией Е определяется распределением Больцмана:
Такая модель оптимизации была предложена С.Киркпатриком, С.Гелатта и М.Веччи в 1983 г. и получила название "имитации отжига". Он дает очень хорошие результаты для обучения нейронных сетей с количеством синапсов несколько сотен. Для большего размера сетей алгоритм работает слишком медленно. Имитация отжига применяется для NP-полных задач, например, задачи коммивояжера, не поддающихся точному алгоритмическому решению. Данный метод используется при автоматическом размещении компонент на печатных платах, при их автотрассировке и во многих других задачах.
Преимущество алгоритма — поиск глобального минимума и отсутствие ограничений на вид минимизируемой функции Е. Недостаток — требование бесконечно медленного охлаждения, на практике означающее медленную работу алгоритма. Для нейронных сетей больших размерностей метод
трудноприменим из-за низкого быстродействия. Множество шагов по параметрам сети осуществляется в случайных, ненужных направлениях.
www.vuzllib.su
Метод отжига
Содержание
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.
Семейство распределений сроится следующим образом. Вводится функция
В качестве y для получения плотности распределений используется , таким образом, новое значение вычисляется по формуле где - случайная величина с плотностью на
При этом выходящие за границы интервала значения параметра генерируются заново или приравниваются соответствующим границам. Такую случайную величину легко промоделировать:
(2)
где - независимые случайные величины, распределенные равномерно на
Доказано, что закон изменения температуры дает статистическую гарантию нахождения глобального минимума. Для вероятности принятия также используется отдельная шкала температуры, изменяющаяся по такому же закону. Как правило, при реализации этого метода управляется двумя параметрами:
Преимущество такого методы очевидны. Во-первых, экспоненциальное убывание температуры гораздо быстрее достижимого в предыдущих методах. Во-вторых, разделение размерностей может дать большой выигрыш, как и благодаря отдельным температурам, так и благодаря ускорению процесса, в случае, если не нужно менять все координаты одновременно.
Кроме того, в отличие от отжига Коши, сверхбыстрый отжиг, как было показано, допускает очень быстрое моделирование распределения независимо от размерности S.
Среди недостатков этого метода можно назвать то, что ввиду большого количества параметров иногда требуется несколько месяцев, чтобы хорошо настроить его для решения конкретной задачи.Алгоритм Ксин Яо
Алгоритм Ксин Яо был повторным применением идеи предыдущего алгоритма. В качестве выбирается
Утверждается, что при изменении температуры по закону
достигается статистическая гарантия нахождения глобального минимума.
Однако, как показано, увеличение скорости убывания температуры вовсе не означает ускорения в решении задачи. Более того, “размазанность” распределения приводит к тому, что метод генерирует огромное число “длинных” переходов, которые отвергаются в силу низкой вероятности их принятия.
Таким образом, несмотря на то. Что этот процесс итерировать до бесконечности, получая законы изменения температуры, ценность таких “улучшений” представляется сомнительной. Более того, легко видеть, что в пределе это приводит к тривиальному методу случайного поиска, которым является метод отжига при T = 0.
Это в небольшой степени применимо и к методу сверхбыстрого отжига, так что вопрос о скорости сходимости этих методов, а также о других методах, обеспечивающих не такое быстрое убывание температуры, но большую скорость сходимости, остается открытым. Вполне возможны задачи, на которых вторая итерация вышеописанного процесса может давать не плохие результаты.Метод “тушения”
Далеко не всегда хватает вычислительных ресурсов на поиск глобального минимума. Кроме того, зачастую достаточно достигнуть не глобального оптимального решения задачи, а достаточно близкого к нему. Методы “тушения” не гарантируют нахождения глобального минимума, но, как правило, быстро находят близкое решение, а на практике зачастую и сам оптимум.
Основная идея этих методов заключается в том, чтобы скомбинировать семейство распределений одного из предыдущих четырех методов с более быстрым законом убывания температуры.
Например, можно рассматривать нормальное распределение из Больцмановского отжига, но при этом уменьшать температуру по закону .
Как правило, в этом случае c выбирается между 0.7 и 0.99. Такой метод очень быстро сходится, и для конкретных задач может давать весьма неплохое решение, близкое к оптимальному, в условиях реального времени.
Зачастую они основаны либо на нормальном распределении, либо на распределении для сверхбыстрого отжига. Кроме того, встречаются специальные распределения, подобранные опытным путем для решения конкретных задач.
Анализ результатов
Программа была запущенна с разными исходными данными большое количество раз. Результаты эксперимента занесены в таблицу.
N – количество предметов; R – объём рюкзака.
| N | R | α | Стоимость | Вес предметов | МДП | МИО |
| 10 | 10 | 0,1 | 6 5 2 3 4 5 4 8 7 3 | 2 2 2 1 2 2 3 3 1 | 27/0,17с | 27/0,0156с |
| 20 | 10 | 0,1 | 6 5 2 3 4 5 4 8 7 3 6 5 2 3 4 5 4 8 7 3 | 2 2 2 1 2 2 3 3 1 2 2 2 1 2 2 3 3 1 | 29/0,18с | 29/0,0156с |
| 20 | 20 | 0,1 0,5 0,9 | 2 4 10 12 6 8 11 3 4 7 2 4 10 12 6 8 11 3 4 7 | 13 19 8 6 10 8 4 9 8 5 13 19 8 6 10 8 4 9 8 5 | 46/0,21с | 45/0,0156с 45/0,0572с 46/0,109с |
| 30 | 20 | 0,1 0,5 0,9 | 2 9 1 10 5 7 1 12 3 4 2 9 1 10 5 7 1 12 3 4 2 9 1 10 5 7 1 12 3 4 | 5 6 2 3 7 2 5 12 5 2 2 3 7 2 5 2 5 12 5 2 2 3 7 2 5 6 8 7 3 3 | 66/0,23с | 64,7/0,014с 65,3/0,0218с 66/0,115с |
| 40 | 10 | 0,1 | 6 5 2 3 4 5 4 8 7 3 6 5 2 3 4 5 4 8 7 3 6 5 2 3 4 5 4 8 7 3 6 5 2 3 4 5 4 8 7 3 | 2 2 2 1 2 2 3 3 1 2 2 2 1 2 2 3 3 1 2 2 2 1 2 2 3 3 1 2 2 2 1 2 2 3 3 1 | 30/0,23с | 30/0,0156 |
| 40 | 20 | 0,1 0,5 0,9 | 1 4 6 8 2 4 3 9 7 10 3 1 2 6 3 7 5 4 5 5 7 1 10 3 2 2 6 8 3 9 1 10 9 5 2 3 6 7 4 2 | 2 6 8 10 12 4 6 6 8 9 2 3 10 4 6 8 2 5 15 2 1 4 2 5 6 7 9 3 2 8 5 6 4 5 2 3 5 7 8 1 | 54/0,23с | 52/0,0156с 52/0,031с 52/0,468с |
| 50 | 10 | 0,1 0,5 | 3 4 3 5 4 4 2 6 3 1 6 7 5 6 4 3 3 5 6 2 2 7 7 8 5 6 3 2 5 4 6 6 5 4 6 4 5 3 2 4 7 3 2 1 2 3 8 5 6 5 | 2 3 4 1 2 5 4 4 3 1 2 2 2 1 3 2 4 3 3 1 4 2 3 5 4 1 1 2 3 4 2 1 2 2 1 3 2 1 4 3 5 3 4 4 2 2 2 3 3 1 | 49/0,21с | 48,8/0,0652с 49/0,35с |
| 50 | 20 | 0,1 | 1 4 6 8 2 4 3 9 7 10 3 1 2 6 3 7 5 4 5 5 7 1 10 3 2 2 6 8 3 9 1 10 9 5 2 3 6 7 4 2 1 4 6 8 2 4 3 9 7 10 | 2 6 8 10 12 4 6 6 8 9 2 3 10 4 6 8 2 5 15 2 1 4 2 5 6 7 9 3 2 8 5 6 4 5 2 3 5 7 8 1 1 8 7 5 3 2 5 4 6 5 | 57/0,24с | 57/0,125с |
| 5050 | 2030 | 0,1 0,5 0,90,1 | 4 5 4 4 6 3 7 6 5 6 8 7 7 8 6 5 7 3 4 5 6 6 5 4 7 6 6 5 7 4 5 5 6 3 4 5 8 7 6 5 5 6 7 6 5 4 4 5 3 4 | 5 10 2 5 7 12 9 5 2 2 7 1 1 8 2 13 1 1 8 5 6 9 3 1 7 4 8 10 2 9 1 3 1 5 5 5 3 12 5 6 3 2 2 10 11 5 4 7 10 9 | 79/0,2398/0,21 | 77,8/0,0249с 78/0,0769с 78,8/0,503с98/0,0156с |
| 5050 | 3020 | 0,10,1 0,5 0,9 | 9 8 7 6 7 5 10 7 5 11 9 3 4 3 3 8 6 12 5 12 11 6 5 3 5 8 10 6 3 3 5 5 15 4 6 7 8 10 9 10 11 7 5 4 5 2 7 8 10 8 | 8 10 8 7 2 5 4 5 7 11 10 9 10 8 7 6 4 15 5 5 3 3 6 10 8 5 3 5 6 11 12 5 12 6 8 3 3 4 3 9 11 5 7 10 5 7 6 7 8 9 | 84/0,21с59/0,21с | 84/0,0262с57/0,0512с 57,8/0,07с 58/0,61с |
| 50 | 30 | 0,1 | 9 8 7 6 7 5 10 7 5 11 9 3 4 3 3 8 6 12 5 12 11 6 5 3 5 8 10 6 3 3 5 5 15 4 6 7 8 10 9 10 11 7 5 4 5 2 7 8 10 8 | 9 10 8 15 11 20 9 7 7 10 22 9 9 8 10 21 9 8 8 7 8 20 16 17 14 8 5 7 20 10 11 7 17 15 2 5 9 5 10 6 9 10 13 9 10 10 7 8 10 20 | 55/0,20с | 55/0,0124с |
| 50 | 50 | 0,1 0,5 0,9 | 3 4 3 5 4 4 2 6 3 1 6 7 5 6 4 3 3 5 6 2 2 7 7 8 5 6 3 2 5 4 6 6 5 4 6 4 5 3 2 4 7 3 2 1 2 3 8 5 6 5 | 25 21 20 30 21 19 31 32 20 15 23 20 15 23 20 15 21 33 33 21 18 34 20 15 22 16 34 25 20 14 15 30 21 19 31 20 23 15 23 20 14 21 15 30 21 34 18 20 15 16 14 22 25 | 21/0,21с | 18,5/0,017с 19/0,0311с 19,8/0,565с |
| 50 | 50 | 0,1 | 3 4 3 5 4 4 2 6 3 1 6 7 5 6 4 3 3 5 6 2 2 7 7 8 5 6 3 2 5 4 6 6 5 4 6 4 5 3 2 4 7 3 2 1 2 3 8 5 6 5 | 25 3 20 15 5 23 30 35 6 2 2 29 31 7 31 8 25 3 2 2 30 33 24 20 19 10 15 35 7 1 2 33 34 25 20 21 25 22 2 33 31 15 10 11 10 5 3 30 31 5 | 66/0,20с | 66/0,0156с |
На основе данных, приведенных в таблицах, можно построить следующие графики.
Сравнение по среднему значению целевой функции
α = 0,9
Сравнение по среднему времени работы программы
Сравнение по среднему значению целевой функции
α = 0,5
Сравнение по среднему времени работы программы
Сравнительный анализ работы алгоритмов
Для решения задачи компоновки рюкзака на плоскости использовались два алгоритма: имитации отжига и метод динамического программирования.
В результате тестирования программы были получены данные, представленные в таблице. По этим данным легко увидеть, что при α = 0,9 алгоритм имитации отжига дает оптимальное решение задачи или достаточно близкого к нему, но время выполнения программы превышает время выполнения метода динамического программирования при большом количестве предметов; при α = 0,5 алгоритм имитации отжига имеет наиболее высокую скорость нахождения решения по сравнению с метод динамического программирования и дает решение, близкое к оптимальному.
en.coolreferat.com
Метод отжига Википедия
Алгори́тм имита́ции о́тжига (англ. Simulated annealing) — общий алгоритмический метод решения задачи глобальной оптимизации, особенно дискретной и комбинаторной оптимизации. Один из примеров методов Монте-Карло.
Общее описание
Поиск глобального максимума методом имитации отжига. Стандартные градиентные методы (методы спуска) в данном случае неприменимы, поскольку имеется множество локальных максимумов. Со временем температура уменьшается.Алгоритм основывается на имитации физического процесса, который происходит при кристаллизации вещества, в том числе при отжиге металлов. Предполагается, что атомы уже выстроились в кристаллическую решётку, но ещё допустимы переходы отдельных атомов из одной ячейки в другую. Предполагается, что процесс протекает при постепенно понижающейся температуре. Переход атома из одной ячейки в другую происходит с некоторой вероятностью, причём вероятность уменьшается с понижением температуры. Устойчивая кристаллическая решётка соответствует минимуму энергии атомов, поэтому атом либо переходит в состояние с меньшим уровнем энергии, либо остаётся на месте. (Этот алгоритм также называется алгоритмом Н. Метрополиса, по имени его автора).
При помощи моделирования такого процесса ищется такая точка или множество точек, на котором достигается минимум некоторой числовой функции F(x¯){\displaystyle F({\overline {x}})}, где x¯=(x1,…,xm)∈X{\displaystyle {\overline {x}}=(x_{1},\;\ldots ,\;x_{m})\in X}. Решение ищется последовательным вычислением точек x0¯,x1¯,…,{\displaystyle {\overline {x_{0}}},\;{\overline {x_{1}}},\;\ldots ,\;} пространства X{\displaystyle X}; каждая точка, начиная с x1¯{\displaystyle {\overline {x_{1}}}}, «претендует» на то, чтобы лучше предыдущих приближать решение. Алгоритм принимает точку x0¯{\displaystyle {\overline {x_{0}}}} как исходные данные. На каждом шаге алгоритм (который описан ниже) вычисляет новую точку и понижает значение величины (изначально положительной), понимаемой как «температура». Алгоритм останавливается по достижении точки, которая оказывается при температуре ноль.
Точка xi+1¯{\displaystyle {\overline {x_{i+1}}}} по алгоритму получается на основе текущей точки xi¯{\displaystyle {\overline {x_{i}}}} следующим образом. К точке xi¯{\displaystyle {\overline {x_{i}}}} применяется оператор A{\displaystyle \mathrm {A} }, который случайным образом модифицирует соответствующую точку, в результате чего получается новая точка x∗¯{\displaystyle {\overline {x^{*}}}}. Точка x∗¯{\displaystyle {\overline {x^{*}}}} становится точкой xi+1¯{\displaystyle {\overline {x_{i+1}}}} с вероятностью P(x∗¯,xi+1¯){\displaystyle P({\overline {x^{*}}},\;{\overline {x_{i+1}}})}, которая вычисляется в соответствии с распределением Гиббса:
P(x∗¯→xi+1¯∣xi¯)={1,F(x∗¯)−F(xi¯)<0exp(−F(x∗¯)−F(xi¯)Qi),F(x∗¯)−F(xi¯)⩾0{\displaystyle P({\overline {x^{*}}}\to {\overline {x_{i+1}}}\mid {\overline {x_{i}}})={\begin{cases}1,&F({\overline {x^{*}}})-F({\overline {x_{i}}})<0\\\exp \left(-{\dfrac {F({\overline {x^{*}}})-F({\overline {x_{i}}})}{Q_{i}}}\right),&{F({\overline {x^{*}}})-F({\overline {x_{i}}})\geqslant 0}\end{cases}}}Здесь Qi>0{\displaystyle Q_{i}>0} — элементы произвольной убывающей, сходящейся к нулю положительной последовательности, которая задаёт аналог падающей температуры в кристалле. Скорость убывания и закон убывания могут быть заданы по желанию создателя алгоритма.
Алгоритм имитации отжига похож на градиентный спуск, но за счёт случайности выбора промежуточной точки должен попадать в локальные минимумы реже, чем градиентный спуск. Алгоритм имитации отжига не гарантирует нахождения минимума функции, однако при правильной политике генерации случайной точки в пространстве X{\displaystyle X}, как правило, происходит улучшение начального приближения.
Применение
См. также
Примечания
Литература
- Каллан Роберт. Основные концепции нейронных сетей. — М.: Издательский дом Вильямс, 2003. — 288 с. — ISBN 5-8459-0219-X. — С. 146—148.
- Кирсанов М. Н. Графы в Maple. — М.: Физматлит, 2007. — 168 с. — ISBN 978-5-9221-0745-7. — С. 151—154.
- Джонс М. Т. Программирование искусственного интеллекта в приложениях. — М.: ДМК Пресс, 2004. — 312 с. — ISBN 5-94074-275-0. — С. 25—42.
Ссылки
wikiredia.ru
Метод отжига
Содержание
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.
Семейство распределений сроится следующим образом. Вводится функция
В качестве y для получения плотности распределений используется , таким образом, новое значение вычисляется по формуле где - случайная величина с плотностью на
При этом выходящие за границы интервала значения параметра генерируются заново или приравниваются соответствующим границам. Такую случайную величину легко промоделировать:
(2)
где - независимые случайные величины, распределенные равномерно на
Доказано, что закон изменения температуры дает статистическую гарантию нахождения глобального минимума. Для вероятности принятия также используется отдельная шкала температуры, изменяющаяся по такому же закону. Как правило, при реализации этого метода управляется двумя параметрами:
Преимущество такого методы очевидны. Во-первых, экспоненциальное убывание температуры гораздо быстрее достижимого в предыдущих методах. Во-вторых, разделение размерностей может дать большой выигрыш, как и благодаря отдельным температурам, так и благодаря ускорению процесса, в случае, если не нужно менять все координаты одновременно.
Кроме того, в отличие от отжига Коши, сверхбыстрый отжиг, как было показано, допускает очень быстрое моделирование распределения независимо от размерности S.
Среди недостатков этого метода можно назвать то, что ввиду большого количества параметров иногда требуется несколько месяцев, чтобы хорошо настроить его для решения конкретной задачи.Алгоритм Ксин Яо
Алгоритм Ксин Яо был повторным применением идеи предыдущего алгоритма. В качестве выбирается
Утверждается, что при изменении температуры по закону
достигается статистическая гарантия нахождения глобального минимума.
Однако, как показано, увеличение скорости убывания температуры вовсе не означает ускорения в решении задачи. Более того, “размазанность” распределения приводит к тому, что метод генерирует огромное число “длинных” переходов, которые отвергаются в силу низкой вероятности их принятия.
Таким образом, несмотря на то. Что этот процесс итерировать до бесконечности, получая законы изменения температуры, ценность таких “улучшений” представляется сомнительной. Более того, легко видеть, что в пределе это приводит к тривиальному методу случайного поиска, которым является метод отжига при T = 0.
Это в небольшой степени применимо и к методу сверхбыстрого отжига, так что вопрос о скорости сходимости этих методов, а также о других методах, обеспечивающих не такое быстрое убывание температуры, но большую скорость сходимости, остается открытым. Вполне возможны задачи, на которых вторая итерация вышеописанного процесса может давать не плохие результаты.Метод “тушения”
Далеко не всегда хватает вычислительных ресурсов на поиск глобального минимума. Кроме того, зачастую достаточно достигнуть не глобального оптимального решения задачи, а достаточно близкого к нему. Методы “тушения” не гарантируют нахождения глобального минимума, но, как правило, быстро находят близкое решение, а на практике зачастую и сам оптимум.
Основная идея этих методов заключается в том, чтобы скомбинировать семейство распределений одного из предыдущих четырех методов с более быстрым законом убывания температуры.
Например, можно рассматривать нормальное распределение из Больцмановского отжига, но при этом уменьшать температуру по закону .
Как правило, в этом случае c выбирается между 0.7 и 0.99. Такой метод очень быстро сходится, и для конкретных задач может давать весьма неплохое решение, близкое к оптимальному, в условиях реального времени.
Зачастую они основаны либо на нормальном распределении, либо на распределении для сверхбыстрого отжига. Кроме того, встречаются специальные распределения, подобранные опытным путем для решения конкретных задач.
Анализ результатов
Программа была запущенна с разными исходными данными большое количество раз. Результаты эксперимента занесены в таблицу.
N – количество предметов; R – объём рюкзака.
| N | R | α | Стоимость | Вес предметов | МДП | МИО |
| 10 | 10 | 0,1 | 6 5 2 3 4 5 4 8 7 3 | 2 2 2 1 2 2 3 3 1 | 27/0,17с | 27/0,0156с |
| 20 | 10 | 0,1 | 6 5 2 3 4 5 4 8 7 3 6 5 2 3 4 5 4 8 7 3 | 2 2 2 1 2 2 3 3 1 2 2 2 1 2 2 3 3 1 | 29/0,18с | 29/0,0156с |
| 20 | 20 | 0,1 0,5 0,9 | 2 4 10 12 6 8 11 3 4 7 2 4 10 12 6 8 11 3 4 7 | 13 19 8 6 10 8 4 9 8 5 13 19 8 6 10 8 4 9 8 5 | 46/0,21с | 45/0,0156с 45/0,0572с 46/0,109с |
| 30 | 20 | 0,1 0,5 0,9 | 2 9 1 10 5 7 1 12 3 4 2 9 1 10 5 7 1 12 3 4 2 9 1 10 5 7 1 12 3 4 | 5 6 2 3 7 2 5 12 5 2 2 3 7 2 5 2 5 12 5 2 2 3 7 2 5 6 8 7 3 3 | 66/0,23с | 64,7/0,014с 65,3/0,0218с 66/0,115с |
| 40 | 10 | 0,1 | 6 5 2 3 4 5 4 8 7 3 6 5 2 3 4 5 4 8 7 3 6 5 2 3 4 5 4 8 7 3 6 5 2 3 4 5 4 8 7 3 | 2 2 2 1 2 2 3 3 1 2 2 2 1 2 2 3 3 1 2 2 2 1 2 2 3 3 1 2 2 2 1 2 2 3 3 1 | 30/0,23с | 30/0,0156 |
| 40 | 20 | 0,1 0,5 0,9 | 1 4 6 8 2 4 3 9 7 10 3 1 2 6 3 7 5 4 5 5 7 1 10 3 2 2 6 8 3 9 1 10 9 5 2 3 6 7 4 2 | 2 6 8 10 12 4 6 6 8 9 2 3 10 4 6 8 2 5 15 2 1 4 2 5 6 7 9 3 2 8 5 6 4 5 2 3 5 7 8 1 | 54/0,23с | 52/0,0156с 52/0,031с 52/0,468с |
| 50 | 10 | 0,1 0,5 | 3 4 3 5 4 4 2 6 3 1 6 7 5 6 4 3 3 5 6 2 2 7 7 8 5 6 3 2 5 4 6 6 5 4 6 4 5 3 2 4 7 3 2 1 2 3 8 5 6 5 | 2 3 4 1 2 5 4 4 3 1 2 2 2 1 3 2 4 3 3 1 4 2 3 5 4 1 1 2 3 4 2 1 2 2 1 3 2 1 4 3 5 3 4 4 2 2 2 3 3 1 | 49/0,21с | 48,8/0,0652с 49/0,35с |
| 50 | 20 | 0,1 | 1 4 6 8 2 4 3 9 7 10 3 1 2 6 3 7 5 4 5 5 7 1 10 3 2 2 6 8 3 9 1 10 9 5 2 3 6 7 4 2 1 4 6 8 2 4 3 9 7 10 | 2 6 8 10 12 4 6 6 8 9 2 3 10 4 6 8 2 5 15 2 1 4 2 5 6 7 9 3 2 8 5 6 4 5 2 3 5 7 8 1 1 8 7 5 3 2 5 4 6 5 | 57/0,24с | 57/0,125с |
| 5050 | 2030 | 0,1 0,5 0,90,1 | 4 5 4 4 6 3 7 6 5 6 8 7 7 8 6 5 7 3 4 5 6 6 5 4 7 6 6 5 7 4 5 5 6 3 4 5 8 7 6 5 5 6 7 6 5 4 4 5 3 4 | 5 10 2 5 7 12 9 5 2 2 7 1 1 8 2 13 1 1 8 5 6 9 3 1 7 4 8 10 2 9 1 3 1 5 5 5 3 12 5 6 3 2 2 10 11 5 4 7 10 9 | 79/0,2398/0,21 | 77,8/0,0249с 78/0,0769с 78,8/0,503с98/0,0156с |
| 5050 | 3020 | 0,10,1 0,5 0,9 | 9 8 7 6 7 5 10 7 5 11 9 3 4 3 3 8 6 12 5 12 11 6 5 3 5 8 10 6 3 3 5 5 15 4 6 7 8 10 9 10 11 7 5 4 5 2 7 8 10 8 | 8 10 8 7 2 5 4 5 7 11 10 9 10 8 7 6 4 15 5 5 3 3 6 10 8 5 3 5 6 11 12 5 12 6 8 3 3 4 3 9 11 5 7 10 5 7 6 7 8 9 | 84/0,21с59/0,21с | 84/0,0262с57/0,0512с 57,8/0,07с 58/0,61с |
| 50 | 30 | 0,1 | 9 8 7 6 7 5 10 7 5 11 9 3 4 3 3 8 6 12 5 12 11 6 5 3 5 8 10 6 3 3 5 5 15 4 6 7 8 10 9 10 11 7 5 4 5 2 7 8 10 8 | 9 10 8 15 11 20 9 7 7 10 22 9 9 8 10 21 9 8 8 7 8 20 16 17 14 8 5 7 20 10 11 7 17 15 2 5 9 5 10 6 9 10 13 9 10 10 7 8 10 20 | 55/0,20с | 55/0,0124с |
| 50 | 50 | 0,1 0,5 0,9 | 3 4 3 5 4 4 2 6 3 1 6 7 5 6 4 3 3 5 6 2 2 7 7 8 5 6 3 2 5 4 6 6 5 4 6 4 5 3 2 4 7 3 2 1 2 3 8 5 6 5 | 25 21 20 30 21 19 31 32 20 15 23 20 15 23 20 15 21 33 33 21 18 34 20 15 22 16 34 25 20 14 15 30 21 19 31 20 23 15 23 20 14 21 15 30 21 34 18 20 15 16 14 22 25 | 21/0,21с | 18,5/0,017с 19/0,0311с 19,8/0,565с |
| 50 | 50 | 0,1 | 3 4 3 5 4 4 2 6 3 1 6 7 5 6 4 3 3 5 6 2 2 7 7 8 5 6 3 2 5 4 6 6 5 4 6 4 5 3 2 4 7 3 2 1 2 3 8 5 6 5 | 25 3 20 15 5 23 30 35 6 2 2 29 31 7 31 8 25 3 2 2 30 33 24 20 19 10 15 35 7 1 2 33 34 25 20 21 25 22 2 33 31 15 10 11 10 5 3 30 31 5 | 66/0,20с | 66/0,0156с |
На основе данных, приведенных в таблицах, можно построить следующие графики.
Сравнение по среднему значению целевой функции
α = 0,9
Сравнение по среднему времени работы программы
Сравнение по среднему значению целевой функции
α = 0,5
Сравнение по среднему времени работы программы
Сравнительный анализ работы алгоритмов
Для решения задачи компоновки рюкзака на плоскости использовались два алгоритма: имитации отжига и метод динамического программирования.
В результате тестирования программы были получены данные, представленные в таблице. По этим данным легко увидеть, что при α = 0,9 алгоритм имитации отжига дает оптимальное решение задачи или достаточно близкого к нему, но время выполнения программы превышает время выполнения метода динамического программирования при большом количестве предметов; при α = 0,5 алгоритм имитации отжига имеет наиболее высокую скорость нахождения решения по сравнению с метод динамического программирования и дает решение, близкое к оптимальному.
ua.coolreferat.com
