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

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

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


 
Свежее новое
  • Четверть населения Финляндии, будет обучена работе с роботами и нейросетями.
  • Финляндии предстоит расти и расти, перед тем, как она сможет выйти на мировой рынок с технологиями искусственного интеллекта и все же, это не мешает
  • Как искусственный интеллект передает информацию от людей, потерявших способность говорить?
  • Несколько групп ученых смогли преобразовать команды головного мозга в речь с помощью компьютера-синтезатора. Для того, чтобы это сделать, они
  • К 2025 году, роботы строители, могут составить 10 процентов рабочей силы Японии.
  • Япония является одной из стран, в которой автоматизация процесса строительства, происходит очень медленно. Роботы на практике показывают лишь то, что
  • Интуитивный Алгоритм Технологической Сингулярности на основе Сильного Искусственного Интеллекта «Smart-MES»
  • Технологическая Сингулярность означает такое быстрое развитие прогресса, связанное с созданием сообщества Сильных Искусственных Интеллектов, когда
  • Видеокамеры научились различать телефоны в руках автомобилистов
  • Совсем недавно, в Москве, Сергей Собянин сделал официальное заявление, что с 2019 года в Москве заработают камеры, которые будут отслеживать опасных
Последние комментарии
Каким был первый робот в мире? Происхождение слова "Робот"
Восхищения нет предела делу ваших рук и идей. Хочется склонить голову перед вашим трудом, хотя твердо придерживаюсь Библии (не поклоняться идолам)
Как работает Любовь? Квантовая связь нейронной активности Людей
Я думаю, когда начнется квантовое взаимодействие мржду человеком и ИИ это и будет началом конца.
Как работает Любовь? Квантовая связь нейронной активности Людей
Как вы считаете, возможно ли образование квантовых взаимодействий между человеком и ИИ? 
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
А почему бы сразу СИИ не запустить в другую галактику, может там нет коррупции, воровства, плебейства и прочей муры, которая не только мешает
Искусственный Интеллект. Концепция развития и внедрения Искусственного Интеллекта (Искусственной Аналитики)
Согласен. проблема ИИ не в наборе задач. Главная проблема - познание процесса мышления как феномена физиологии головного мозга человека.
Мы в социальных сетях
Статистика
0  
Всего статей 1545
0  
Всего комментариев 76
0  
Пользователей 69