RADIOELECTRONIC AND COMPUTER SYSTEMS

Today, for intelligent computer systems of general and special purpose, the task of finding the optimal route is actual. Currently, there is a problem of lack of efficiency of methods for finding the quasi-optimal route. The object of the research is the process of solving optimization problems of finding a route. The subject of the research is a method for finding a quasi-optimal route based on metaheuristics. The current work increases the efficiency of searching for a quasi-optimal route using a metaheuristic method based on the ant algorithm. To achieve this goal, the work was created a method based on the ant algorithm and simulated annealing for the traveling salesman problem, was formulated the problem of the shortest path in the world of tiles, was developed a method based on the ant algorithm and simulated annealing for the problem of the shortest path in the world of tiles. Advantages of the proposed methods include the following. First, for calculating the probability of an ant moving from the current vertex to other vertices at the initial iterations, the random pheromone level plays the main role, which makes it possible to implement a random search, and at the final iterations, the normalized previous pheromone levelplays the main role, which makes it possible to implement directed search. This is ensured by the use of simulated annealing and increases the accuracy of finding a quasi-optimal route. Second, for calculating the change in the pheromone level at the initial iterations, the pheromone increment plays the main role, which ensures the breadth of the search, and at the final iterations, the previous pheromone level plays the main role, which ensures the convergence of the method. This is ensured by the use of simulated annealing and increases the accuracy of finding a quasi-optimal route. Third, the modification of the ant algorithm by calculating the length of the edges based on the Chebyshev distance, placing all ants in the initial vertex, checking for a dead-end, checking that the target vertex has been reached, and using Moore's neighborhood allows solving problems of the shortest path in the world of tiles. The performed numerical study made it possible to evaluate both methods (for the first method, the root-mean-square error was 0.04, and for the second method it was 0.03). The proposed methods make it possible to expand the area of application of metaheuristics based on the ant algorithm, which is confirmed by its adaptation for the specified optimization problems and contributes to an increase in the efficiency of intelligent computer systems for general and special purposes. The prospects for future research are the study of the proposed methods for a wide class of artificial intelligence problems.

metaheuristics; optimal route search; ant algorithm; simulated annealing; traveling salesman problem; shortest path problem in the world of tiles; pheromone level; Moore's neighborhood

Yu, X., Gen, M. Introduction to evolutionary algorithm. London, Springer-Verlag Publ., 2010. 433 p.

Engelbrecht, A. P. Computational intelligence: an introduction. Chichester, West Sussex, Wiley & Sons Publ., 2007. 630 р. DOI: 10.1002/9780470512517.

Talbi, El-G. Metaheuristics: from design to implementation. Hoboken, New Jersey, Wiley & Sons Publ., 2009. 618 р. DOI: 10.1002/9780470496916.

Yang, X.-S. Nature-inspired Algorithms and Applied Optimization. Charm, Springer Publ., 2018. 330 р. DOI: 10.1007/978-3-642-29694-9.

Nakib, A., Talbi, El-G. Metaheuristics for Medicine and Biology. Berlin, Springer-Verlag Publ., 2017. 211 р. DOI: 10.1007/978-3-662-54428-0.

Glover, F., Kochenberger G. A. Handbook of metaheuristics. Dordrecht, Kluwer Academic Publishers, 2003. 570 р. DOI: 10.1007/B101874.

Subbotin, S., Oliinyk, A., Levashenko, V., Zaitseva, E. Diagnostic Rule Mining Based on Artificial Immune System for a Case of Uneven Distribution of Classes in Sample. Communications, 2016, vol. 3, рр. 3–11.

Yang, X.-S. Optimization Techniques and Applications with Example. Hoboken, New Jersey, Wiley & Sons Publ., 2018. 364 р. DOI: 10.1002/9781119490616.

Blum, C., Raidl, G. R. Hybrid Metaheuristics. Powerful Tools for Optimization. Charm, Springer Publ., 2016. 157 р. DOI: 10.1007/978-3-319-30883-8.

Martí, R., Pardalos, P. M., Resende, G. C. Handbook of Heuristics. Charm, Springer Publ., 2018. 1289 р. DOI: 10.1007/978-3-319-07124-4.

