Генетический поиск может прекратиться вдали от искомого экстремума. Причиной этого могут быть вырождение популяции (стагнация) или застревание в локальном экстремуме.
Для предотвращения стагнации обычно используют макромутации и/или увеличение вероятности мутации. Однако по мере приближения к малым окрестностям экстремума (а именно тогда и наступает стагнация) обычные макромутации становятся малоэффективными. Это связано с тем, что функция () мутированной хромосомы оказывается значительно хуже, чем у других хромосом популяции, мутированная хромосома выпадает из числа возможных родителей и, следовательно, не может вывести популяцию из состояния стагнации. Если же попытаться уйти из этого состояния, выполнив мутации большинства генов у всех хромосом, то мутированные хромосомы смогут участвовать в генерации потомков, поскольку полезности всех членов популяции становятся сопоставимыми. Но при столь значительных мутациях теряется накопленный полезный генный материал и поэтому после макромутации поиск практически начинается вновь с исходных позиций.
Для того чтобы макромутации были эффективными, необходимо выполнение двух условий:
1. Сохранение накопленного генного материала;
2. Начальная полезность всех хромосом после макромутаций должна быть соизмеримой.
Совместить эти два противоречивых требования удалось в методе, названном циклическим генетическим методом (ЦГМ). Циклический генетический метод создан в рамках смешанного эволюционного метода. Его сущность поясняет рис. 1.
Рис. 1.  Макромутации в циклическом генетическом методе
В соответствии с циклическим методом каждая хромосома текущего поколения может при макромутациях породить двух потомков. В хромосому первого потомка переписываются нечетные фрагменты, а гены четных фрагментов получают случайным образом сгенерированные аллели. В хромосоме второго потомка сохраняются фрагменты родителя с четными номерами, а нечетные фрагменты заполняются случайными значениями.
Макромутации повторяются периодически через W смен поколений, называемых циклами, где W – число смен поколений, после которых вероятно появление признаков стагнации. Поскольку за счет 50% заполнения генов случайными значениями число хромосом после макромутаций увеличивается вдвое, в операции макромутации участвует и далее используется лишь половина хромосом предыдущего поколения. В эту половину целесообразно включать лучшие особи.
После каждой макромутации целевая функция резко ухудшается, но за счет сохранения полезных шаблонов в новом цикле наблюдается ее ускоренное улучшение, причем велика вероятность, что это улучшение приведет траекторию поиска в меньшую окрестность экстремума (или на более удачный уровень стагнации), чем это было в предыдущем цикле.
Рис. 2.  Результаты применения ММЕМ и ЦГМ
Для иллюстрации повышения эффективности циклического генетического метода (ЦГМ) были выполнены эксперименты с тестовой задачей синтеза расписаний со следующими исходными данными: число работ 105, число стадий 4, число машин на стадиях {4, 4, 4, 3}. На рис. 2 представлены результаты расчетов — зависимости целевой функции () от номера поколения при применении простого смешанного эволюционного метода (ММЕМ) и ЦГМ с макромутациями через 120 поколений. Как видно на рис. 2, на первых четырех циклах происходило улучшение целевой функции. Причем стагнация в случае применения ММЕМ наступила на уровне ()=21751, а в случае ЦГМ на втором, третьем и четвертом циклах достигнуты значения (), равные 21734, 21716 и 21676.
Список литературы
1. Норенков И.П. Исследование эффективности генетического метода с фрагментным кроссовером // Информационные технологии, 2008, N 6, стр. 26-29.