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

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

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


Если у вас есть статья, заметка или обзор, которыми вы хотите поделиться с аудиторией нашего сайта, присылайте информацию на: neuronus.com@yandex.ru.
Гость, оставишь комментарий?
Имя:*
E-Mail:


Свежее новое
  • Китай опередил Америку по количеству боевых кораблей
  • Согласно информации Popular Mechanics, эпоха тотального военного доминирования Штатов в Мировом океане близка к завершению.
  • Японцы создали самый быстрый поезд на планете, который может развивать скорость до 400 км/ч
  • Конструкторы Страны восходящего солнца усиленно трудятся над завершением и доработкой нового поезда, получившего имя ALFA-X. По заверению японского
  • Армия США «воскресила» стратегический бомбардировщик B-52 времен холодной войны
  • Wise Guy — это имя самолета, которое до недавних пор упоминалось лишь в прошедшем времени. Однако ситуации изменилась, и древние бомбардировщики
  • В США разработали концепт самого быстрого самолета в мире
  • Пассажирское судно разрабатывается конструкторами компании Hermeus. Судно должно мгновенно развивать высокую скорость. Всего за полтора часа можно
  • Учёному из Бристоля удалось расшифровать загадочный манускрипт Войнича
  • Джерард Чешир, академик университета в Бристоле (Великобритания), заявил, что выполнил расшифровку манускрипта Войнича, в течение свыше ста лет
Последние комментарии
Таинственная планета Нибиру: может ли она столкнуться с Землей
Вы видите в поле суслика? Нет? А он там есть. Не всё что мы не видим значит нету. Есть параллельное время -28 измерений. У каждого свои частоты
Вы уверены, что наш мир существует? Солипсизм, или игры разума за гранью реальности
это ограниченный взгляд на окружающую действительность.Есть доказательства .что обьективной реальности не существует.Реальность разная для каждого
6 самых необъяснимых и удивительных объектов во Вселенной
Вот когда ты полетишь на Марс на свою дачу, и в тебя врежеться камушек размером с крупного слоника, вот тогда ты вспомнишь, что в космосе есть
Что круче: сверхзвуковой бомбардировщик ВВС США "XB-70 Valkyrie" или созданный в СССР МиГ-25
Правильнее сравнивать машины-одноклассники. А ведь у нас был проект сверхзвукового бомбардировщика. Его называли "сотка". Процент новизны в
Таинственная планета Нибиру: может ли она столкнуться с Землей
Здравствуйте . Спасибо ,что вы успокаиваете. Я знаю ,что эта планета выдумка ,но все равно спасибо. 
Мы в социальных сетях
Статистика
1  
Всего статей 1919
10  
Всего комментариев 304
0  
Пользователей 113