Программный комплекс для изучения методов глобальной оптимизации «GlOpt» (стр. 1 из 3)

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

По схожей тематике известна работа Соколова Д.О и Давыдова А.А [7], однако реализованная авторами виртуальная лаборатория на наш взгляд обладает рядом недостатков, которые мы постарались устранить в настоящей работе. Одним из главных требований предъявляемых к программному комплексу являлась гибкость, его дальнейшая расширяемость, позволяющая в будущем наращивать не только набор рассматриваемых алгоритмов решения какой-либо конкретной задачи оптимизации, но и добавлять к рассмотрению новые проблемы, наглядно проводить их сравнительный анализ. В работе основное внимание было сосредоточено на алгоритме имитации отжига, сравнении его с генетическими алгоритмами.

1. Глобальная оптимизация

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

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

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

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

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

Метод отжига [?], также известен под названиями: метод обжига, метод симуляции отжига, метод модельной закалки, simulated annealing. Этот метод – техника оптимизации, использующая упорядоченный случайный поиск на основе аналогии с процессом образования в веществе кристаллической структуры с минимальной энергией, происходящем при охлаждении этого вещества.

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

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

, где

соответствует начальному разделению. При достижении точки

алгоритм завершает свою работу. Пусть рассматривается текущая точка

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

Вероятность, с которой

станет следующей точкой

равна

, где P- распределение Гиббса:

Здесь

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

Достоинством метода отжига является свойство избегать "ловушек" в локальных минимумах оптимизируемой функции, и продолжить поиск глобального минимума. Это достигается за счет принятия не только изменений параметров, приводящих к уменьшению значения функции, но и некоторых изменений, увеличивающих ее значение, в зависимости от температуры Т – характеристики моделируемого процесса. Чем выше температура, тем большие "ухудшающие" изменения (аналогичные случайным флуктуациям в нагретом веществе) допустимы, и больше их вероятность. Еще одним достоинством является то, что даже в условиях нехватки вычислительных ресурсов для нахождения глобального минимума, метод отжига, как правило, выдает весьма неплохое решение (один из локальных минимумов). Л. Ингбером [?] показано, что метод отжига и его модификации являются одним из наиболее эффективных методов случайного поиска оптимального решения для большого класса задач. Им же проведен сравнительный анализ адаптивного метода отжига (Adaptive Simulated Annealing - ASA) и генетических алгоритмов, из которого следует, что на большинстве задач метод отжига не проигрывает генетическим алгоритмам, а на многих и выигрывает. К настоящему времени разработано множество различных вариантов метода отжига, как общих, так и их специализаций для решения конкретных задач.

Алгоритм имитации отжига можно представить в виде следующей структурной схемы (рис.1).

Рис. 1

3. Схемы алгоритма отжига

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

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

Семейство распределений Q(x; T) выбирается как семейство нормальных
распределений с математическим ожиданием и дисперсией, т.е. задается
плотностью

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

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

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

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

В качестве Q используются нормированные распределения Коши с плотностью

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