Программный комплекс для изучения методов глобальной оптимизации «GlOpt» (стр. 2 из 3)
Недостатки двух предыдущих методов привели к тому, что в 1989 году
американским исследователем Л. Ингбером был разработан метод сверхбыстрого отжига (Very Fast Annealing). В нем пространство S считается состоящим из D-мерных векторов
где 
. Кроме этого,температура по каждой из координат может различаться, таким образом,
T также является вектором размерности D. Семейство распределений
строится следующим образом. Вводится функция:
В качестве y для получения плотности распределений используется
. 
вычисляется по формуле 
, где 
- случайная величина с плотностью g(i;T) на [-1;1].Такую случайную величину легко промоделировать 
,где
- независимые случайные величины, равномерно распределенные на [0,1]. Доказано, что закон изменения температуры 
дает статистическую гарантию нахождения глобального минимума.
как правило управляется двумя параметрами: 
Преимущества такого метода очевидны. Экспоненциальное убывание температуры гораздо быстрее достижимого в предыдущих методах. Разделение размерностей может дать большой выигрыш, как благодаря отдельным температурам (т.к. специфика конкретной задачи может сильно различать параметры), так и благодаря ускорению процесса, в случае, если не нужно менять все координаты одновременно. Кроме того, в отличие от отжига Коши, сверхбыстрый отжиг допускает очень быстрое моделирование распределения независимо от размерности пространства. Недостатком данного метода является сложность его настройки для решения конкртеной задачи ввиду большого количества параметром.
3.4. Другие схемы алгоритма отжига
Известны и другие алгоритмы отжига. Например, алгоритм Ксин Яо, полученный повторением метода сверхбыстрого отжига. Вполне возможны задачи, где этот метод показывает лучшую производительность, чем предыдущий рассмотренный, однако на практике метод Ксин Яо зачастую выдает результат худший, чем при сверхбыстром отжиге.
В тех случаях, когда достаточно не глобального оптимального решения, а лишь близкого к нему, либо при отсутствии достаточных вычислительных ресурсов находят свое применение так называемые методы «тушения». Их идея заключена в комбинировании семейства распределений одного из вышеописанных методов с более быстрым законом изменения температуры.
4.1. Задача о расстановке N ферзей
В качестве примера использования алгоритма отжига рассмотрим задачу о расстановке N шахматных ферзей на доске размером N*N. Ферзи должны быть расставлены так, чтобы ни один из них не бил другого. Это означает, что ни на одной вертикали, горизонтали или диагонали не могут находиться два ферзя одновременно. Иными словами, функция коллизий должна принимать минимальное значение. Пример решения задачи для размерности N = 8 показан на рисунке 2.
Рис. 2
Данная задача в течение многих лет решалась известными математиками, такими как Гаусс, однако оптимальное решение найдено не было. Задача может решаться непосредственно - алгоритмом полного перебора с возвратом, однако это не позволяет рассматривать данную задачу при достаточно больших N. На обычном персональном компьютере за разумное время может быть получен результат лишь для N менее 15. В то же время с помощью метода имитации отжига задача может достаточно эффективно решаться для значительно большей размерности, однако при достаточно больших N решение может содержать коллизии.
4.2. Задача об «Умном муравье»
Действие происходит на поверхности тора размером 32x32 клетки. В некоторых клетках находится еда. Муравей начинает движение из клетки, помеченной «Start».
За ход муравей может выполнить следующие действия:
· повернуть налево;
· повернуть направо;
· сделать шаг вперед и, если в новой клетке есть еда, съесть ее;
· ничего не делать.
Игра длится 200 ходов. Цель игры - создать муравья «с минимальным числом состояний», который за минимальное число ходов съест как можно больше яблок.
Рис. 3 Визуализатор особи в задаче об умном муравье комплекса GLOpt
5. Структура программного комплекса GLOpt
Важнейшим критерием при создании программного комплекса являлось удобство и легкость его расширения на максимальное количество задач оптимизации. Реализация этой задачи потребовала разработки специальной программной структуры, которая бы полностью соответствовала предъявляемым требованиям к масштабируемости, а также была бы довольно простой для понимания, позволяя желающим внедрять и анализировать методы оптимизации, не вошедшие в рамки данной работы.
Основные классы фреймворка GLOpt, реализованного на языке С# под платформой Microsoft.NET, представлены на рисунке 4. Управляющий класс Brain ответственен за загрузку основных сущностей программного комплекса: Problem, Optimizer, ISearchOperator, а также осуществляет контроль над текущими процессами. Сама же задача глобальной оптимизации полностью описывается абстрактными классами Problem, Algorithm, Individual, SearchOperator, от которых в свою очередь наследуются классы, реализующие конкретные задачи, например, задачу «умного муравья» или же метод имитации отжига.
5.2 Класс Problem
Абстрактный класс Problem содержит метод OptimizationDirection, возвращающий информацию о направления оптимизации (min, max) и метод EvaluateIndividual, служащий для вычисления целевой fitness-функции у конкретной особи. Наследники этого класс должны реализовывать эти методы, а также методы обеспечивающие доступ к базовой информации о задаче: названии, ее кратком описании.
public abstract class Problem : Plugin
{
public abstract OptimizationDirection OptimizationDirection { get; }
public abstract double EvaluateIndividual(Individual individual);
}
5.3 Класс Individual
Абстрактный класс Individual реализует представление индивидуальной для каждой задачи оценочной характеристики Fitness, описывает метод сравнения индивидов между собой.
public abstract class Individual : IComparable<Individual>
{
public double Fitness
{
…
}
#region IComparable<Individual> Members
public int CompareTo(Individual other)
{
return Fitness.CompareTo(other.Fitness);
}
#endregion
}
5.4 Класс SearchOperator
Класс SearchOperator необходим для организации требуемых в задаче операций над объектами класса Individual.Так, например, в задаче «умного муравья» это методы мутации индивида и скрещивания индивидов между собой (кроссовер), а в методе имитации отжига – изменение уже найденного решения в соответствии с выбранным вероятностным распределением. Классы наследники должны определять следующие методы.
· Create – создание новой особи.
· Modify – изменение особи каким-либо образом (например случайно), с учетом интерфейса, который требует Algorithm.
public abstract class SearchOperator : Plugin, ICreateOperator
{
#region ICreateOperator Members
public abstract Individual Create(Random r);
#endregion
}
5.5 Класс Algorithm
Класс Algorithm содержит следующие методы:
· OptimizationDirection – направление оптимизации, характеризаующее сам алгоритм (направление по умолчанию).
· SearchOperator – набор методов для работы с особями, которые использует алгоритм.
· Initialize – установка необходимых для работы алгоритма параметров.
· NextIteration – метод, описывающий шаг итерации алгоритма.
· Terminated – метод, позволяющий определить - закончил ли алгоритм работу. Если метод возвращает true, то алгоритм автоматически перезапускается.
public abstract class Algorithm : Plugin
{
protected internal abstract OptimizationDirection OptimizationDirection { get; }
protected internal SearchOperator SearchOperator {get; internal set; }
protected internal virtual List<Individual> CurrentIndividuals { get;
protected set; }
protected internal virtual Individual BestIndividual { get; set; }
protected internal virtual void Initialize(){}
protected internal virtual void NextIteration(){}
protected internal virtual bool Terminated() {}
}
5.4 Интерфейс IIndividualViewer
Данный интерфейс необходим для создания возможности отображать решения конкретной задачи визуально. Для визуализации решения также должен быть подготовлен необходимый набор форм.
public interface IIndividualViewer
{
void ViewIndividual(Individual individual);
}
Рис.4
6. Инструкция по разработке модулей GLOpt
Программный комплекс GLOpt разрабатывался как средство анализа и сравнения различных методов оптимизации на конкретных задачах. В систему закладывалась возможность добавления новых алгоритмов и рассматриваемых задач как самими авторами на различных этапах разработки, так и другими студентами – с помощью подключения отдельных модулей (плагинов).
Проектирование модулей предполагает изучение структуры уже реализованных методов оптимизации, и постарении на их основе собственных. Ниже приведены базовые рекомендации, которым необходимо следовать при разработке собственных модулей, определяющих алгоритм решения.