Bozorg Haddad, O., Solgi, M., Loaiciga H. Meta-heuristic and Evolutionary Algorithms for Engineering Optimization, Hoboken, New Jersey, Wiley & Sons Publ., 2017. 293 р. DOI: 10.1002/9781119387053.

Gendreau, M., Potvin, J.-Y. Handbook of Metaheuristics. New York, Springer Publ., 2010. 640 р. DOI: 10.1007/978-1-4419-1665-5.

Chopard, B., Tomassini, M. An Introduction to Metaheuristics for Optimization. New York, Springer Publ., 2018. 230 р. DOI: 10.1007/978-3-319-93073-2.

Radosavljević, J. Metaheuristic Optimization in Power Engineering. New York, Institution of Engineering and Technology Publ., 2018. 536 р. DOI: 10.1049/PBPO131E.

Doerner, K. F., Gendreau, M., Greistorfer, P., Gutjahr, W., Hartl, R. F., Reimann, M. Metaheuristics. Progress in Complex Systems Optimization. New York, Springer Publ., 2007. 408 р. DOI: 10.1007/978-0-387-71921-4.

Colorni, A., Dorigo, M., Maniezzo, V., Trubian, M. Ant system for job-shop scheduling. Belgian Journal of Operations Research, Statistics and Computer Science, 1994, vol. 34, no. 1, рр. 39–53.

Gambardella, L. M., Taillard, É. D., Dorigo M. Ant colonies for the quadratic assignment problem. Journal of the Operational Research Society, 1999, vol. 50, no. 2, рр. 167–176.

Min, H., Dazhi, P., Song, Y. An improved hybrid ant colony algorithm and its application in solving TSP. Proceedings of the 2014 7th IEEE Joint International Information Technology and Artificial Intelligence Conference (ITAIC '14), Chongqing, China, December, 2014, рр. 423–427.

Du, K.-L., Swamy, M. N. S. Search and Optimization by Metaheuristics. Techniques and Algorithms Inspired by Nature. Charm, Springer Publ., 2016. 434 р. DOI: 10.1007/978-3-319-41192-7.

Alba, E., Nakib, A., Siarry, P. Metaheuristics for Dynamic Optimization. Berlin, Springer-Verlag Publ., 2013. 398 р. DOI: 10.1007/978-3-642-30665-5.

Brownlee, J. Clever algorithms: nature-inspired programming recipes. Melbourne, Brownlee Publ., 2011. 436 р.

Grygor, O. O., Fedorov, E. E., Utkina, T. Yu., Lukashenko, A. G., Rudakov, K. S., Harder, D. A., Lukashenko, V. M. Optimization method based on the synthesis of clonal selection and annealing simulation algorithms. Radio Electronics, Computer Science, Control, 2019, no. 2, рр. 90-99. DOI: 10.15588/1607-3274-2019-2-10.

Fedorov, E., Lukashenko, V., Utkina, T., Lukashenko, A., Rudakov, K. Method For Parametric Identification Of Gaussian Mixture Model Based On Clonal Selection Algorithm. CEUR Workshop Proceedings, 2019, vol. 2353, рр. 41-55. Available at: http://ceur-ws.org/Vol-2353/paper4.pdf (accessed 12.10.2021).

Sturtevant, N. R. Benchmarks for Grid-Based Pathfinding. IEEE Transactions on Computational Intelligence and AI in Games, 2012, vol. 4, no. 2, рр. 144-148.

Kuchuk, N., Merlak, V. Modeling of information interconnection in a computer control system of moving objects. Radioelectronic and computer systems, 2021, no. 1, рр. 31-39. DOI: 10.32620/reks.2021.1.02.

Wawrzynski, T. Artificial intelligence and cyberculture. Radioelectronic and computer systems, 2020, no. 3, рр. 20–25. DOI: 10.32620/reks.2020.3.02.

Li. Fangfang, Krivenko, S., Lukin, V. Two-step providing of desired quality in lossy image compression by spiht. Radioelectronic and computer systems, 2020, no. 2, рр. 22-32. DOI: 10.32620/reks.2020.2.02.

Kononenko, I., Sushko, H. Mathematical model of software development project team composition optimization with fuzzy initial data. Radioelectronic and computer systems, 2021, no. 3, рр. 149-159. DOI: 10.32620/reks.2021.3.12.