Figure 1.
The flow chart of improved ant colony algorithm
-
Previous Article
Environmental game modeling with uncertainties
- DCDS-S Home
- This Issue
-
Next Article
Retraction: Xiao-Qian Jiang and Lun-Chuan Zhang, A pricing option approach based on backward stochastic differential equation theory
August & September
2019, 12(4&5): 979-987.
doi: 10.3934/dcdss.2019066
A solution of TSP based on the ant colony algorithm improved by particle swarm optimization
China University of Political Science and Law, Beijing, China |
TSP is a classic problem in the field of logistics, and ant colony algorithm is an important way to solve the problem. However, the ant colony algorithm has some shortcomings in practical application. In this paper, the ant colony algorithm is improved by particle swarm optimization algorithm, and the ant colony algorithm is obtained by giving the ant colony a certain ''particle property''. Finally, an example is given to demonstrate the effectiveness of the improved ant colony algorithm.
Mathematics Subject Classification:
Primary: 58F15, 58F17; Secondary: 53C35.
Citation:
Miao Yu. A solution of TSP based on the ant colony algorithm improved by particle swarm optimization. Discrete & Continuous Dynamical Systems - S,
2019, 12
(4&5)
: 979-987.
doi: 10.3934/dcdss.2019066
![]()
References:
| [1] |
Y. An, Application of linear programming theory to strengthen the cost control of engineering project Railway engineering cost management, 2013. Google Scholar |
| [2] |
G. Barbarosoglu and D. Ozgur,
A tabu seacrh algorithm for the vehiciel routing problem, Computers & Operations Reseacrh, 26 (1999), 255-270.
doi: 10.1016/S0305-0548(98)00047-1. |
| [3] |
M. L. Bech and E. Atalay, The topology of the federal funds market, Physica A: Statistical Mechanics and its Applications, 389 (2010), 5223-5246. https://www.sciencedirect.com/science/article/pii/S0378437110004887. Google Scholar |
| [4] |
I. Ciornei and E. Kyriakides, Hybrid ant colony-genetic algorithm (GAAPI) for global continuous optimization, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 42 (2012), 234-245. https://ieeexplore.ieee.org/document/6008671. Google Scholar |
| [5] |
M. Dorigo, V. Maniezzo and A. Colorni, Positive feedback as a Search Strategy, Technical Report, 1991, 91-106. https://www.researchgate.net/publication/2573263_Positive_Feedback_as_a_Search_Strategy. Google Scholar |
| [6] |
M. Dorigo and L. M. Gambardella, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation 1997, 1(1): 53-66. https://ieeexplore.ieee.org/abstract/document/585892. Google Scholar |
| [7] |
H. Hernández and C. Blum, Foundations of antcycle: Self-synchronized duty-cycling in mobile sensor networks, Computer Journal, 54 (2011), 1427-1448. https://ieeexplore.ieee.org/document/8130483. Google Scholar |
| [8] |
S. Kirkpatrick1, C. D. Gelatt Jr. and M. P. Vecchi,
Optimization by simulated annealing, Science, 220 (1983), 671-680.
doi: 10.1126/science.220.4598.671. |
| [9] |
F. Liu, S. Zhao, M. Weng and Y. Liu, Fire risk assessment for large-scale commercial buildings based on structure entropy weight method, Safety Sci., 94 (2017), 26-40. https://www.sciencedirect.com/science/article/pii/S0925753516306531?via. Google Scholar |
| [10] |
Y. Z. Liu and Z. P. Fan, Multiple attribute decision making considering attribute aspirations: A method based on prospect theory, Kongzhi Yu Juece/control & Decision, 30 (2015), 91-97. http://en.cnki.com.cn/Article_en/CJFDTOTAL-KZYC201501017.htm. Google Scholar |
| [11] |
L. Liu, T. Zhang and B. Ru, A flying qualities assessment model based on multiparameter integration, Computer Engineering and Science, 38 (2016), 1262-1268. https://www.sciencedirect.com/science/article/pii/S1389041718302365. Google Scholar |
| [12] |
S. C. Nicolis and J. L. Deneubourg, Emerging patterns and food recruitment in ants: An analytical study, Journal of Theoretical Biology, 198 (1999), 575-592. https://www.sciencedirect.com/science/article/pii/S0022519399909347. Google Scholar |
| [13] |
M. W. P. Savelsbergh,
Local search in routing problems with time windows, Annals of Operations Research, 4 (1985), 285-305.
doi: 10.1007/BF02022044. |
| [14] |
L. Santos, J. Coutinho-Rodrigues and J. R. Current, An improved ant colony optimization based algorithm for the capacitated arc routing problem, Transportation Research Part B: Methodological, 44 2010,246-266. https://www.sciencedirect.com/science/article/pii/S0191261509000836. Google Scholar |
| [15] |
T. Stützle and H. H. Hoos, MAX-MIN ant system, Future Generation Computer Systems, 16 (2000), 889-914. https://www.sciencedirect.com/science/article/pii/S0167739X00000431. Google Scholar |
| [16] |
M. Yu, S. Li, M Kong, J. Song and G. Ren, Comparison of advantages and disadvantages among various algorithms in logisticspath designTaking H-group as an example, Cognitive Systems Research, 52(2018) 843-852. https://www.sciencedirect.com/science/article/pii/S1389041718302365.
doi: 10.1016/j.cogsys.2018.08.014. |
| [17] |
M. Yu, J. Song, D. Zhao and G. Ren, Management of expressway service area based on integrated optimization, Cognitive Systems Research, 52 (2018) 875-881. https://www.sciencedirect.com/science/article/pii/S1389041718302390.
doi: 10.1016/j.cogsys.2018.08.013. |
| [18] |
Z. Zhang, Y. Shi and G. Gao, A rough set-based multiple criteria linear programming approach for the medical diagnosis and prognosis, Expert Systems with Applications, 36 (2009), 8932-8937.https://www.semanticscholar.org/paper/A-rough-set-based-multiple-criteria-linear-approach-Zhang-Shi/73209c1d7bc7051a4cd64c059d0edf2cfad86840.
doi: 10.1016/j.eswa.2008.11.007. |
| [19] |
S. Zhou, C. Hu and X. Qiao, et al., A forecasting method for Chinese civil planes attendance rate based on vague sets. Chaos Solitons & Fractals the Interdisciplinary Journal of Nonlinear Science & Nonequilibrium & Complex Phenomena, 89 (2016), 518-526. https://www.sciencedirect.com/science/article/pii/S0960077916300649?via. Google Scholar |
| [20] |
S. Zhou, W. Liu and W. Chang, An improved TOPSIS with weighted hesitant vague information, Chaos Solitons & Fractals the Interdisciplinary Journal of Nonlinear Science & Nonequilibrium & Complex Phenomena, 89 (2016), 47-53. https://www.sciencedirect.com/science/article/pii/S0960077915002970. Google Scholar |
show all references
References:
| [1] |
Y. An, Application of linear programming theory to strengthen the cost control of engineering project Railway engineering cost management, 2013. Google Scholar |
| [2] |
G. Barbarosoglu and D. Ozgur,
A tabu seacrh algorithm for the vehiciel routing problem, Computers & Operations Reseacrh, 26 (1999), 255-270.
doi: 10.1016/S0305-0548(98)00047-1. |
| [3] |
M. L. Bech and E. Atalay, The topology of the federal funds market, Physica A: Statistical Mechanics and its Applications, 389 (2010), 5223-5246. https://www.sciencedirect.com/science/article/pii/S0378437110004887. Google Scholar |
| [4] |
I. Ciornei and E. Kyriakides, Hybrid ant colony-genetic algorithm (GAAPI) for global continuous optimization, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 42 (2012), 234-245. https://ieeexplore.ieee.org/document/6008671. Google Scholar |
| [5] |
M. Dorigo, V. Maniezzo and A. Colorni, Positive feedback as a Search Strategy, Technical Report, 1991, 91-106. https://www.researchgate.net/publication/2573263_Positive_Feedback_as_a_Search_Strategy. Google Scholar |
| [6] |
M. Dorigo and L. M. Gambardella, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation 1997, 1(1): 53-66. https://ieeexplore.ieee.org/abstract/document/585892. Google Scholar |
| [7] |
H. Hernández and C. Blum, Foundations of antcycle: Self-synchronized duty-cycling in mobile sensor networks, Computer Journal, 54 (2011), 1427-1448. https://ieeexplore.ieee.org/document/8130483. Google Scholar |
| [8] |
S. Kirkpatrick1, C. D. Gelatt Jr. and M. P. Vecchi,
Optimization by simulated annealing, Science, 220 (1983), 671-680.
doi: 10.1126/science.220.4598.671. |
| [9] |
F. Liu, S. Zhao, M. Weng and Y. Liu, Fire risk assessment for large-scale commercial buildings based on structure entropy weight method, Safety Sci., 94 (2017), 26-40. https://www.sciencedirect.com/science/article/pii/S0925753516306531?via. Google Scholar |
| [10] |
Y. Z. Liu and Z. P. Fan, Multiple attribute decision making considering attribute aspirations: A method based on prospect theory, Kongzhi Yu Juece/control & Decision, 30 (2015), 91-97. http://en.cnki.com.cn/Article_en/CJFDTOTAL-KZYC201501017.htm. Google Scholar |
| [11] |
L. Liu, T. Zhang and B. Ru, A flying qualities assessment model based on multiparameter integration, Computer Engineering and Science, 38 (2016), 1262-1268. https://www.sciencedirect.com/science/article/pii/S1389041718302365. Google Scholar |
| [12] |
S. C. Nicolis and J. L. Deneubourg, Emerging patterns and food recruitment in ants: An analytical study, Journal of Theoretical Biology, 198 (1999), 575-592. https://www.sciencedirect.com/science/article/pii/S0022519399909347. Google Scholar |
| [13] |
M. W. P. Savelsbergh,
Local search in routing problems with time windows, Annals of Operations Research, 4 (1985), 285-305.
doi: 10.1007/BF02022044. |
| [14] |
L. Santos, J. Coutinho-Rodrigues and J. R. Current, An improved ant colony optimization based algorithm for the capacitated arc routing problem, Transportation Research Part B: Methodological, 44 2010,246-266. https://www.sciencedirect.com/science/article/pii/S0191261509000836. Google Scholar |
| [15] |
T. Stützle and H. H. Hoos, MAX-MIN ant system, Future Generation Computer Systems, 16 (2000), 889-914. https://www.sciencedirect.com/science/article/pii/S0167739X00000431. Google Scholar |
| [16] |
M. Yu, S. Li, M Kong, J. Song and G. Ren, Comparison of advantages and disadvantages among various algorithms in logisticspath designTaking H-group as an example, Cognitive Systems Research, 52(2018) 843-852. https://www.sciencedirect.com/science/article/pii/S1389041718302365.
doi: 10.1016/j.cogsys.2018.08.014. |
| [17] |
M. Yu, J. Song, D. Zhao and G. Ren, Management of expressway service area based on integrated optimization, Cognitive Systems Research, 52 (2018) 875-881. https://www.sciencedirect.com/science/article/pii/S1389041718302390.
doi: 10.1016/j.cogsys.2018.08.013. |
| [18] |
Z. Zhang, Y. Shi and G. Gao, A rough set-based multiple criteria linear programming approach for the medical diagnosis and prognosis, Expert Systems with Applications, 36 (2009), 8932-8937.https://www.semanticscholar.org/paper/A-rough-set-based-multiple-criteria-linear-approach-Zhang-Shi/73209c1d7bc7051a4cd64c059d0edf2cfad86840.
doi: 10.1016/j.eswa.2008.11.007. |
| [19] |
S. Zhou, C. Hu and X. Qiao, et al., A forecasting method for Chinese civil planes attendance rate based on vague sets. Chaos Solitons & Fractals the Interdisciplinary Journal of Nonlinear Science & Nonequilibrium & Complex Phenomena, 89 (2016), 518-526. https://www.sciencedirect.com/science/article/pii/S0960077916300649?via. Google Scholar |
| [20] |
S. Zhou, W. Liu and W. Chang, An improved TOPSIS with weighted hesitant vague information, Chaos Solitons & Fractals the Interdisciplinary Journal of Nonlinear Science & Nonequilibrium & Complex Phenomena, 89 (2016), 47-53. https://www.sciencedirect.com/science/article/pii/S0960077915002970. Google Scholar |
Figure 2.
The simulation results of the basic ant colony algorithm
Figure 3.
The simulation results of the improved ant colony algorithm
Table 1.
Observations' latitude and longitude
| Number | City | Longitude | latitude |
| 1 | Zhengzhou | 113.63E | 34.75N |
| 2 | Anyang | 114.4E | 36.1N |
| 3 | Hebi | 114.3E | 35.75N |
| 4 | Jiaozuo | 113.25E | 35.22N |
| 5 | Kaifeng | 114.32E | 34.8N |
| 6 | Luohe | 114.02E | 33.59N |
| 7 | Luoyang | 112.46E | 34.63N |
| 8 | Nanyang | 112.54E | 33N |
| 9 | Pingdingshan | 113.2E | 33.77N |
| 10 | Puyang | 115.04E | 35.77N |
| 11 | Sanmenxia | 111.21E | 34.78N |
| 12 | Shangqiu | 115.66E | 34.42N |
| 13 | Xinxiang | 113.93E | 35.31N |
| 14 | Xinyang | 114.1E | 32.15N |
| 15 | Xuchang | 113.86E | 34.04N |
| 16 | Zhoukou | 114.7E | 33.63N |
| 17 | Zhumadian | 113.03E | 33.02N |
| Number | City | Longitude | latitude |
| 1 | Zhengzhou | 113.63E | 34.75N |
| 2 | Anyang | 114.4E | 36.1N |
| 3 | Hebi | 114.3E | 35.75N |
| 4 | Jiaozuo | 113.25E | 35.22N |
| 5 | Kaifeng | 114.32E | 34.8N |
| 6 | Luohe | 114.02E | 33.59N |
| 7 | Luoyang | 112.46E | 34.63N |
| 8 | Nanyang | 112.54E | 33N |
| 9 | Pingdingshan | 113.2E | 33.77N |
| 10 | Puyang | 115.04E | 35.77N |
| 11 | Sanmenxia | 111.21E | 34.78N |
| 12 | Shangqiu | 115.66E | 34.42N |
| 13 | Xinxiang | 113.93E | 35.31N |
| 14 | Xinyang | 114.1E | 32.15N |
| 15 | Xuchang | 113.86E | 34.04N |
| 16 | Zhoukou | 114.7E | 33.63N |
| 17 | Zhumadian | 113.03E | 33.02N |
| [1] |
Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028 |
| [2] |
Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021 doi: 10.3934/naco.2021008 |
| [3] |
Jean Dolbeault, Maria J. Esteban, Michał Kowalczyk, Michael Loss. Improved interpolation inequalities on the sphere. Discrete & Continuous Dynamical Systems - S, 2014, 7 (4) : 695-724. doi: 10.3934/dcdss.2014.7.695 |
| [4] |
J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 |
| [5] |
Seung-Yeal Ha, Jinwook Jung, Jeongho Kim, Jinyeong Park, Xiongtao Zhang. A mean-field limit of the particle swarmalator model. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021011 |
| [6] |
Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781 |
| [7] |
Xianchao Xiu, Ying Yang, Wanquan Liu, Lingchen Kong, Meijuan Shang. An improved total variation regularized RPCA for moving object detection with dynamic background. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1685-1698. doi: 10.3934/jimo.2019024 |
| [8] |
Eduardo Casas, Christian Clason, Arnd Rösch. Preface special issue on system modeling and optimization. Mathematical Control & Related Fields, 2021 doi: 10.3934/mcrf.2021008 |
| [9] |
Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 |
| [10] |
Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 |
| [11] |
Luigi C. Berselli, Jishan Fan. Logarithmic and improved regularity criteria for the 3D nematic liquid crystals models, Boussinesq system, and MHD equations in a bounded domain. Communications on Pure & Applied Analysis, 2015, 14 (2) : 637-655. doi: 10.3934/cpaa.2015.14.637 |
| [12] |
Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024 |
| [13] |
Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023 |
2019 Impact Factor: 1.233
Tools
Article outline
Figures and Tables
[Back to Top]