Повышение эффективности работы генетических алгоритмов за счёт применения оператора многохромосомного кроссовера

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

Суть данного оператора заключается в скрещивании трёх или более (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.


Гость, оставишь комментарий?
Имя:*
E-Mail:


 
Свежее новое
  • Искусственный интеллект, робот Вера, получил 226 млн рублей
  • ФРИИ и Кировский завод вкладывают 226 миллионов рублей в представителя «Сколкова» — компанию «Стафори», создавшую робота-рекрутера. Искусственный
  • В Москве состоялся финал PicsArt AI Hackathon, с самым крупным призовым фондом в истории
  • 30 ноября-2 декабря, в Москве прошел крупнейший хакатон в сфере искусственного интеллекта и компьютерного зрения - PicsArt AI Days. На хакатон было
  • В следующем году в Москве, заработает видеоконтроль, способный обнаружить преступников
  • Как рассказал в своем сообщении Сергей Собянин, новая система будет способна анализировать записи с видеокамер. Быстрая обработка данных позволит
  • В Москве пройдет один из крупнейших хакатонов в мире в сфере искусственного интеллекта
  • PicsArt, ведущая творческая платформа для создания контента и визуализации историй в социальных сетях с более чем 100 миллионами активных
  • Сильный Искусственный Интеллект «Smart-MES» меняет взгляды на Технологическую Сингулярность
  • Учёные полагают, что Технологическая Сингулярность наступит тогда, когда Сильный Искусственный Интеллект будет способен самостоятельно создавать себе
Последние комментарии
Мы в социальных сетях
Статистика
0  
Всего статей 1537
0  
Всего комментариев 69
0  
Пользователей 63