№1, 2020
COMPARISON OF DECISIONS QUALITY OF HEURISTIC METHODS BASED ON MODIFYING OPERATIONS IN THE GRAPH SHORTEST PATH PROBLEM
The article deals with the problem of the analysis of effectiveness of the heuristic methods based on the modification of earlier found decisions in the test problem for getting the shortest path in graph. The article briefly describes the selected group of methods used to solve the problem. The methodology considers the experimental comparison for estimating the quality of solutions based on the performance of computational experiments with the samples of pseudo-randomly structured graphs that uses the BOINC platform. It also presents the description of obtained experimental results which allow to identify the areas of the preferable usage of selected subset of methods depending on the size of the problem and power of constraints. It is shown that the particle swarm optimization, random walks, simulated annealing and bee colony methods are ineffective in the selected problem and significantly inferior to the quality of solutions that are provided by ant colony optimization method and genetic algorithms (pp.3-15).
Keywords: heuristic methods, genetic algorithms, particle swarm optimization, random walks, simulated an-nealing, bee colony method, shortest path problem, discrete combinatorial optimization, BOINC.
References
- Rosen K.H. et al. Handbook of discrete and combinatorial mathematics. CRC Press, New York, 2000, 768 p.
- Vatutin E.I., Titov V.S., Emelyanov S.G. Basics of discrete combinatorial optimization (in Russian). M.: Argamac-Media, Moscow, 2016, 270 p.
- Karpenko A.P. Modern algorithms of search optimization. Algorithms inspired by nature (in Russian). M.: Bauman Moscow State Technical University, 2014, 446 p.
- Prim R.C. Shortest connection networks and some generalizations // Bell System Technical Journal, 1957, vol. 36, no 6, pp. 1389–1401. DOI: 10.1002/j.1538-7305.1957.tb01515.x
- Kruskal J.B. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 1956, vol. 7, pp. 48–50.
DOI: 10.1090/S0002-9939-1956-0078686-7 - Kuhn H.W. Variants of the Hungarian method for assignment problems. Naval Research Logistics Quarterly. 1956. pp. 253–258. DOI: 10.1002/nav.3800030404
- Munkres J. Algorithms for the Assignment and Transportation Problems // Journal of the Society for Industrial and Applied Mathematics, 1957, vol. 1, no. 5, pp. 32–38. DOI: 10.1137/0105003
- Land A.H., Doig A.G. An Automatic Method of Solving Discrete Programming Problems. Econometrica, 1960, vol. 28, pp. 497–520. DOI: 10.2307/1910129
- Colbourn C.J., Dinitz J.H. Handbook of Combinatorial Designs, 2nd ed. (Discrete Mathematics and Its Applications). New York: Chapman & Hall/CRC, 2006, 1026 p.
- Zaikin O.S., Kochemazov S.E., Semenov A.A. SAT-based search for systems of diagonal Latin squares in volunteer computing project SAT@home / 39th international convention on information and communication technology, electronics and microelectronics (MIPRO 2016). 2016, pp. 277–281. DOI: 10.1109/MIPRO.2016.7522152
- Vatutin E.I., Dremov E.N., Martynov I.A., Titov V.S. Weighted random search method for discrete combinatorial problems solving (in Russian) // Proceedings of Volgograd State Technical University. Series: Electronics, Measuring Equipment, Radiotechnics and Communication, 2014, № 10 (137). 9, pp. 59–64.
- Dorigo M. Optimization, Learning and Natural Algorithms. PhD thesis. Milan: Politecnico di Milano, 1992.
- Vatutin E.I., Titov V.S. Analysis of results of ant colony optimization method in the problem of getting shortest path in graph with constraints (in Russian) // Proceedings of South State University. Technical sciences. 2014, № 12 (161), pp. 111–120.
- Glover F., Kochenberger G.A. Handbook of Metaheuristics. New York: Kluwer Academic Publishers, 2003, 756 p.
- Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by Simulated Annealing. Science, 1983, vol. 220, no. 4598, pp. 671–680. DOI: 10.1126/science.220.4598.671
- Karaboga D.D. An Idea Based On Honey Bee Swarm for Numerical Optimization. Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.
- Pham D.T., Ghanbarzadeh A., Koc E., Otri S., Rahim S., Zaidi M. The Bees Algorithm. Technical Note, Manufacturing Engineering Centre, Cardiff University, 2005.
- Kennedy J., Eberhart R. Particle Swarm Optimization / Proceedings of IEEE International Conference on Neural Networks. 1995, pp. 1942–1948. DOI: 10.1109/ICNN.1995.488968
- Vatutin E.I., Titov V.S. Investigation of Features of Particle Swarm Optimization Method in Graph Shortest Path Problem with Constraints (in Russian) // Herald of computer and information technologies, 2018, no. 5 (167), pp. 26–34. DOI: 0.14489/vkit.2018.05.pp.026–034
- Vatutin E.I. Comparison of Decisions Quality of Heuristic Methods with Sequential Formation of the Decision in the Graph Shortest Path Problem / CEUR Workshop Proceedings. Proceedings of the Third International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC: FAST 2017). Technical University of Aachen, Germany, 2017, pp. 67–76.
- Vatutin E.I. Comparison of Decisions Quality of Heuristic Methods with Limited Depth-First Search Techniques in the Graph Shortest Path Problem // Open Engineering, 2017, vol. 7, no 1, pp. 428–434. DOI: 10.1515/eng-2017-0041
- Dijkstra E.W. A note on two problems in connexion with graphs. Numerische Mathematik, 1959, vol. 1., pp. 269–271.
- Vatutin E.I., Valyaev S.Yu., Titov V.S. Comparison of Sequential Methods for Getting Separations of Parallel Logic Control Algorithms Using Volunteer Computing / CEUR Workshop Proceedings. Proceedings of the Second International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC: FAST 2015). 2015, vol. 1502, pp. 37–51. urn:nbn:de:0074-1502-3
- Vatutin E.I., Titov V.S. Analisys of the areas of qualitative superiority of the sequential heuristic methods for getting separation during logic multicontrollers design (in Russian). Proceedings of the Higher Educational Institutions. Instrument Making, 2015, vol. 58, no 2, pp. 115–122. DOI: 10.17586/0021-3454-2015-58-2-115-122
- Anderson D.P. BOINC: a system for public-resource computing and storage / Fifth IEEE/ACM International Workshop on Grid Computing, 2004. DOI: 10.1109/GRID.2004.14
- Vatutin E.I., Titov V.S. Parametric optimization of simulated annealing algorithm at the shortest path problem (in Russian) // Proceedings of Cherepovets State University, 2015, no 6 (67), pp.13–16.
- Vatutin E.I., Titov V.S. The features of use genetic algorithm in the problem of finding the shortest path in the graph with graph density constraint (in Russian) // Multicore processors, parallel programming, FPGA, signal processing systems. Barnaul: Altay State University, 2016. pp.152–159.
- Vatutin E.I., Titov V.S. Features of meta-optimization of the bee colony method in the shortest path problem with constraints on the graph density (in Russian) // Proceedings of Southwest State University. Series: Control, Computer Science, Informatics. Medical Devices, 2016, no 2 (19), pp. 52–65.
- Hamming R.W. Error detecting and error correcting codes // Bell System Technical Journal. 1950, vol. 29, pp. 147–160. DOI: 10.1002/j.1538-7305.1950.tb00463.x.
- Levenstein V.I. Binary codes with correction of fallouts, inserts and substitutions of symbols (in Russian) // Proceedings of Academies of Sciences of the USSR, 1965, vol. 163, no 4. pp. 845–848.
- Kurochkin I.I. Determination of Replication Parameters in the Project of the Voluntary Distributed Computing Netmax@Home // Science. Business. Society, 2016, vol. 2, pp.10–12.
- Nikitina N.N., Ivashko E.E. The Price of Anarchy in a Game for Drug Discovery. Networking Games and Management Extended abstracts. 2016, pp. 24–25.
- Vatutin E.I., Martynov I.A., Titov V.S. Method of Workaround deadlocks for solving discrete combinatorial optimization problems with constraints (in Russian) // Perspective information technologies. Samara, Samara scientific center of RAS, 2014, pp. 313–317.
