Математика и математическое моделирование. 2020; : 25-45
Исследование эффективности популяционного алгоритма лиги чемпионов для задачи глобальной оптимизации
https://doi.org/10.24108/mathm.0220.0000217Аннотация
Целью статьи является исследование эффективности нового алгоритма лиги чемпионов (League Championship Algorithm, LCA) на основе сравнения с эффективностью алгоритма роя частиц (Particle Swarm optimization, PSO).
Представлено краткое описание терминов, использующихся в алгоритме лиги чемпионов, изложены основные правила алгоритма, на основе которых строится итерационный процесс решения задачи глобальной оптимизации.
Статья содержит подробное описание алгоритма лиги чемпионов, которое включает в себя схематичное представление алгоритма, а также формализованное изложение всех основных его этапов.
Приведено исчерпывающее описание разработанного программного обеспечения, которое реализует алгоритм лиги чемпионов для решения задач глобальной оптимизации.
Дано краткое описание модифицированного алгоритма роя частиц. Представлены значения всех свободных параметров алгоритма, а также модификации алгоритма, отличающие его от классической версии.
Основной частью работы является представление результатов большого числа вычислительных экспериментов, которые проводились с использованием двух указанных алгоритмов. Представлено описание всех критериев эффективности, на основе которых проводилась оценка эффективности алгоритмов.
Вычислительные эксперименты выполнены с использованием сферической функции, а также функций Розенброка, Растригина и Экли. Результаты экспериментов сведены в таблицы, а также проиллюстрированы рисунками. Зксперименты проведены для размерности вектора варьируемых параметров равной 2, 4, 8, 16, 32, 64.
Выполнен анализ результатов вычислительных экспериментов, который включает в себя полную оценку эффективности алгоритма лиги чемпионов, а также дает ответ на вопрос о целесообразности проведения последующих работ, направленных на развитие алгоритма.
Показано, что представленный в работе алгоритм лиги чемпионов имеет высокий потенциал развития и требует проведения дальнейших работ по его изучению.
Список литературы
1. Bo Xing, Wen-Jing Gao. Innovative computational intelligence: a rough guide to 134 clever algorithms. Cham: Springer, 2014. 451 p. DOI: 10.1007/978-3-319-03404-1
2. Blum C., Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison // ACM Computing Surveys. 2003. Vol. 35. No. 3. Pp. 268–308. DOI: 10.1145/937503.937505
3. Engelbrecht A.P. Computational intelligence: an introduction. 2nd ed. Chichester; Hoboken: Wiley, 2007. 597 p.
4. Карпенко А.П. Современные алгоритмы поисковой оптимизации: алгоритмы, вдохновленные природой. М.: МГТУ им. Н.Э. Баумана, 2017. 448 с.
5. Kashan A.H. League championship algorithm: A new algorithm for numerical function optimization // 2009 intern. conf. of soft computing and pattern recognition (Malacca, Malaysia, December 4-7, 2009): Proc. N.Y.: IEEE, 2010. Pp. 43-48. DOI: 10.1109/SoCPaR.2009.21
6. Kashan A.H., Karimi B. A new algorithm for constrained optimization inspired by the sport league championships // IEEE congress on evolutionary computation (Barcelona, Spain, July 18-23, 2010): Proc. N.Y.: IEEE, 2010. Pp. 487-494. DOI: 10.1109/CEC.2010.5586364
7. Kashan A.H. An efficient algorithm for constrained global optimization and application to mechanical engineering design: League championship algorithm (LCA) // Computer-Aided Design. 2011. Vol. 43. No. 12. Pp. 1769-1792. DOI: 10.1016/j.cad.2011.07.003
8. Воробьёва Е.Ю., Карпенко А.П., Селиверстов Е.Ю. Ко-гибридизация алгоритмов роя частиц // Наука и образование. МГТУ им. Н.Э. Баумана: электрон. журн. 2012. № 4. С. 28. Режим доступа: http://technomag.edu.ru/doc/355792.html (дата обращения 16.06.2020).
9. Chattopadhyay S., Murthy C.A., Sankar K. Pal. Fitting truncated geometric distributions in large scale real world networks // Theoretical Computer Science. 2014. Vol. 551. Pp. 22-38. DOI: 10.1016/j.tcs.2014.05.003
10. Карпенко А. П., Селиверстов Е.Ю. Обзор методов роя частиц для задачи глобальной оптимизации (particle swarm optimization) // Наука и образование. МГТУ им. Н.Э. Баумана: электрон. журн. 2009. № 3. С. 2-26. DOI: 10.7463/00309.0116072
11. Ершов Н.М. Неоднородные клеточные генетические алгоритмы // Компьютерные исследования и моделирование. 2015. Т. 7. № 3. С. 775–780. DOI: 10.20537/2076-7633-2015-7-3-775-780
12. Ямченко Ю.В., Андрусенко А.С. Исследование эффективности алгоритмов непрерывной поисковой оптимизации методом роя частиц // Политехн. молодежный журнал. 2016. № 1. С. 2-16. DOI: 10.18698/2541-8009-2016-1-7
13. Карпенко А. П., Свианадзе З.О. Метод мета-оптимизации поисковых алгоритмов оптимизации // Наука и образование. МГТУ им. Н.Э. Баумана: электрон. журн. 2011. № 1. С. 3-36. DOI: 10.7463/0111.0164546
14. Остроух Е.Н., Требухин А.В., Чернышев Ю.А., Панасенко П.А. Разработка и анализ гибридного алгоритма решения нелинейных задач оптимизации // Современные наукоемкие технологии. 2018. № 10. С. 87-91. Режим доступа: http://top-technologies.ru/ru/article/view?id=37200 (дата обращения 17.06.2020).
Mathematics and Mathematical Modeling. 2020; : 25-45
Study of League Championship Algorithm Efficiency for Global Optimization Problem
https://doi.org/10.24108/mathm.0220.0000217Abstract
The article objective is to study a new League Championship Algorithm (LCA) algorithm efficiency by its comparing with the efficiency of the Particle Swarm optimization (PSO) algorithm.
The article presents a brief description of the terms used in the League Championship algorithm, describes the basic rules of the algorithm, on the basis of which the iterative process for solving the global optimization problem is built.
Gives a detailed description of the League Championship algorithm, which comprises a flowchart of the algorithm, as well as a formalization of all its main steps.
Depicts an exhaustive description of the software developed to implement the League Championship algorithm to solve global optimization problems.
Briefly describes the modified particle swarm algorithm. Presents the values of all free parameters of the algorithm and the algorithm modifications, which make it different from the classical version, as well.
The main part of the article shows the results of a great deal of computational experiments using two abovementioned algorithms. All the performance criteria, used for assessment of the algorithms efficiency, are given.
Computational experiments were performed using the spherical function, as well as the Rosenbrock, Rastrigin, and Ackley functions. The results of the experiments are summarized in Tables, and also illustrated in Figures. Experiments were performed for the vector dimension of the variable parameters that is equal to 2, 4, 8, 16, 32, and 64.
An analysis of the results of computational experiments involves a full assessment of the efficiency of the League Championship algorithm, and also provides an answer about expediency for further algorithm development.
It is shown that the League Championship algorithm presented in the article has a high development potential and needs further work for its study.
References
1. Bo Xing, Wen-Jing Gao. Innovative computational intelligence: a rough guide to 134 clever algorithms. Cham: Springer, 2014. 451 p. DOI: 10.1007/978-3-319-03404-1
2. Blum C., Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison // ACM Computing Surveys. 2003. Vol. 35. No. 3. Pp. 268–308. DOI: 10.1145/937503.937505
3. Engelbrecht A.P. Computational intelligence: an introduction. 2nd ed. Chichester; Hoboken: Wiley, 2007. 597 p.
4. Karpenko A.P. Sovremennye algoritmy poiskovoi optimizatsii: algoritmy, vdokhnovlennye prirodoi. M.: MGTU im. N.E. Baumana, 2017. 448 s.
5. Kashan A.H. League championship algorithm: A new algorithm for numerical function optimization // 2009 intern. conf. of soft computing and pattern recognition (Malacca, Malaysia, December 4-7, 2009): Proc. N.Y.: IEEE, 2010. Pp. 43-48. DOI: 10.1109/SoCPaR.2009.21
6. Kashan A.H., Karimi B. A new algorithm for constrained optimization inspired by the sport league championships // IEEE congress on evolutionary computation (Barcelona, Spain, July 18-23, 2010): Proc. N.Y.: IEEE, 2010. Pp. 487-494. DOI: 10.1109/CEC.2010.5586364
7. Kashan A.H. An efficient algorithm for constrained global optimization and application to mechanical engineering design: League championship algorithm (LCA) // Computer-Aided Design. 2011. Vol. 43. No. 12. Pp. 1769-1792. DOI: 10.1016/j.cad.2011.07.003
8. Vorob'eva E.Yu., Karpenko A.P., Seliverstov E.Yu. Ko-gibridizatsiya algoritmov roya chastits // Nauka i obrazovanie. MGTU im. N.E. Baumana: elektron. zhurn. 2012. № 4. S. 28. Rezhim dostupa: http://technomag.edu.ru/doc/355792.html (data obrashcheniya 16.06.2020).
9. Chattopadhyay S., Murthy C.A., Sankar K. Pal. Fitting truncated geometric distributions in large scale real world networks // Theoretical Computer Science. 2014. Vol. 551. Pp. 22-38. DOI: 10.1016/j.tcs.2014.05.003
10. Karpenko A. P., Seliverstov E.Yu. Obzor metodov roya chastits dlya zadachi global'noi optimizatsii (particle swarm optimization) // Nauka i obrazovanie. MGTU im. N.E. Baumana: elektron. zhurn. 2009. № 3. S. 2-26. DOI: 10.7463/00309.0116072
11. Ershov N.M. Neodnorodnye kletochnye geneticheskie algoritmy // Komp'yuternye issledovaniya i modelirovanie. 2015. T. 7. № 3. S. 775–780. DOI: 10.20537/2076-7633-2015-7-3-775-780
12. Yamchenko Yu.V., Andrusenko A.S. Issledovanie effektivnosti algoritmov nepreryvnoi poiskovoi optimizatsii metodom roya chastits // Politekhn. molodezhnyi zhurnal. 2016. № 1. S. 2-16. DOI: 10.18698/2541-8009-2016-1-7
13. Karpenko A. P., Svianadze Z.O. Metod meta-optimizatsii poiskovykh algoritmov optimizatsii // Nauka i obrazovanie. MGTU im. N.E. Baumana: elektron. zhurn. 2011. № 1. S. 3-36. DOI: 10.7463/0111.0164546
14. Ostroukh E.N., Trebukhin A.V., Chernyshev Yu.A., Panasenko P.A. Razrabotka i analiz gibridnogo algoritma resheniya nelineinykh zadach optimizatsii // Sovremennye naukoemkie tekhnologii. 2018. № 10. S. 87-91. Rezhim dostupa: http://top-technologies.ru/ru/article/view?id=37200 (data obrashcheniya 17.06.2020).
