Preview

Математика и математическое моделирование

Расширенный поиск

Исследование эффективности популяционного алгоритма лиги чемпионов для задачи глобальной оптимизации

https://doi.org/10.24108/mathm.0220.0000217

Полный текст:

Аннотация

Целью статьи  является исследование эффективности нового алгоритма лиги чемпионов (League Championship Algorithm, LCA) на основе сравнения с эффективностью алгоритма роя частиц (Particle Swarm optimization, PSO).

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

Статья содержит подробное описание алгоритма лиги чемпионов, которое включает в себя схематичное представление алгоритма, а также формализованное изложение всех основных его этапов.

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

Дано краткое описание модифицированного алгоритма роя частиц. Представлены значения всех свободных параметров алгоритма, а также модификации алгоритма, отличающие его от классической версии.

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

Вычислительные эксперименты выполнены с использованием сферической функции, а также функций Розенброка, Растригина и Экли. Результаты экспериментов сведены в таблицы, а также проиллюстрированы рисунками. Зксперименты проведены для размерности вектора варьируемых параметров равной 2, 4, 8, 16, 32, 64.

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

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

Об авторах

Д. О. Захаров
МГТУ им. Н.Э. Баумана, Москва
Россия

Захаров Дмитрий Олегович

Кафедра САПР (РК-6)



А. П. Карпенко
МГТУ им. Н.Э. Баумана, Москва
Россия

Карпенко Анатолий Павлович

Кафедра САПР (РК-6), зав. кафедры.



Список литературы

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).


Для цитирования:


Захаров Д.О., Карпенко А.П. Исследование эффективности популяционного алгоритма лиги чемпионов для задачи глобальной оптимизации. Математика и математическое моделирование. 2020;(2):25-45. https://doi.org/10.24108/mathm.0220.0000217

For citation:


Zaharov D.O., Karpenko A.P. Study of League Championship Algorithm Efficiency for Global Optimization Problem. Mathematics and Mathematical Modeling. 2020;(2):25-45. (In Russ.) https://doi.org/10.24108/mathm.0220.0000217

Просмотров: 4428


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2412-5911 (Online)