Курсовая работа
Программный комплекс для изучения методов глобальной оптимизации
«GlOpt»
Оглавление
Введение. 3
1. Глобальная оптимизация. 3
2.Алгоритм имитации отжига. 3
3. Схемы алгоритма отжига. 5
3.1. Больцмановский отжиг. 5
3.2. Отжиг Коши (быстрый отжиг) 6
3.3. Сверхбыстрый отжиг. 6
3.4. Другие схемы алгоритма отжига. 7
4. Исследуемые задачи. 7
4.1. Задача о расстановке N ферзей. 7
4.2. Задача об «Умном муравье». 8
5. Структура программного комплекса GLOpt 9
5.2 Класс Problem.. 9
5.3 Класс Individual 9
5.4 Класс SearchOperator 10
5.5 Класс Algorithm.. 10
5.4 Интерфейс IIndividualViewer 10
7. Заключение. 13
Источники. 14
Исходные коды.. 15
Введение
Целью данной работы являлось изучение методов глобальной оптимизации, создание программного комплекса, позволяющего провести количественные сравнения между различными оптимизационными методами на различных задачах оптимизации.
По схожей тематике известна работа Соколова Д.О и Давыдова А.А [7], однако реализованная авторами виртуальная лаборатория на наш взгляд обладает рядом недостатков, которые мы постарались устранить в настоящей работе. Одним из главных требований предъявляемых к программному комплексу являлась гибкость, его дальнейшая расширяемость, позволяющая в будущем наращивать не только набор рассматриваемых алгоритмов решения какой-либо конкретной задачи оптимизации, но и добавлять к рассмотрению новые проблемы, наглядно проводить их сравнительный анализ. В работе основное внимание было сосредоточено на алгоритме имитации отжига, сравнении его с генетическими алгоритмами.
Глобальная оптимизация
Под термином глобальная оптимизация будем понимать процесс поиска экстремума или экстремумов функции, которая, например, в эволюционном моделировании соответствует приспособленности особи, интерпретируемой как ее способность решать поставленную задачу.
Глобальная оптимизация применима к широкому классу задач. Она находит применение в проблемах проектирования, теории управления физическими процессами, распределении ограниченных ресурсов, анализе данных и других областях.
Известные методы глобальной оптимизации можно разделить на детерминированные и стохастические. Детерминированные методы находят глобальное решение посредством поиска на всем допустимом множестве. Поэтому большинство детерминированных алгоритмов теряют эффективность с возрастанием размерности задачи. Стохастические методы позволяют уйти от проблем детерминированных алгоритмов. Стохастический подход присутствует не только в разработке алгоритма, но и, например, при определении условия остановки.
К числу методов глобальной оптимизации относят алгоритм имитации отжига, генетические алгоритмы, метод виртуальных частиц, алгоритм контролируемого случайного поиска.
Алгоритм имитации отжига
Метод отжига [?], также известен под названиями: метод обжига, метод симуляции отжига, метод модельной закалки, simulated annealing. Этот метод – техника оптимизации, использующая упорядоченный случайный поиск на основе аналогии с процессом образования в веществе кристаллической структуры с минимальной энергией, происходящем при охлаждении этого вещества.
Алгоритм имитации отжига основан на моделировании физического процесса, который происходит при кристаллизации вещества из жидкого состояния в твердое (к примеру, при отжиге металлов). Предполагается, что, во-первых, процесс протекает при понижающейся температуре, а во-вторых, атомы в веществе уже выстроились в кристаллическую решетку, однако переходы отдельных атомов из одной ячейки в другую еще возможны. Вероятность этих переходов в свою очередь обусловлена температурой: чем ниже температура, тем ниже вероятность. Устойчивая кристаллическая структура вещества соответствует минимальному значению энергии. Это значит, что атом либо переходит в состояние с меньшим уровнем энергии, либо остается на месте.
Формализуем данный процесс. Фактически, при моделировании ищется некоторая точка (либо множество точек), на котором достигается минимум некоторой числовой функции F(x). Строится последовательность точек 
, где 
соответствует начальному разделению. При достижении точки 
алгоритм завершает свою работу. Пусть рассматривается текущая точка 
. К ней применяется некоторый оператор A, который произвольным образом модифицирует эту точку, в результате чего получается новая точка 
Вероятность, с которой станет следующей точкой 
равна 
, где P - распределение Гиббса:
Здесь 
-элементы произвольной убывающей, сходящейся к нулю последовательности. Она представляет собой аналог понижающейся температуры во время реального физического процесса.
Достоинством метода отжига является свойство избегать "ловушек" в локальных минимумах оптимизируемой функции, и продолжить поиск глобального минимума. Это достигается за счет принятия не только изменений параметров, приводящих к уменьшению значения функции, но и некоторых изменений, увеличивающих ее значение, в зависимости от температуры Т – характеристики моделируемого процесса. Чем выше температура, тем большие "ухудшающие" изменения (аналогичные случайным флуктуациям в нагретом веществе) допустимы, и больше их вероятность. Еще одним достоинством является то, что даже в условиях нехватки вычислительных ресурсов для нахождения глобального минимума, метод отжига, как правило, выдает весьма неплохое решение (один из локальных минимумов). Л. Ингбером [?] показано, что метод отжига и его модификации являются одним из наиболее эффективных методов случайного поиска оптимального решения для большого класса задач. Им же проведен сравнительный анализ адаптивного метода отжига (Adaptive Simulated Annealing - ASA) и генетических алгоритмов, из которого следует, что на большинстве задач метод отжига не проигрывает генетическим алгоритмам, а на многих и выигрывает. К настоящему времени разработано множество различных вариантов метода отжига, как общих, так и их специализаций для решения конкретных задач.
Алгоритм имитации отжига можно представить в виде следующей структурной схемы (рис.1).
Рис. 1
3. Схемы алгоритма отжига
3.1. Больцмановский отжиг
Исторически первой схемой метода отжига является схема Больцмановского отжига. Эта схема использовалась Н.Метрополисом для вычисления многомерных интегралов пути в задачах статистической физики, а также С.Киркпатриком для решения задачи нахождения оптимальной разводки микросхем. В Больцмановском отжиге изменение температуры задается формулой
Семейство распределений Q(x; T) выбирается как семейство нормальных
распределений с математическим ожиданием и дисперсией, т.е. задается
плотностью
где D - размерность пространства состояний. Пространство состояний предполагается метрическим. Для больцмановской схемы доказано, что при достаточно больших 
и общем числе шагов k, выбор такого семейства распределений гарантирует нахождение глобального минимума. Основным недостатком метода является медленное убывание температуры.
3.2. Отжиг Коши (быстрый отжиг)
В результате совершенствования больцмановского метода Цу и Хартли предложили алгоритм, использующий другую схему изменения температуры
В качестве Q используются нормированные распределения Коши с плотностью
Однако это распределение сложно моделировать в пространствах размерностью больше единицы. Кроме того, в них накладывается ряд ограничений на закон изменения температуры, что является серьезным недостатком данного алгоритма.
3.3. Сверхбыстрый отжиг
Недостатки двух предыдущих методов привели к тому, что в 1989 году
американским исследователем Л. Ингбером был разработан метод сверхбыстрого отжига (Very Fast Annealing). В нем пространство S считается состоящим из D-мерных векторов 
где 
. Кроме этого,
температура по каждой из координат может различаться, таким образом,
T также является вектором размерности D. Семейство распределений
строится следующим образом. Вводится функция:
В качестве y для получения плотности распределений используется
. 
вычисляется по формуле 
, где 
- случайная величина с плотностью g ( i ; T ) на [-1;1].Такую случайную величину легко промоделировать
,
где 
- независимые случайные величины, равномерно распределенные на [0,1]. Доказано, что закон изменения температуры
дает статистическую гарантию нахождения глобального минимума. 
как правило управляется двумя параметрами:
Преимущества такого метода очевидны. Экспоненциальное убывание температуры гораздо быстрее достижимого в предыдущих методах. Разделение размерностей может дать большой выигрыш, как благодаря отдельным температурам (т.к. специфика конкретной задачи может сильно различать параметры), так и благодаря ускорению процесса, в случае, если не нужно менять все координаты одновременно. Кроме того, в отличие от отжига Коши, сверхбыстрый отжиг допускает очень быстрое моделирование распределения независимо от размерности пространства. Недостатком данного метода является сложность его настройки для решения конкртеной задачи ввиду большого количества параметром.
3.4. Другие схемы алгоритма отжига
Известны и другие алгоритмы отжига. Например, алгоритм Ксин Яо, полученный повторением метода сверхбыстрого отжига. Вполне возможны задачи, где этот метод показывает лучшую производительность, чем предыдущий рассмотренный, однако на практике метод Ксин Яо зачастую выдает результат худший, чем при сверхбыстром отжиге.
В тех случаях, когда достаточно не глобального оптимального решения, а лишь близкого к нему, либо при отсутствии достаточных вычислительных ресурсов находят свое применение так называемые методы «тушения». Их идея заключена в комбинировании семейства распределений одного из вышеописанных методов с более быстрым законом изменения температуры.
4. Исследуемые задачи