nach oben

Automatic Documentation and Mathematical Linguistics

Erschienen in:

01.02.2024 | INFORMATION PROCESSES

Development of a Modification of the Particle Collision Algorithm (PCA), Providing an Approximate Solution to the Traveling Salesman Problem

verfasst von: D. Yu. Syedin

Erschienen in: Automatic Documentation and Mathematical Linguistics | Ausgabe 1/2024

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract—

This work is devoted to the development of a modification of the particle collision algorithm (PCA), which provides an approximate solution to the traveling salesman problem. The resulting modification was tested on a number of well-known tasks and demonstrated greater accuracy and efficiency than its analogues.

Nächster Artikel On Rank r Empirical Regularities in the JSM Method of Automated Research Supporta

Makarkin, S.B., Mel’nikov, B.F., and Trenina, M.A., Approach to solving pseudo-geometric version of the travelling salesman problem, Izv. Vyssh. Uchebn. Zaved., Povolzhskii Region, Fiziko-Mat. Nauki, 2015, no. 2, pp. 135–147.

Makarkin, S.B. and Mel’nikov, B.F., Suitability of the mathematical models on example of the travelling salesman problem, Filosofskie Probl. Inf. Tekhnol. Kiberprostranstva, 2013, no. 2, pp. 4–17.

Kureichik, V.M. and Logunova, J.A., The hybrid approach for the travelling salesman problem solving using cloud computing in the Internet, Izv. Yuzhnogo Fed. Univ., Tekh. Nauki, 2019, no. 5, pp. 25–33. https://doi.org/10.23683/2311-3103-2019-5-25-33

Ramazanova, R.R., Filippova, A.S., and Kartak, V.M., Analysis of practical use of one algorithm for solving the problem of transport logistics in information system, Sbornik trudov mezhdunarodnoi nauchno-tekhnicheskoi konferentsii Perspektivnye informatsionnye tekhnologii PIT-2013 (Proc. Int. Sci.-Tech. Conf. on Perspective Information Technologies), Samara, 2013, Prokhorov, S.A., Ed., Samara: Izd-vo Samarskogo Nauchnogo Tsentra Ross. Akad. Nauk, 2013, pp. 221–224.

Mel’nikov, B.F., Aksenova, E.A., Anokhina, T.V., Korneeva, S.A., Zotova, M.A., Naumov, V.V., Smirnova, T.G., Sokurova, A.M., and Yuldashev, A.V., Heuristic algorithms for solving the problems of combinatorial optimization, Mire Nauchnykh Otkrytii, 2012, nos. 12–1, pp. 86–114.

Betin, V.N., Ivashchenko, V.A., and Suprun, A.P., Eliciting and the use of information concerning regular structures in the formalism of functional neural networks in decision-support systems, Autom. Doc. Math. Linguist., 2022, vol. 56, no. 4, pp. 179–186. https://doi.org/10.3103/s0005105522040021CrossRef

Betin, V.N., Luk’yanov, S.E., and Suprun, A.P., A mechanism for a solution search within the formalism of functional neural networks, Autom. Doc. Math. Linguist., 2020, vol. 54, pp. 124–129. https://doi.org/10.3103/S0005105520030024CrossRef

Kolesnikov, A.V., Kirikov, I.A., Listopad, S.V., Rumovskaya, S.B., and Domanitskii, A.A., Reshenie slozhnykh zadach kommivoyazhera metodami funktsional’nykh gibridnykh intellektual’nykh sistem (Solving Complicated Travelling Salesman Problems by the Methods of Functional Hybrid Intelligent Systems), Kolesnikov, A.V., Ed., Moscow: Inst. Problem Informatiki Ross. Akad. Nauk, 2011.

Sacco, W.F. and De Oliveira, C.R.E., A new stochastic optimization algorithm based on particle collisions, Proc. 2005 ANS Annu. Meeting. Transactions of the American Nuclear Society, San Diego, Calif.: American Nuclear Society, 2005, pp. 657–659.

10.

Da Luz, E.F.P. and Beccener, J.C., A new multi-particle collision algorithm for optimization in a high performance environment, J. Comput. Interdiscip. Sci., 2008, vol. 1, no. 1, pp. 3–10.

11.

Sulimov, V. and Shkapov, P., Application of hybrid global optimization algorithms to extremum problems in hydro-mechanical systems, Nauka Obraz., 2013, vol. 13, no. 11, pp. 141–158.

12.

