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

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

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


Свежее новое
  • На B-52 испытали новую гиперзвуковую ракету
  • Б-52 — знаменитый североамериканский бомбардировщик стратегического назначения. Минобороны США планирует оснастить этот самолет новейшим комплексом
  • Две погасшие звезды слились воедино и образовали одну, которая «ожила»
  • Можно ли из двух мертвых тел создать одно живое? Оказывается, это реально, если речь идет о звездах. Астрономы открыли такую редкую звезду, которая
  • Трансгенные грибы могут истреблять разносчиков малярии и других москитов
  • Ученые из США и Буркина-Фасо провели эксперименты, доказавшие эффективность нового средства от москитов. Это генномодифицированный гриб вида
  • Ролик о массовом взлете конвертопланов Osprey и вертолетов CH-53E завораживает
  • По сети гуляет видео, где несколько десятков летательных аппаратов ВМС Соединенных Штатов Америки демонстрируют слаженный взлет. Этот завораживающий
  • Ученые нашли окаменелость, которая сохранила целую стаю рыбок
  • В Америке нашли окаменелость, в которой «законсервирована» целая стайка рыбок. Они застыли в процессе движения, которое, как считают ученые, было
Последние комментарии
Ролик о массовом взлете конвертопланов Osprey и вертолетов CH-53E завораживает
Сколько раз я задавал вопрос про аварийную посадку конвертоплана,но так и не получил ответа. Если у него двигатели не повернутся вверх,то как он
5 необъяснимых для науки загадок
Ваша цитата: "Масса - это сконцентрированная Энергия. Энергия - это не сконцентрированная Масса".   Мой комментарий: Чтобы увеличить (в общем случае
Исследование показало: рождение ребенка старит женщину на 11 лет, а бездетные люди живут меньше
Корреляция в данном случае заключается в том что работает программа размножения. Программа размножения с точки зрения системы не дать умереть виду,
Сколько придется лететь со скоростью света до ближайшей звезды?
Ни какого замедления времени и ни какого сокращения расстояния не происходит при полёте в Космосе со скоростью близкой к скорости света, а тем более
Сколько придется лететь со скоростью света до ближайшей звезды?
Ближайшая звезда к нам, это Солнце. Расстояние порядка 150 млн. км. (Астрономическая единица). Несложные арифметические действия и "вуаля", получаем
Мы в социальных сетях
Статистика
3  
Всего статей 2003
1  
Всего комментариев 333
2  
Пользователей 118