В. А. Топчий, А. В. Еремеев
Обобщённая мутация с тяжёлыми хвостами для эволюционных алгоритмов.
Аннотация
Генетический алгоритм представляет собой эвристический алгоритм оптимизации, в основу которого положены биологические принципы естественного отбора и изменчивости. Процесс работы алгоритма представляет собой последовательную случайную смену поколений, состоящих из особей – бинарных векторов длины $n$. При формировании следующего поколения часть потомков полностью идентична родителям, а часть изменяется некоторым случайным образом в результате мутации и кроссинговера (скрещивания). Потомки с большим значением целевой функции имеют преимущество при последующем отборе.
Мы изучаем оператор мутации с тяжёлыми хвостами, предложенный Доерром, Ле, Махмарой и Нгуеном (2017) для генетического алгоритма $(1+(\lambda, \lambda))$. Степенное предположение о распределении вероятностей для интенсивности мутаций обобщено на случай правильно меняющихся ограничений на функцию распределения для интенсивности мутаций. В докладе обобщаются верхние границы ожидаемого времени оптимизации (попадания в оптимум), полученные Антиповым, Буздаловым и Доерром (2022). В частности, показано, что на классе целевых функций OneMax (значение функции равно сумме компонент решения) ожидаемое время оптимизации для генетического алгоритма $(1+(\lambda, \lambda))$ с обобщенным вариантом мутации по-прежнему линейно по размерности задачи. Известно, что это асимптотически быстрее, чем то, что может быть получено при любой фиксированной интенсивности мутаций.
