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

Суть данного оператора заключается в скрещивании трёх или более (P) родительских хромосом в P–1 случайной позиции с получением дочерних особей, имеющих фрагменты хромосом каждого из P родителей. Из полученных вариантов дочерних особей далее выбирается одна (лучшая или случайным образом с вероятностью, пропорциональной улучшению значения функции приспособленности) для нового поколения популяции. Так, для трёххромосомного кроссовера в позициях 4-го и 6-го генов при заданных родительских хромосомах:

a1 b1 c1 d1 e1 f1 g1 h1
a2 b2 c2 d2 e2 f2 g2 h2
a3 b3 c3 d3 e3 f3 g3 h3

возможны 6 дочерних хромосом:

a1 b1 c1 d2 e2 f3 g3 h3
a1 b1 c1 d3 e3 f2 g2 h2
a2 b2 c2 d1 e1 f3 g3 h3
a2 b2 c2 d3 e3 f1 g1 h1
a3 b3 c3 d1 e1 f2 g2 h2
a3 b3 c3 d2 e2 f1 g1 h1

Зависимость количества возможных дочерних особей D от числа родительских определяется формулой: D = P!

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

Было проведено исследование скорости и качества поиска оптимального значения функций при решении задач многомерной оптимизации со следующими параметрами генетического алгоритма: размер популяции 100 особей, продолжительность эволюционного процесса 1000 поколений, шаг изменения каждой переменной 0,001, интервал изменения переменных [–5; 5]. В ходе исследования варьировались вид оператора мутации (простая однопозиционная или многопозиционная – в нескольких случайно выбранных позициях), вероятность применения выбранного вида мутации в текущем поколении, соотношение простого и многохромосомного кроссовера. В качестве многохромосомного кроссовера использовался только кроссовер трёх родительских особей с полным анализом приспособленностей возможных потомков.

Тестовые функции Растригина:

и Розенброка:

,

включали 5 оптимизируемых переменных. Как известно, функция Растригина имеет глобальный минимум, равный 0, при , а функция Розенброка – глобальный минимум, равный 0, при

Результаты тестирования алгоритма с различными параметрами настройки приведены в таблице. Для каждого вычислительного эксперимента было выполнено от 5 до 12 повторяющихся эволюционных процессов при различных начальных популяциях, сгенерированных случайным образом. Наибольшее количество повторений соответствует экспериментам №№ 4, 8 и 9, показавшим наилучший результат. Значения тестовых функций, полученные в одном эксперименте, усреднялись следующим образом: одно или два максимальных и минимальных значения отбрасывались, а для оставшихся (от 3 до 8 значений) рассчитывалось среднее арифметическое.

 Номер вычислительного эксперимента
1 2 3 4 5 6 7 8 9
Вид мутации:
1 – простая однопозиционная;
2 – многопозиционная
1 1 1 2 2 2 2
Вероятность мутации, % 0 20 20 20 20 10 25 0 20
Соотношение кроссоверов: обычный / трёххромосомный, % 100 / 0 100 / 0 50 / 50 0 / 100 100 / 0 100 / 0 100 / 0 100 / 0 100 / 0
Оптимальное значение функции Растригина 27,4 26,8 5,8 2,7 23,6 30,7 26,6 1,7 1,3
Оптимальное значение функции Розенброка 516,4 327,9 10,4 2,4 860,1 538,9 1015 3,4 2,9

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

Интересным представляется тот факт, что наилучшие варианты настройки генетического алгоритма для двух тестовых функций отличаются между собой: для функции Растригина это – 100 % трёххромосомного кроссовера и 20 % многопозиционной мутации, а для функции Розенброка – 100 % трёххромосомного кроссовера и 20 % простой однопозиционной мутации.

Возросший объём вычислений, необходимых для выполнения трёххромосомного кроссовера, выразился в уменьшении количества шагов эволюции в 1,75 раза по сравнению с настройками, использовавшими только простой кроссовер. Тем не менее, не только точность, но и скорость нахождения оптимального решения при использовании трёххромосомного кроссовера значительно повысилась. Так, для настроек, принятых в вычислительных экспериментах № 5 (с простым кроссовером) и № 9 (с трёххромосомным кроссовером), за одно и то же время работы алгоритма, равное 4 с, получены средние значения функции Растригина соответственно 32,9 и 6,6.

Полученные результаты доказывают высокую эффективность работы генетических алгоритмов, использующих многохромосомный кроссовер, и, как следствие, целесообразность его использования в репродуктивных планах.

По материалам публикации:
Дударов С. П. Генетический алгоритм с оператором многохромосомного кроссовера/ С. П. Дударов, Ю. А. Карибова. – Математические методы в технике и технологиях – ММТТ-25: сб. трудов XXV Междунар. науч. конф., секции 1, 2. – Волгоград: Волгогр. гос. техн. ун-т, 2012; Харьков: Национ. техн. ун-т «ХПИ», 2012. – с. 132–134.