НАХОЖДЕНИЕ НАИЛУЧШИХ ВЕРОЯТНОСТЕЙ МУТАЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ОПТИМИЗАЦИИ ПРОСТЫХ МНОГОЭКСТРЕМАЛЬНЫХ ФУНКЦИЙ



Рассматривается важность правильного нахождения наилучших вероятностей мутации, используемых в генетическом алгоритме оптимизации простых многоэкстремальных функций.

Ключевые слова: генетические алгоритмы, оптимизация многоэкстремальных функций, задачи оптимизации, вероятность мутации.

Генетические алгоритмы являются алгоритмами поиска, основанными на принципах естественного отбора и генетики. Они представляют собой подмножество крупного множества алгоритмов, известного как эволюционные алгоритмы. Генетические алгоритмы обычно используются для решения NP-полных задач оптимизации. По своей природе, генетические алгоритмы являются достаточно рандомизированными, но они гораздо лучше справляются с поставленными задачами, чем рандомизированный локальный поиск. Одним из наиболее важных параметров генетического алгоритма является вероятность мутации, однако на данный момент в научной среде не существует единого мнения относительно ее оптимального значения .

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

Мутация играет важную роль в поддержании разнообразия в популяции особей генетического алгоритма. Она участвует в исследовании пространства поиска возможных решений поставленной задачи. Корректное значение вероятности мутации является одним из основных условий сходимости генетического алгоритма.

В ходе серий проведенных экспериментов были смоделированы несколько стандартных ситуаций. Параметры генетического алгоритмы задавались следующим образом: вероятность скрещивания – 90%, максимальное число поколений – 20, число особей в каждой популяции – 8.  Значение вероятности мутации варьировалось от 1 до 25 процентов, причем для каждой отдельно взятой серии экспериментов значение вероятности мутации оставалось неизменным. Для повышения точности результатов исследования для каждого набора параметров алгоритма было проведено по 10 экспериментов.

Общее число экспериментов составило 40; поэтапное увеличение значения вероятности мутации генетического алгоритма в каждом последующем эксперименте происходило по следующей схеме: 1%, 5%, 10% и 25%. Значения вероятности мутации выше 25% не были рассмотрены, так как в таком случае алгоритм теряет свою эффективность и сводится к простому случайному поиску.

Полученные числовые результаты экспериментов представлены в таблице 1. В большинстве проведенных экспериментов значение функции полезности равнялось 4, что соответствует значениям глобальных экстремумов исследуемых функций. Данное значение было принято за 100% полезности и использовано для визуализации полученных результатов (рис. 1).