A Two-Way Parallel Slime Mold Algorithm by Flow and Distance for the Travelling Salesman Problem
Source abstract
Abstract
In order to solve the problem of poor local optimization of the Slime Mold Algorithm (SMA) in the Travelling Salesman Problem (TSP), a Two-way Parallel Slime Mold Algorithm by Flow and Distance (TPSMA) is proposed in this paper. Firstly, the flow between each path point is calculated by the “critical pipeline and critical culture” model of SMA; then, according to the two indexes of flow and distance, the set of path points to be selected is obtained; finally, the optimization principle with a flow index is improved with two indexes of flow and distance and added random strategy. Hence, a two-way parallel optimization method is realized and the local optimal problem is solved effectively. Through the simulation of Traveling Salesman Problem Library (TSPLIB) on ulysses16, city31, eil51, gr96, and bier127, the results of TPSMA were improved by 24.56, 36.10, 41.88, 49.83, and 52.93%, respectively, compared to SMA. Furthermore, the number of path points is more and the optimization ability of TPSMA is better. At the same time, TPSMA is closer to the current optimal result than other algorithms by multiple sets of tests, and its time complexity is obviously better than others. Therefore, the superiority of TPSMA is adequately proven.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Slime Mold and Myxomycetes Research · Metaheuristic Optimization Algorithms Research · Robotic Path Planning Algorithms
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Changchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences, Changchun 130033, China
School of Optoelectronics, University of Chinese Academy of Sciences, Beijing 100049, China
College of Resources and Environmental Sciences, Jilin Agricultural University, Changchun 130118, China
Funding
National Natural Science Foundation of China · Science and Technology Development Plan of Jilin province · Jilin Province and the Chinese Academy of Sciences cooperation in science and technology high-tech industrialization special funds project
References (37)
Show source-provided references
1. Lu, Y., Liu, Y., Gao, C., Tao, L., and Zhang, Z. (2014, January 17–20). A Novel Physarum-Based Ant Colony System for Solving the Real-World Traveling Salesman Problem. Proceedings of the International Conference in Swarm Intelligence, Hefei, China.10.1007/978-3-319-11857-4_20 ↗
2. Random-key cuckoo search for the travelling salesman problem10.1007/s00500-014-1322-9 ↗
3. A hybrid method of 2-TSP and novel learning-based GA for job sequencing and tool switching problem10.1016/j.asoc.2017.12.045 ↗
4. A Hybrid PSO-GA Algorithm for Traveling Salesman Problems in Different Environments10.1142/S0218488519500314 ↗
5. Particle Swarm Optimization: A survey of historical and recent developments with hybridization perspectives
6. An improved multi-objective particle swarm optimization and its application in raw ore dispatching10.1177/1687814018757376 ↗
7. A solution of TSP based on the ant colony algorithm improved by particle swarm optimization
8. Nechita, E., Crisan, G.C., Lantovics, L.B., and Huang, Y. (2020). On the Resilience of Ant Algorithms. Experiment with Adapted MMAS on TSP. Mathematics, 8.10.3390/math8050752 ↗
9. Lin-Kernighan Heuristic Adaptations for the Generalized Traveling Salesman Problem10.1016/j.ejor.2010.08.011 ↗
10. (2019). Kernighan local search for a real-life Two-Echelon Heterogeneous Vehicle Routing Problem based on Brazilian wholesale companies. Appl. Soft Comput., 76, 697–711.10.1016/j.asoc.2018.12.036 ↗
11. General k-opt submoves for the Lin–Kernighan TSP heuristic10.1007/s12532-009-0004-6 ↗
12. Solving Arc Routing Problems Using the Lin-Kernighan-Helsgaun Algorithm
13. Myxomycetes: A Handbook of Slime Molds by Steven, L. Stephenson
14. Intelligence: Maze-Solving by an Amoeboid Organism10.1038/35035159 ↗
15. Rules for Biologically Inspired Adaptive Network Design10.1126/science.1177894 ↗
16. Physarum Itinerae: Evolution of Roman Roads with Slime Mould10.4018/jnmc.2011040103 ↗
17. Slime mould imitates transport networks in China10.1108/IJICC-02-2013-0005 ↗
18. Slime mould imitates development of Roman roads in the Balkans
19. Becker, M. (2016, January 24–29). On the quality of graphs generated by swarm algorithms. Proceedings of the IEEE Congress on Evolutionary Computation, Vancouver, BC, Canada.10.1109/CEC.2016.7744262 ↗
20. Meyer-Nieberg, S. (2017, January 15–19). Coordinating a team of searchers: Of ants, swarms, and slime molds. Proceedings of the Genetic & Evolutionary Computation Conference, Berlin, Germany.10.1145/3071178.3071277 ↗
21. A Bio-Inspired Approach to Traffic Network Equilibrium Assignment Problem10.1109/TCYB.2017.2691666 ↗
22. Novel Routing Method Using Slime Mold Algorithm Corresponding to Movement of Content Source in Content-Oriented Networks10.2299/jsp.23.173 ↗
23. Slime mould algorithm: A new method for stochastic optimization10.1016/j.future.2020.03.055 ↗
24. Smart network solutions in an amoeboid organism10.1016/S0301-4622(03)00189-3 ↗
25. Physarum solver: A biologically inspired method of road-network navigation10.1016/j.physa.2006.01.053 ↗
26. Mathematical Model for Rhythmic Protoplasmic Movement in the True Slime Mold10.1007/s00285-006-0007-0 ↗
27. A mathematical model for adaptive transport network in path finding by true slime mold10.1016/j.jtbi.2006.07.015 ↗
28. Minimum-risk path finding by an adaptive amoebal network10.1103/PhysRevLett.99.068104 ↗
29. Minimal model of a cell connecting amoebic motion and adaptive transport networks10.1016/j.jtbi.2008.04.017 ↗
30. An adaptive and robust biological network based on the vacant-particle transportation model10.1016/j.jtbi.2010.12.013 ↗
31. Liu, Y., Lu, Y., Gao, C., Zhang, Z., and Tao, L. (2014, January 19–21). A multi-objective ant colony optimization algorithm based on the Physarum-inspired mathematical model. Proceedings of the 10th International Conference on Natural Computation, Xiamen, China.10.1109/ICNC.2014.6975852 ↗
32. A universal optimization strategy for ant colony optimization algorithms based on the Physarum-inspired mathematical model10.1088/1748-3182/9/3/036006 ↗
33. Zhang, Z., Gao, C., Lu, Y., Liu, Y., and Liang, M. (2016). Multi-Objective Ant Colony Optimization Based on the Physarum-Inspired Mathematical Model for Bi-Objective Traveling Salesman Problems. PLoS ONE, 11.10.1371/journal.pone.0146709 ↗
34. A new multi-agent system to simulate the foraging behaviors of Physarum10.1007/s11047-015-9530-5 ↗
35. Route 20, Autobahn 7, and Slime Mold: Approximating the Longest Roads in USA and Germany with Slime Mold on 3-D Terrains10.1109/TCYB.2013.2248359 ↗
36. Uemura, M., Matsushita, H., and Kraetzschmar, G.K. (2015, January 9–12). Path Planning with Slime Molds: A Biology-Inspired Approach. Proceedings of the International Conference on Neural Information Processing, Istanbul, Turkey.10.1007/978-3-319-26561-2_37 ↗
37. Physical maze solvers. All twelve prototypes implement 1961 Lee algorithm10.1007/978-3-319-46376-6_23 ↗