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

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 необходимо сделать следующее.

Реализовать класс - наследник от абстрактного класса Individual, определяющего объект к которому в дальнейшем применяется алгоритм оптимизации. Так, в задачи о ферзях таким объектом выступает шахматная доска с расставленными на ней ферзями.

Реализовать класс – наследник от абстрактного класса Problem. В данном классе должны быть определены методы Title, Description, OptimizationDirecrtion, аналогичные методам, описанным в разделе рекомендаций по реализации алгоритма. Также необходимо определить метод EvaluateIndividual, возвращающий значение типа double – значение целевой функции для данного индивида.
Для реализации компоненты визуализации текущего решения требуется определить класс Viewer, наследуемый от класса IndividualViewer, и в частности определить метод ViewIndividual, вызывающий графическую форму, либо представляющий данные о решении в любом другом удобном для пользователя виде.

Необходимо удостовериться что библиотека *.dll откомпилированного модуля находится в папке plugins проекта Framework.

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

7. Заключение

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

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

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

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

Источники

1. Ingber A.L. Simulating Annealing: Practice versus theory -

Mathl. Comput. Modelling, 1993

2. Елкин Д. И. Тяхти А. C. Метод отжига - СПбГУ ИТМО, 2008, http://rain.ifmo.ru/cat/view.php/theory/unsorted/ai-annealing-2008/article.pdf

3. Бедный Ю.Д., Шалыто А.А. Применение генетических алгоритмов для построения автоматов в задаче «Умный муравей». http://is.ifmo.ru/works/_ant.pdf

4. Джонс М. Т. Программирование искусственного интеллекта в приложениях – М.: ДМК-Пресс, 2004

5. Лопатин А. Методы отжига. Электронный конспект – Крысталь Б.

www.cs-seminar.spb.ru/reports/52.pdf

6. Орлянская И.В Современные подходы к построению методов глобальной оптимизации. http://zhurnal.ape.relarn.ru/articles/2002/189.pdf

7. Соколов Д.О., Давыдов А.А., Царев Ф.Н., Шалыто А.А. Виртуальная лаборатория обучения генетическому программированию для генерации управляющих конечных автоматов. – МК МГУ. М.: МАКС Пресс, 2008, с. 179 – 183. http://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