Comparative analysis of the effectiveness of genetic algorithms the routing of the flight, taking into account their different computational complexity and multicriteria tasks

Аuthors

Mikhailin D. A.^1*, Alliluyeva N. V.^2**, Rudenko E. M.^3***

1. Main research and testing center for robotics Ministry of Defense of the Russian , 5, ul. Seregina, Moscow, 125167, Russia
2. Joint-stock company “Scientific and production enterprise “Radar-mms”, 37, Novosel'kovskaya str., lit. A, Sankt-Peterburg, 197375, Russia
3. Peter the Great Strategic Missile Troops Academy, 17, Brigadnaya str., Serpukhov, Moscow region, 142210, Russia

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

Abstract

The paper presents results of the genetic algorithms research. This algorithm solves routing problem the aircraft executes the automatic flight on a pre-laid in memory of his computer flight mission. The cases of single- and multiobjective implementation of the genetic algorithm.

The multicriteria of routing tasks decision can be performed in two stages:

– finding a plurality of routes connecting a start and end point;

– verify the achievements in them the values of all criteria to select the best options.

Multiple routes selecting in a graph between two vertices can be carried out on the basis of minimizing the target function graph.

Estimated computational complexity of the described algorithm one criterion. It is shown, that when a large number of vertices and edges of a graph minimizing the objective function method the most beneficial in the development of preflight tasks.

In real conditions of planning the generated flight plan to meet a number of sometimes conflicting requirements of cost, flight duration, the total importance included in the plan of points. Their importance is uneven and variable, the timeliness of the observations according to the given schedule, etc. The essence of the alternative approach is that the full planned route is divided into several sections (blocks), each of which the dominant one private criteria. This method is suggested by the practice of observation, when one area important the timeliness, on the other – the economy. Thus, the objective functions of genetic algorithm are specified criteria. After the procedure, the formation of “elite” based on specify criteria starts the procedure of “crossing”. It is produced by blocks permutations of intermediate route points in the flight mission and provides a sufficient number of “descendants”. Then, inside all three blocks of the interblock points performs “mutation” that will be performed only between the boundary of points.

It is shown that due to the high performance of modern on-Board computers, implementing complex routing algorithms when observing terrestrial objects with a specified flight schedule does not cause difficulties.

On the basis of simulation results the performance of the algorithms a comparative analysis of their work effectiveness.

Keywords:

genetic algorithm, routing, aircraft surveillance, flight mission

References

1. Lebedev G.N, Goncharenko V.I., Rumakina A.V. Mekhatronika, avtomatizatsiya, upravlenie, 2016, vol. 17, no. 11, pp. 783 – 791.

2. Lebedev G.N., Mirzoyan L.A., Efimov A.V. Mekhatronika, avtomatizatsiya, upravlenie, 2009, no. 11. pp. 60 – 65.

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

4. Skiena S.S. The Algorithm Design Manual. Second Edition. ISBN 978-1-84800-069-8. Springer. The Netherlands as a part of Springer Science+Business Medias, 2008, 730 p.

5. Tomas Kormen, Charl’z Lejzerson, Ronal’d Rivest, Klifford SHtajn. Algoritmy: postroenie i analiz (Introduction to algorithms. 2 edition), Moscow, Izdatel’skii dom “Vil’yams”, 2005, 1290 p.

6. Kogabaev N.T. Lektsii po teorii algoritmov (Lectures on the theory of algorithms), Novosibirsk, Novosibirskii gosudarstvennyi universitet, 2009, 107 p.

7. Lebedev G.N. Trudy MAI, 2015, no. 83, available at: http://trudymai.ru/eng/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. Golovko V.A. Neironnye seti: obuchenie, organizatsiya i primenenie (Neural networks: training, organization and application), Moscow, IPRZhR, 2001, Book 4, 256 p.

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

11. Tsarev F.N. Nauchno-tekhnicheskii vestnik Sankt-Peterburgskogo gosudarstvennogo universiteta informatsionnykh tekhnologii, mekhaniki i optiki, 2008, no. 8(53), pp. 42 – 60.

12. Lebedev G.N., Malygin V.B., Mikhailin D.A. Nauchnyi vestnik MGTU GA, 2017, vol. 20, no. 4, pp. 8 – 17.

13. Allilueva N.V., Rudenko E.M. Trudy MAI, 2017, no. 96, available at: http://trudymai.ru/eng/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. Krasnov M.L., Kiselev A.I., Makarenko G.I., Shikin E.V., Zalyapin V.I., Evnin A.Yu. Vsya vysshaya matematika (All higher mathematics), Moscow, KomKniga, 2006, vol. 7, 199 p.

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.

Download