- •1. Практикум
- •Практические занятия 3, 4. Изучение различных кодировок генотипа.
- •Практические занятия 5, 6. Применение эвристических операторов.
- •Практическое занятие 7. Проектирование пользовательского интерфейса.
- •Практическое занятие 8. Исследование схемы «генетический алгоритм – классический метод оптимизации».
- •2. Вспомогательные материалы.
- •2.1. Пример работы га и анализа результатов.
- •2.2. Общие рекомендации к программной реализации га
- •Список литературы
- •Справочные материалы
2.2. Общие рекомендации к программной реализации га
Поскольку ГА представляют собой достаточно универсальный подход к решению многоэкстремальных задач, то выбор языка программирования не играет решающей роли. Саму программу можно писать, используя как объектно-ориентированный подход, так и процедурный. В таблице предложены соображения по поводу способа реализации различных компонентов ГА при использовании обоих подходов. Приведенные советы по реализации ГА не являются эталонными и, возможно, далеки от идеала проектирования. Данные, приведенные в этой таблице, могут служить в качестве опорной точки для программной реализации ГА.
Стоит отметить, что большую гибкость и расширяемость программной реализации не только ГА, но и любого другого алгоритма, можно достичь, грамотно применяя объектно-ориентированный подход и паттерны проектирования [6].
Таблица
Компонент ГА |
Процедурный подход |
Объектно-ориентированный подход |
Особь |
Одномерный массив для записи значений генов. Размерность массива совпадает с количеством генов у одной особи (количество генов равно числу оптимизируемых параметров) |
Класс «Особь», содержащий коллекцию генов с реализованным алгоритмом ее обхода (паттерн iterator). |
Окончание таблицы
Компонент ГА |
Процедурный подход |
Объектно-ориентированный подход |
Популяция |
Двумерный массив, в котором i-я строка содержит гены i-й особи. |
Типизированный класс «Популяция», содержащий коллекцию «особей». В роли параметра-типизатора может выступать класс «особь», если типов особей несколько и в каждом типе – своя логика вычислений |
Оценка популяции |
Подпрограмма оценки строк массива популяции в соответствии с выбранной целевой функцией. |
Метод управляющего класса, оценивающий популяцию в соответствии с выбранной целевой функцией. |
Приспособленность популяции |
Одномерный массив, в котором i-й элемент соответствует приспособленности i-й особи. |
Свойство в классе «особь», характеризующее приспособленность данной особи |
Особи, выбранные для скрещивания |
Двумерный массив, строки которого соответствуют хромосомам особей, выбранным для скрещивания. |
Объект класса «популяция», содержащий объекты класса «особь», соответствующие выбранным особям |
Реализация скрещивания, мутации, формирования нового поколения |
Подпрограммы, обрабатывающие элементы массива, представляющего популяцию особей, а также популяцию особей, выбранных для скрещивания. |
Методы управляющего класса, работающие с основной популяцией и выборкой особей для скрещивания. |
Список литературы
Holland J. H., Adaptation in Neural and Artificial Systems, University of Michigan Press: Ann Arbor, 1975.
Whitley D. L., Genetic Algorithms and Evolutionary Computing, Van Nostrand's Scientific Encyclopedia, Princeton: New Jersey, 2002.
Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И. Д. Рудинского – М.: Горячая линия – Телеком, 2006. – 452 с.
В. В. Емельянов, В. В. Курейчик, В. М. Курейчик Теория и практика эволюционного моделирования. – М.: ФИЗМАТЛИТ, 2003. – 432 c.
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.
Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. – СПб: Питер, 2001. – 368 с.