Генетические операторы

Те же механизмы передачи наследственности, которые действуют в при­роде, в упрощенной форме положены в основу того, что мы назы­ваем генетическими операторами в теории генетических алгоритмов. Таких операторов три (рис. …):

1. Кроссовер приводит к тому, что хромо­сома потомка включает два фрагмента, один из которых принадлежал ра­нее, условно говоря, отцовской хромосоме, а другой — материнской.

2. Мутация вызывает замену существующего со­стояния отдельного гена в хромосоме на противоположное (единицы — на ноль и наоборот).

3. Инверсия приводит к нарушению порядка сле­дования фрагментов хромосом у потомка по сравнению с родительской хромосомой (фрагменты меняются местами).

Рис. …. Триада генетических операторов

У всех трех операторов место приложения (помеченное на рис… закрашенным треугольником) выбирается случайно.

Процедурно работу одной из его быстро сходящихся версий ГА (репродуктивный план Холланда) можно проиллюстрировать блок-схемой, представленной на рис. …

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

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

Далее оцениваем приспособленность потомка, и, действуя аналогич­ным образом, постепенно заполняем популяцию следующего поколения. Через Μ шагов новое поколение оказывается сформированным. Ясно, что поскольку оно получено от лучших родителей, то его приспособленность должна быть также высокой. Блокируя слабо приспособленным особям возможность стать родителем и дать потомство, мы увеличиваем или, по крайней мере, не уменьшаем среднюю по популя­ции приспособленность.

Работу алгоритма прекращаем при достижении популяцией состояния адаптации, идентифицируемому по существенному сокращению генетического разнообразия в популяции - вырождению популяции. В идеальном случае в популяции остается 1 наиболее приспособленный генотип-родитель, все остальные – его полные близнецы.

Рис. … Репродуктивный план Холланда

К сожалению, невозможно с полной уверенностью утверждать, что найденное решение представляет собой глобальный экстремум. Вырождение популяции является необходи­мым, но не достаточным признаком успешности поиска. Можно лишь повторно запустить алгоритм (возможно, изменив те или иные начальные условия) в надежде получить более удачное решение.

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