Генетический алгоритм

Идея генетических алгоритмов предложена Джоном Холландом в 60-х годах, а результаты первых исследований обобщены в его монографии «Адаптация в природных и искусственных системах» [24], а также в диссертации его аспиранта Кеннета Де Йонга [32].

Как уже говорилось выше, ГА используют для работы эволюционные принципы наследственности, изменчивости и естественного отбора. Общая схема ГА представлена на рис. 5.1 [34].

Рис. 5.1. Общая схема генетического алгоритма

Генетический алгоритм работает с популяцией особей, в хромосоме (генотип) каждой из которых закодировано возможное решение задачи (фенотип). В начале работы алгоритма популяция формируется случайным образом (блок «Формирование начальной популяции» на рис. 5.1). Для того чтобы оценить качество закодированных решений используют функцию приспособленности, которая необходима для вычисления приспособленности каждой особи (блок «Оценивание популяции»). По результатам оценивания особей наиболее приспособленные из них выбираются (блок «Селекция») для скрещивания. В результате скрещивания выбранных особей посредством применения генетического оператора кроссинговера создается потомство, генетическая информация которого формируется в результате обмена хромосомной информацией между родительскими особями (блок «Скрещивание»). Созданные потомки формируют новую популяцию, причем часть потомков мутирует (используется генетический оператор мутации), что выражается в случайном изменении их генотипов (блок «Мутация»). Этап, включающий последовательность «Оценивание популяции» – «Селекция» – «Скрещивание» – «Мутация», называется поколением. Эволюция популяции состоит из последовательности таких поколений.

Длительность эволюции может определяться следующими факторами:

- нахождение решения в результате эволюционного поиска;

- ограниченность количества поколений;

- ограниченность количества вычислений функции приспособленности (целевой функции);

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