Действие происходит на поверхности тора размером 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 разрабатывался как средство анализа и сравнения различных методов оптимизации на конкретных задачах. В систему закладывалась возможность добавления новых алгоритмов и рассматриваемых задач как самими авторами на различных этапах разработки, так и другими студентами – с помощью подключения отдельных модулей (плагинов).
Проектирование модулей предполагает изучение структуры уже реализованных методов оптимизации, и постарении на их основе собственных. Ниже приведены базовые рекомендации, которым необходимо следовать при разработке собственных модулей, определяющих алгоритм решения.
1. Реализуйте алгоритм поиска оптимального решения – класс, наследованный от абстрактного класса Algorithm. Данный класс должен определять следующие методы.
· Title – возвращает стоку с названием реализуемого алгоритма.
· Description – возвращает строку с кратким описанием алгоритма.
· OptimizationDirection – возвращает одну из двух именованных констант: OptimizationDirection.Minimize или OptimizationDirection.Maximize.
· Initialize - описывает начальное состояние в алгоритме поиска решения.
· NextIteration – описывает действия, происходящие на очередной итерации алгоритма.
· В переменной BestIndividual типа Individual должна содержаться актуальная информация об объекте типа Individual c лучшей на данной итерации алгоритма целевой функцией.
Методы Title и Description в свою очередь являются абстрактными методами класса Plugin, от которого наследуется класс Algorithm.
2. Реализуйте интерфейс SearchOperator, наследованный от интерфейса ICreateOperator. В данном интерфейсе должен быть определен метод Create, возвращающий объект типа Individual (абстрактный класс, определяется для конкретной задачи). Также в SearchOperator’е реализуются все необходимые методы для работы с объектами Individual – например, операции мутации и кроссовера.
3. Необходимо удостовериться что библиотека *.dll откомпилированного модуля находится в папке plugins проекта Framework.
Для реализации новой задачи в комплексе GLOpt необходимо сделать следующее.
1. Реализовать класс - наследник от абстрактного класса Individual, определяющего объект к которому в дальнейшем применяется алгоритм оптимизации. Так, в задачи о ферзях таким объектом выступает шахматная доска с расставленными на ней ферзями.
2. Реализовать класс – наследник от абстрактного класса Problem. В данном классе должны быть определены методы Title, Description, OptimizationDirecrtion, аналогичные методам, описанным в разделе рекомендаций по реализации алгоритма. Также необходимо определить метод EvaluateIndividual, возвращающий значение типа double – значение целевой функции для данного индивида.
3. Для реализации компоненты визуализации текущего решения требуется определить класс Viewer, наследуемый от класса IndividualViewer, и в частности определить метод ViewIndividual, вызывающий графическую форму, либо представляющий данные о решении в любом другом удобном для пользователя виде.
4. Необходимо удостовериться что библиотека *.dll откомпилированного модуля находится в папке plugins проекта Framework.
К программному комплексу GLOpt прилагается пакет технической документации, призванный упростить разработку собственных модулей задач и алгоритмов, а также понимание архитектурных принципов самого модуля. Документация получена с помощью генератора документации компании Microsoft – Sandcastle.
7. Заключение
Реализованный программный комплекс позволяет анализировать эффективность тех или иных методов глобальной оптимизации на любых задачах, к которым применима оптимизация.
Возможным является добавление в среду как собственных задач для рассмотрения, алгоритмов их решения, так и реализация визуализаторов для соответствующих задач и методов.
В ходе сравнения эффективности различных методов оптимизации для решения уже существующих в среде задач были получены следующие результаты. Для решения задачи об умном муравье наиболее эффективным оказался простой клеточный алгоритм, показавший чуть более высокую фитнесс-функцию, чем клеточный. Метод отжига показал на этой задаче существенно более низкие результаты. Для решения же задачи о расстановке ферзей при разных установках параметров наиболее эффективными оказались метод отжига и клеточный генетический алгоритм. Простой генетический алгоритм при любых настройках показывал худшие результаты. Однако следует понимать, что в данном случае сильна зависимость результатов от конкретной реализации алгоритмов.
В будущих версиях планируется проработать систему документации и подсказок, облегчающая понимание пользователями уже существующих решений и упрощающая реализацию собственных плагинов.
Источники
1. Ingber A . L . Simulating Annealing: Practice versus theory -
Mathl. Comput. Modelling, 1993
2. Елкин Д. И. Тяхти А. C . Метод отжига - СПбГУ ИТМО, 2008, https://rain.ifmo.ru/cat/view.php/theory/unsorted/ai-annealing-2008/article.pdf
3. Бедный Ю.Д., Шалыто А.А. Применение генетических алгоритмов для построения автоматов в задаче «Умный муравей». https://is.ifmo.ru/works/_ant.pdf
4. Джонс М. Т. Программирование искусственного интеллекта в приложениях – М.: ДМК-Пресс, 2004
5. Лопатин А. Методы отжига. Электронный конспект – Крысталь Б.
www.cs-seminar.spb.ru/reports/52.pdf
6. Орлянская И.В Современные подходы к построению методов глобальной оптимизации. https://zhurnal.ape.relarn.ru/articles/2002/189.pdf
7. Соколов Д.О., Давыдов А.А., Царев Ф.Н., Шалыто А.А. Виртуальная лаборатория обучения генетическому программированию для генерации управляющих конечных автоматов. – МК МГУ. М.: МАКС Пресс, 2008, с. 179 – 183. https://is.ifmo.ru/works/_2_93_davidov_sokolov.pdf
Исходные коды
Ознакомиться с исходными кодами можно в архиве, прилагаемом к данной работе. Файловая структура программного комплекса выглядит следующим образом:
C:.
│ GloptFramework.sln
│
├───ArtificialAnt – задача об «умном муравье»
│ ├───AntViewer
│ │ AntViewerForm.cs
│ │ AntViewerForm.Designer.cs
│ │ FieldControl.cs
│ │ FieldControl.Designer.cs
│ │
│ ├───IndividualInfo – описание индивида в задаче
│ │ Automation.cs
│ │
│ ├───ProblemInfo – представление задачи
│ │ SimpleAntProblem.cs
│ │
│ └───_Internal
│ ├───Mover
│ │ IMover.cs
│ │ SimpleMover.cs
│ │
│ └───Phenotype
│ AbstractAnt.cs
│ Ant.cs
│ SimpleAnt.cs
│
├───CellularGenetic – клеточный генетический алгоритм
│ CellularGeneticAlgorithm.cs
│
├───Charts
│ ChartControl2D.cs
│ IChart.cs
│ SimpleChart.cs
│ SurfaceChart.cs
│
├─── Framework
│ Program.cs
│
├───Genetic – генетический алгоритм
│ │ GeneticOptimizationAlgorithm.cs
│ │
│ └───Operators
│ GeneticSearchOperator.cs
│ GeneticSearchOperatorOnAutomation.cs – реализация |алгоритма с использованием особи на базе автомата
│ GeneticSearchOperatorOnBoard.cs – реализация |алгоритма с использованием особи на базе шахматной доски
│ IGeneticSearchOperator.cs
│ SearchOperatorOnBoard.cs
│
├───NewBrain – управляющие модули программного комплекса
│ │ AlgorithmHistory.cs
│ │ Brain.cs
│ │ ClassDiagram1.cd
│ │ ConfigurationManager.cs
│ │
│ ├───Algorithms
│ │ AlgorithmRunner.cs
│ │ ASOPair.cs
│ │ ASOPairEditor.cs
│ │
│ ├───Attributes
│ │ ConfigurableAttribute.cs
│ │ IndividualTypeAttribute.cs
│ │ SearchOperatorTypeAttribute.cs
│ │
│ ├───ComponentModel
│ │ IndividualViewer.cs
│ │
│ ├───Exceptions
│ │ TypeAttributeException.cs
│ │
│ ├───Plugins
│ │ Algorithm.cs
│ │ CustomProperties.cs
│ │ ICreateOperator.cs
│ │ Individual.cs
│ │ OptimizationDirection.cs
│ │ Plugin.cs
│ │ PluginManager.cs
│ │ Problem.cs
│ │ SearchOperator.cs
│ │
│ └───UI
│ ├───Controls
│ └───Forms
├───QueensPlacement – задача о расстановке N ферзей
│ ├───IndividualInfo – представление индивида в задаче
│ │ Board.cs
│ │
│ ├───ProblemInfo
│ │ QueensPlacementProblem.cs
│ │
│ └───QueenViewer – визуализатор индивида на базе шахматной доски
│ FieldControl.cs
│ FieldControl.Designer.cs
│ QueenViewerForm.cs
│ QueenViewerForm.Designer.cs
│
├───SimpleGeneticOptimizer – простой генетический алгоритм
│ SimpleGeneticOptimizationAlgorithm.cs
│
├───SimulatedAnnealing – метод имитации отжига
│ GaussianRandom.cs
│ ISimulatedAnnealingOperator.cs
│ SimulatedAnnealingAlgorithm.cs
│ SimulatedAnnealingOperatorOnAutomation.cs
│ SimulatedAnnealingOperatorOnBoard.cs
│
└───Utils
├───ComponentModel
│ EditorHelper.cs
│ SimpleTypeDescriptorContext.cs
│
└───Drawing
MatrixHelper.cs
RectangleHelper.cs