УДК 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.