Sulimov, V.D., Shkapov, P.M., and Nosachev, S.K., Hooke–Jeeves method-used local search in a hybrid global optimization algorithm, Nauka Obraz., 2014, vol. 14, no. 6, pp. 107–123.

13.

Syedin, D.Yu., On hybridization of stochastic global optimization algorithms taking into account the features of their architecture, Informatizatsiya Svyaz’, 2021, no. 1, pp. 113–117. https://doi.org/10.34219/2078-8320-2021-12-1-113-117

14.

Zakharov, V.V. and Mugaiskikh, A.V., Dynamic adaptation of genetic algorithm for the large-scale routing problems, Upr. Bol’shimi Sist., 2018, vol. 73, pp. 108–133. https://doi.org/10.25728/ubs.2018.73.6CrossRef

15.

Andrianova, E.G., Raev, V.K., and Filgus, D.I., Determination of the shortest Hamiltonian paths in an arbitrary graph of distributed databases, Ross. Tekhnol. Zh., 2019, vol. 7, no. 4, pp. 7–20. https://doi.org/10.32362/2500-316x-2019-7-4-7-20CrossRef

16.

El Krari, M., Ahiod, B., and El Benani, B., Breakout local search for the travelling salesman problem, Comput. Inf., 2018, vol. 37, no. 3, pp. 656–672. https://doi.org/10.4149/cai_2018_3_656MathSciNetCrossRef

17.

Sengupta, L., Mariescu-Istodor, R., and Fränti, P., Which local search operator works best for the open-loop TSP?, Appl. Sci., 2019, vol. 9, no. 19, p. 3985. https://doi.org/10.3390/app9193985CrossRef

18.

Croes, G.A., A method for solving traveling-salesman problems, Oper. Res., 1958, vol. 6, no. 6, pp. 791–812. https://doi.org/10.1287/opre.6.6.791MathSciNetCrossRef

19.

Flood, M.M., The traveling-salesman problem, Oper. Res., 1956, vol. 4, no. 1, pp. 61–75. https://doi.org/10.1287/opre.4.1.61CrossRef

20.

Martin, O., Otto, S.W., and Felten, E.W., Large-step Markov chains for the TSP incorporating local search heuristics, Oper. Res. Lett., 1992, vol. 11, no. 4, pp. 219–224. https://doi.org/10.1016/0167-6377(92)90028-2MathSciNetCrossRef

21.

Bjelić, N. and Popović, D., Two-phase algorithm for solving heterogeneous travelling repairmen problem with time windows, Int. J. Traffic Transp. Eng., 2015, vol. 5, no. 1, pp. 64–73. https://doi.org/10.7708/ijtte.2015.5(1).08CrossRef

22.

Hoos, H. and Stützle, T., Stochastic Local Search: Foundations and Applications, San Francisco: Morgan Kaufmann, 2005.

23.

Holland, J.H., Adaptation in Natural and Artificial Systems, Ann Arbor, Mich.: Univ. of Michigan Press, 1975.

24.

Kennedy, J. and Eberhart, R. Particle swarm optimization, Proc. ICNN'95 Int. Conf. on Neural Networks, Perth, Australia, 1995, vol. 4, pp. 1942–1948.https://doi.org/10.1109/ICNN.1995.488968

Titel: Development of a Modification of the Particle Collision Algorithm (PCA), Providing an Approximate Solution to the Traveling Salesman Problem
verfasst von: D. Yu. Syedin
Publikationsdatum: 01.02.2024
Verlag: Pleiades Publishing
Erschienen in: Automatic Documentation and Mathematical Linguistics / Ausgabe 1/2024
Print ISSN: 0005-1055
Elektronische ISSN: 1934-8371
DOI: https://doi.org/10.3103/S0005105524010047

Springer Professional

Development of a Modification of the Particle Collision Algorithm (PCA), Providing an Approximate Solution to the Traveling Salesman Problem

Abstract—

Premium Partner

Springer Professional

Abstract—

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 1/2024

Digital Twins and Basic Digital Student Profiles

Topic Modeling for Mining Opinion Aspects from a Customer Feedback Corpus

Correspondence between Hierarchical Knowledge Classifiers

On Rank r Empirical Regularities in the JSM Method of Automated Research Supporta

Technical Writer as a Communication Specialty: Editorial Interpretation of Its Professionogram

The Practical Significance of Bradford’s Informetric Model to Predict the Scattering of Articles and Optimize Journal Selection

Premium Partner