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

Авторы

Михайлин Д. А.^1*, Аллилуева Н. В.^2**, Руденко Э. М.^3***

1. Главный научно-исследовательский испытательный центр робототехники Министерства обороны Российской Федерации, ул. Серегина, 5, Москва, 125167, Россия
2. Научно-производственное предприятие «Радар ммс», ул. Новосельковская, 37 лит. А, Санкт-Петербург, 197375, Россия
3. Военная академия Ракетных войск стратегического назначения имени Петра Великого, ул. Бригадная, 17, Серпухов, Московская обл., 142210, Россия

*e-mail: tau_301@mail.ru
**e-mail: allilueva_nv@radar-mms.com
***e-mail: eduard5529@yandex.ru

Аннотация

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

Ключевые слова:

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

Библиографический список

1. Лебедев Г.Н, Гончаренко В.И., Румакина А.В. Модификация метода ветвей и границ для двумерной маршрутизации координированного полета группы летательных аппаратов // Мехатроника, автоматизация, управление. 2016. Т. 17. № 11. С. 783 – 791.

2. Лебедев Г.Н., Мирзоян Л.А., Ефимов А.В. Нейросетевое планирование групповых действий ЛА при наблюдении заданной группы подвижных объектов // Мехатроника, автоматизация, управление. 2009. № 11. С. 60 – 65.

3. Antonios Tsourdos, Brian A. White, Madhavan Shanmugavel. Cooperative path planning of unmanned aerial vehicles, John Wiley & Sons, 2011, 212 p.

4. Скиена С. Алгоритмы. Руководство по разработке: Пер. с англ. – СПб.: БХВ-Петербург, 2017. – 720 с.

5. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ. – М.: Издательский дом «Вильямс», 2005. – 1290 с.

6. Когабаев Н.Т. Лекции по теории алгоритмов. – Новосибирск: Новосибирский государственный университет, 2009. – 107 с.

7. Лебедев Г.Н. Система логического управления обхода препятствий беспилотным летательным аппаратом при маршрутном полете // Труды МАИ. 2015. № 83. URL: http://trudymai.ru/published.php?ID=61905

8. Lebedev G., Goncharenko V., Mikhaylin D., Rumakina A. Aircraft group coordinated flight route optimization using branch-and-bound procedure in resolving the problem of environmental monitoring // ITM Web of Conferences 10, 01003 (2017), Seminar on Systems Analysis, 2017, vol. 10, pp. 1 – 3.

9. Головко В.А. Нейронные сети: обучение, организация и применение / Под ред. А.И. Галушкина. – М.: ИПРЖР, 2001. Кн. 4. – 256 с.

10. Holland J.H.. Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, USA, 1992, ISBN:0-262-58111-6.

11. Царев Ф.Н. Совместное применение генетического программирования, конечных автоматов и искусственных нейронных сетей для построения системы управления беспилотным летательным аппаратом // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2008. № 8(53). С. 42 – 60.

12. Лебедев Г.Н., Малыгин В.Б., Михайлин Д.А. Постановка и решение задачи оперативной коррекции потоков прилета и вылета воздушных судов в районе аэродрома с помощью генетического алгоритма // Научный вестник МГТУ ГА. 2017. Т. 20. № 4. С. 8 – 17.

13. Аллилуева Н.В., Руденко Э.М. Математический метод расчета целевой функции на графах и решение задачи маршрутизации // Труды МАИ. 2017. № 96. URL: http://trudymai.ru/published.php?ID=85773

14. Zadeh S.M., Powers D., Sammut K. Optimal Route Planning with Prioritized Task Scheduling for AUV Missions Article, University, Adelaide, SA 5042, Australia, 2016. pp. 1 – 8.

15. Genshe Chen, Jose B. Cruz. Genetic algorithm for task allocation in UAV cooperative control // AIAA Conference on Guidance, Navigation, and Control, Austin, Texas, August 2003, pp. 1 – 13.

16. Marjorie A. Darrah, William M. Niland, Brian M. Stolarik, Lance E. Walp. Increased UAV task assignment performance through parallelized genetic algorithms // Proceedings of Infotech@Aerospace Conference, Rohnert Park, CA, 2007, pp. 1 – 10.

17. Marc D. Richards, Darrell Whitley, J. Ross Beveridge. Evolving cooperative strategies for UAV teams, GECCO 2005, Washington, D.C. USA. pp. 1 – 8.

18. Краснов М.Л., Киселев А.И., Макаренко Г.И., Шикин Е.В., Заляпин В.И., Эвнин А.Ю. Вся высшая математика. – М.: КомКнига, 2006. Т.7. – 199 с.

19. He P., Dai S. Stealth Real-time Paths Planning for Heterogeneous UAV Formation Based on Parallel Niche Genetic Algorithm // Journal of Computational Information Systems, 2014, no.10 (15), pp. 6731 – 6740.

20. Wang F., Man Y., Man L. Intelligent Optimization Approach for the k Shortest Paths Problem Based on Genetic Algorithm // 10th International Conference on Natural Computation, 19-21 August, 2014, Xiamen, China, DOI: 10.1109/ICNC.2014.6975838

21. Wagner M., Neumann F. Single- and Multi-Objective Genetic Programming: New Runtime Results for SORTING // IEEE Congress on Evolutionary Computation (CEC), Beijing, China, 2014, pp. 125 – 133.

22. Kim J.W., Kim S.K. Fitness switching genetic algorithm for solving combinatorial optimization problems with rare feasible solutions // The Journal of Supercomputing, September 2016, vol. 72, no. 9, pp. 3549 – 3571.

Скачать статью