Настройка параметров генетического алгоритма

Результат работы генетического алгоритма сильно зависит от того, каким образом настроены его параметры. Основными параметрами ГА являются:

– длительность эволюции (количество поколений);

– размер популяции;

– интенсивность (давление) селекции;

– тип оператора кроссинговера;

– вероятность кроссинговера Р_С;

– тип оператора мутации;

– вероятность мутации Р_М;

– величина разрыва поколений Т.

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

1. Исследование пространства поиска (exploration).

2. Использование найденных «хороших» решений (exploitation).

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

Игнорирование найденных решений может привести к тому, что работа ГА будет напоминать случайный поиск, что также отрицательно сказывается на эффективности поиска и качестве получаемых решений.

Основная цель в настройке параметров ГА и, одновременно, необходимое условие для стабильного получения хороших результатов работы алгоритма – это достижение баланса между исследованием пространства поиска и использованием найденных решений.

Взаимосвязь между параметрами генетического алгоритма, а также влияние параметров на эволюционный процесс имеют сложный характер. На рис. 5.7 схематично изображено влияние изменения некоторых параметров ГА на характеристики эволюционного поиска.

Рис. 5.7. Влияние параметров ГА на характеристики эволюционного поиска

Неправильная настройка параметров может стать причиной различных проблем в работе ГА. Краткий список часто встречающихся проблем и возможные пути их исправления приведены в табл. 5.1.