Алгоритм работы ГА

Работа ГА представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий останова.

На каждом поколении ГА реализуется отбор пропорционально приспособленности, кроссовер и мутация.

НАЧАЛО /* генетический алгоритм */

Создать начальную популяцию

Оценить приспособленность каждой особи

останов = FALSE

ПОКА НЕ останов ВЫПОЛНЯТЬ

НАЧАЛО /* создать популяцию нового поколения */

ПОВТОРИТЬ (размер_популяции/2) РАЗ

НАЧАЛО /* цикл воспроизводства */

Выбрать две особи с высокой приспособленностью из

предыдущего поколения

Скрестить выбранные особи и получить двух потомков

Оценить приспособленности потомков

Поместить потомков в новое поколение

КОНЕЦ

ЕСЛИ популяция сошлась, ТО останов = TRUE

КОНЕЦ

КОНЕЦ

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

Ниже предлагается способ реализации различных компонентов генетического алгоритма при использовании обоих подходов.

 

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

 

Приведенный в табл. способ реализации генетического алгоритма не является эталонным и, вполне возможно, далек от идеала. Данные в табл. могут служить в качестве «опорных» для конкретной реализации генетического алгоритма.