УДК 004.023
ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ ТУРНИРНОГО ВЫТЕСНЕНИЯ
С ГАУССОВОЙ МУТАЦИЕЙ
Аннотация. Для решения задач многоэкстремальной оптимизации предложен новый генетический алгоритм образования ниш — генетический алгоритм турнирного вытеснения с гауссовой мутацией. Проведенный сравнительный анализ предложенного алгоритма с другими алгоритмами вытеснения и с параллельным алгоритмом поиска с восхождением к вершинам показал преимущества разработанного алгоритма во многих случаях. Введен критерий оценки степени разброса элементов популяции. Показано, что вычисление этого критерия является целесообразным для оценки качества работы алгоритмов поиска глобальных и локальных максимумов.
Ключевые слова: задача многоэкстремальной оптимизации, генетические алгоритмы образования ниш, алгоритмы вытеснения, параллельный алгоритм поиска с восхождением к вершинам, доля ложных пиков.
ПОЛНЫЙ ТЕКСТ
Шило Володимир Петрович,
доктор фіз.-мат. наук, професор, провідний науковий співробітник Інституту кібернетики
ім. В.М. Глушкова НАН України, Київ,
v.shylo@gmail.com
Глибовець Микола Миколайович,
доктор фіз.-мат. наук, професор, декан Національного університету «Києво-Могилянська академія», Київ,
glib@ukma.kiev.ua
Гулаєва Наталія Михайлівна,
кандидат фіз.-мат. наук, доцент кафедри Національного університету «Києво-Могилянська академія», Київ,
ngulayeva@yahoo.com
Нікіщіхіна Катерина Вячеславівна,
магістр факультету інформатики Національного університету «Києво-Могилянська академія», Київ,
kateryna.nikishchikhina@gmail.com
СПИСОК ЛИТЕРАТУРЫ
- Glybovets M.M., Gulayeva N.M. Evolutionary multimodal optimization. In: Optimization Methods and Applications: in Honor of Ivan V. Sergienko’s 80th Birthday. Butenko S., Pardalos P.M., Shylo V. (Eds.). Springer International Publishing, 2017. P. 129–173.
- Preuss M. Multimodal optimization by means of evolutionary algorithms. Berlin: Springer, 2015. 175 p.
- Reeves C. (ed.). Modern heuristic techniques for combinatorial problems. New York: Halsted Press, 1993.
- Aickelin U. An indirect genetic algorithm for set covering problems. J. of the Oper. Res. Society. 2002. Vol. 53. P. 1118–1126.
- Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы решения, исследования. Киев: Наук. думка, 2003. 264 с.
- Глибовець М.М., Гулаєва Н.М. Еволюційні алгоритми. Підручник. Київ: НаУКМА, 2013. 828 с.
- Mahfoud S. Niching method for genetic algorithms. Ph.D. thesis. Urbana, 1995. 251 p.
- Singh G., Deb K. Comparison of multi-modal optimization algorithms based on evolutionary algorithms. Proc. 8th Ann. Conf. on Genetic and Evolutionary Computation (GECCO’06) (July 8–12, 2006, Seattle, Washington, USA). Seattle, 2006. P. 1305–1312.
- Friedrich T., Oliveto P.S., Sudholt D., Witt C. Analysis of diversity-preserving nechanisms for global exploration. Evolutionary Computation. 2009. Vol. 17, N 4. P. 455–476. https://doi.org/ 10.1162/ evco.2009.17.4.17401.
- Osuna E. C., Sudholt D. Runtime analysis of crowding mechanisms for multimodal optimization. IEEE Trans. Evol. Comp. 2019. http://doi.org/10.1109/TEVC.2019.2914606
- Mengshoel O., Goldberg D. Probabilistic crowding: deterministic crowding with probabilistic replacement. Proc. the Genetic and Evolutionary Computation Conference (GECCO-99) (13–17 July, 1999, Orlando, FL, USA). Orlando, 1999. P. 409–416.