2014-02-02
405
Работа ГА представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий останова.
На каждом поколении ГА реализуется отбор пропорционально приспособленности, кроссовер и мутация.
НАЧАЛО /* генетический алгоритм */
Создать начальную популяцию
Оценить приспособленность каждой особи
останов = FALSE
ПОКА НЕ останов ВЫПОЛНЯТЬ
НАЧАЛО /* создать популяцию нового поколения */
ПОВТОРИТЬ (размер_популяции/2) РАЗ
НАЧАЛО /* цикл воспроизводства */
Выбрать две особи с высокой приспособленностью из
предыдущего поколения
Скрестить выбранные особи и получить двух потомков
Оценить приспособленности потомков
Поместить потомков в новое поколение
КОНЕЦ
ЕСЛИ популяция сошлась, ТО останов = TRUE
КОНЕЦ
КОНЕЦ
Поскольку генетические алгоритмы представляют собой достаточно универсальный подход к решению экстремальных задач, то выбор языка программирования не играет большой роли. Саму программу можно писать, используя как объектноориентированный подход, так и структурный.
|
|
|
Ниже предлагается способ реализации различных компонентов генетического алгоритма при использовании обоих подходов.
| Компонент генетического алгоритма | Структурный подход | Объектно-ориентированный подход |
| Особь | Одномерный массив для записи значений генов. Размерность массива совпадает с количеством генов у одной особи (количество генов равно числу настраиваемых параметров) | Класс «Особь», содержащий массив генов. |
| Популяция | Двумерный массив, в котором i -я строка содержит гены i -й особи. | Отдельный класс «Популяция», содержащий одномерный массив объектов класса, представляющего особь. |
| Оценивание популяции | Подпрограмма оценки строк массива популяции в соответствии с выбранной целевой функцией. | Метод управляющего класса, оценивающий популяцию в соответствии с выбранной целевой функцией. |
| Приспособленность популяции | Одномерный массив, в котором i -й элемент соответствует приспособленности i -й особи. | Одномерный массив со значениями ошибок особей, входящий в управляющий класс. |
| Особи, вы бранные для скрещивания | Двумерный массив, строки которого соответствуют хромосомам особей, выбранным для скрещивания. | Объект класса «Популяция», содержащий объекты класса «Особь», соответствующие выбранным особям |
| Реализация скрещивания, мутации, формирования нового поколения. | Подпрограммы, обрабатывающие элементы массива, представляющего популяцию особей, а также популяцию особей, выбранных для скрещивания. | Методы управляющего класса, работающие с основной популяцией и популяцией особей для скрещивания. |
Приведенный в табл. способ реализации генетического алгоритма не является эталонным и, вполне возможно, далек от идеала. Данные в табл. могут служить в качестве «опорных» для конкретной реализации генетического алгоритма.
