Обобщенная мутация с тяжелыми хвостами для эволюционных алгоритмов

Аннотация

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