Общие рекомендации к программной реализации ГА

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

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

Таблица

Компонент ГА Процедурный подход Объектно-ориентированный подход
Особь Одномерный массив для записи значений генов. Размерность массива совпадает с количеством генов у одной особи (количество генов равно числу оптимизируемых параметров) Класс «Особь», содержащий коллекцию генов с реализованным алгоритмом ее обхода (паттерн iterator).

Окончание таблицы

Компонент ГА Процедурный подход Объектно-ориентированный подход
Популяция Двумерный массив, в котором i-я строка содержит гены i-й особи. Типизированный класс «Популяция», содержащий коллекцию «особей». В роли параметра-типизатора может выступать класс «особь», если типов особей несколько и в каждом типе – своя логика вычислений
Оценка популяции Подпрограмма оценки строк массива популяции в соответствии с выбранной целевой функцией. Метод управляющего класса, оценивающий популяцию в соответствии с выбранной целевой функцией.
Приспособленность популяции Одномерный массив, в котором i-й элемент соответствует приспособленности i-й особи. Свойство в классе «особь», характеризующее приспособленность данной особи
Особи, выбранные для скрещивания Двумерный массив, строки которого соответствуют хромосомам особей, выбранным для скрещивания. Объект класса «популяция», содержащий объекты класса «особь», соответствующие выбранным особям
Реализация скрещивания, мутации, формирования нового поколения Подпрограммы, обрабатывающие элементы массива, представляющего популяцию особей, а также популяцию особей, выбранных для скрещивания. Методы управляющего класса, работающие с основной популяцией и выборкой особей для скрещивания.

 


Список литературы

1. Holland J. H., Adaptation in Neural and Artificial Systems, University of Michigan Press: Ann Arbor, 1975.

2. Whitley D. L., Genetic Algorithms and Evolutionary Computing, Van Nostrand's Scientific Encyclopedia, Princeton: New Jersey, 2002.

3. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И. Д. Рудинского – М.: Горячая линия – Телеком, 2006. – 452 с.

4. В. В. Емельянов, В. В. Курейчик, В. М. Курейчик Теория и практика эволюционного моделирования. – М.: ФИЗМАТЛИТ, 2003. – 432 c.

5. De Jong K. An analysis of the behavior of a class of genetic adaptive systems. Doctoral dissertation. – University of Michigan: Ann Arbor. – University Microfilms No. 76-9381. – 1975.

6. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. – СПб: Питер, 2001. – 368 с.

 

Справочные материалы

· http://basegroup.ru/, интернет-ресурс BaseGroup Labs (теория ГА, исходные тексты программ)

· http://www.gotai.net/, интернет- ресурс, посвященный технологиям искусственного интеллекта (теория, публикации, исходные тексты программ, примеры)

· http://www.exponenta.ru/soft/Mathcad/Mathcad.asp, интернет-ресурс компании AXOFT, посвященный описанию различных пакетов математического и физического моделирования, в частности MathCAD.

· Chonoles M.J., Schardt J.A. UML 2 for Dummies, Hungry Minds, 2003 г. - 412 с

 


[1] http://ru.wikipedia.org/wiki/UML, интернет-ресурс Wiki, посвященный UML-нотации.

[2] См. там же

[3] Г. Д. Дмитревич, А. И. Ларистов, В. А. Павлушин Программирование методов оптимизации: Методические указания к лабораторным работам. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2004. – 24-31 сс.