AGH; An Ant Genetic Hybrid Solution to Solve the Multi-model Traveling Salesmen Problem
Keywords:
Multi-model, Optimization, GA, ACS, Hybrid, MMTSP, Traveling salesmen problemAbstract
The concept of multi-model optimization brings the idea of finding all or most of the existing high quality solutions. Recent research on multi-model optimization (MMO) seemed to be using nature inspired algorithms in solving such interesting problems. Multi-model traveling salesman problem is an important but rarely addressed discrete MMO problem. This paper proposes a hybrid algorithm combining the Ant Colony Systems algorithm (ACS) with a modified genetic algorithm (MODGA) to solve multi-model traveling salesman problems (MMTSPs). The concept of the hybrid algorithm divides the solution into two parts where ACS is used to find an average quality solution which is then provided as a threshold to the MODGA to find other quality solutions as much as possible. Benchmark multi-model TSP problems have been used on the new algorithm to test its capability. 70% of the success PR and 0.6% of success SR values indicates the capability of the method solving MMTSPs. The results compared with several state of the art multi-model optimization algorithms showed that the proposed hybrid algorithm performs competitively with these algorithms. As the first approach to solve MMTSPs without niching strategies, improvements will lead the current algorithm to a greater place.
References
‘Multimodal optimization,’ in Introduction to Evolutionary Algorithms. London: Springer London,n2010, pp. 165–191, ISBN: 978-1-84996-129-5.nDOI: 10.1007/978- 1- 84996- 129- 5_5. [Online]. Available: https://doi.org/10.1007/ 978-1-84996-129-5_5
J.Barrera and C. A. C. Coello, ‘A review of particle swarm optimization methods used for multimodal optimization,’ Innovations in swarm intelligence, pp. 9–37, 2009
B. Boˇskovi´c and J. Brest, ‘Clustering and differential evolution for multimodal optimization,’ in 2017 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2017, pp. 698–705
K. Deb, ‘Genetic algorithms in multimodal function optimization,’ Ph.D. dissertation, Clearinghouse for Genetic Algorithms, Department of Engineering Mechanics, 1989
N. Glibovets and N. Gulayeva, ‘A review of niching genetic algorithms for multimodal function optimization,’ Cybernetics and Systems Analysis, vol. 49, no. 6, pp. 815–820, 2013.
J. K. Lenstra and A. R. Kan, ‘Some simple applications of the travelling salesman problem,’ Journal of the Operational Research Society, vol. 26, no. 4, pp. 717–733, 1975
B. Gavish and S. C. Graves, ‘The travelling salesman problem and related problems,’ 1978.
G. Laporte, A. Asef-Vaziri and C. Sriskandarajah, ‘Some applications of the generalized travelling salesman problem,’ Journal of the Operational Research Society, vol. 47, no. 12, pp. 1461–1467, 1996
P. Siarry, A. P´etrowski and M. Bessaou, ‘Amultipopulation genetic algorithm aimed at multimodal optimization,’ Advances in Engineering Software, vol. 33, no. 4, pp. 207–213, 2002.
B.-Y. Qu, P. N. Suganthan and J.-J. Liang, ‘Differential evolution with neighborhood mutation for multimodal optimization,’ IEEE transactions on evolutionary computation, vol. 16, no. 5, pp. 601–614, 2012
R. Thomsen, ‘Multimodal optimization using crowding based differential evolution,’ in Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No. 04TH8753), IEEE, vol. 2, 2004, pp. 1382–1389
M. Preuss, Multimodal optimization by means of evolutionary algorithms. Springer, 2015.
P. D. Justesen, ‘Multi-objective optimization using evolutionary algorithms,’ University of Aarhus, Department of Computer Science, Denmark, vol. 33, 2009.
J. R¨onkk¨onen et al., ContinuousMultimodal Global Optimization with Differential Evolution-Based Methods. Lappeenranta University of Technology, 2009
B. L. Miller and M. J. Shaw, ‘Genetic algorithms with dynamic niche sharing for multimodal function optimization,’ in Proceedings of IEEE international conference on evolutionary computation, IEEE, 1996, pp. 786–791.
M. Dorigo and L. M. Gambardella, ‘Ant colony system: A cooperative learning approach to the traveling salesman problem,’ IEEE Transactions on evolutionary computation, vol. 1, no. 1, pp. 53–66, 1997
P. Larranaga, C. M. H. Kuijpers, R. H. Murga, I. Inza and S. Dizdarevic, ‘Genetic algorithms for the travelling salesman problem: A review of representations and operators,’ Artificial Intelligence Review, vol. 13, no. 2, pp. 129–170, 1999.
R. L. Karg and G. L. Thompson, ‘A heuristic approach to solving travelling salesman problems,’ Management science, vol. 10, no. 2, pp. 225–248, 1964.
D. Angus, ‘Crowding population-based ant colony optimization for the multi-objective travelling salesman problem,’ in 2007 IEEE Symposium on Computational Intelligence in Multi-Criteria Decision- Making, IEEE, 2007, pp. 333–340
C. Changdar, G. Mahapatra and R. K. Pal, ‘An efficient genetic algorithm for multi-objective solid travelling salesman problem under fuzziness,’ Swarm and Evolutionary Computation, vol. 15, pp. 27–37, 2014.
S. Ronald, ‘Finding multiple solutions with an evolutionary algorithm,’ in Proceedings of 1995 IEEE International Conference on Evolutionary Computation,IEEE, vol. 2, 1995, pp. 641–646
X. Lin, W. Luo and P. Xu, ‘Differential evolution for multimodal optimization with species by nearest better clustering,’ IEEE transactions on cybernetics, 2019
D. Angus, ‘Niching for population-based ant colony optimization,’ in 2006 Second IEEE International Conference on e-Science and Grid Computing (e-Science’06), IEEE, 2006, pp. 115–115
X.-C. Han, H.-W. Ke, Y.-J. Gong, Y. Lin, W.-L. Liu and J. Zhang, ‘Multimodal optimization of traveling salesman problem: A niching ant colony system,’ in Proceedings of the Genetic and Evolutionary Computation Conference Companion, 2018, pp. 87–88.
T. Huang, Y.-J. Gong and J. Zhang, ‘Seeking multiple solutions of combinatorial optimization problems: A proof of principle study,’ in 2018 IEEE Symposium Series on Computational Intelligence (SSCI), IEEE, 2018, pp. 1212–1218
T. Huang, Y.-J. Gong, S. Kwong, H. Wang and J. Zhang, ‘A niching memetic algorithm for multisolution traveling salesman problem,’ IEEE Transactions on Evolutionary Computation, vol. 24, no. 3, pp. 508–522, 2019.
X. Li, M. G. Epitropakis, K. Deb and A. Engelbrecht, ‘Seeking multiple solutions: An updated survey on niching methods and their applications,’ IEEE Transactions on Evolutionary Computation, vol. 21, no. 4, pp. 518–538, 2016.
C. R. Houck, J. Joines and M. G. Kay, ‘A genetic algorithm for function optimization: A matlab implementation,’ Ncsu-ie tr, vol. 95, no. 09, pp. 1–10, 1995.
G. C. Dandy, A. R. Simpson and L. J. Murphy, ‘An improved genetic algorithm for pipe network optimization,’ Water resources research, vol. 32, no. 2, pp. 449–458, 1996
J. Horn, N. Nafpliotis and D. E. Goldberg, ‘A niched pareto genetic algorithm for multi objective optimization, ‘in Proceedings of the first IEEE conference on evolutionary computation. IEEE world congress on computational intelligence, Ieee, 1994, pp. 82–87
P. C. Chu and J. E. Beasley, ‘A genetic algorithm for the multidimensional knapsack problem,’ Journal of heuristics, vol. 4, no. 1, pp. 63–86, 1998
F. H. Khan, N. Khan, S. Inayatullah and S. T. Nizami, ‘Solving tsp problem by using genetic algorithm,’International Journal of Basic & Applied Sciences, vol. 9, no. 10, pp. 79–88, 2009
M. Ariyaratne, T. Fernando and S Weerakoon, ‘A hybrid algorithm to solve multi-model optimization problems based on the particle swarm optimization with a modified firefly algorithm,’ in Proceedings of the Future Technologies Conference, Springer, 2020, pp. 308–325
G. Reinelt, ‘TSPLIB–a traveling salesman problem library,’ ORSA Journal on Computing, vol. 3, no. 4, pp. 376 384, 1991.
X. Li, A. Engelbrecht and M. G. Epitropakis, ‘Benchmark functions for cec’2013 special session and competition on niching methods for multimodal function optimization,’ RMIT University, Evolutionary Computation and Machine Learning Group, Australia, Tech. Rep, 2013.
F. Wilcoxon, ‘Individual comparisons by ranking methods,’ in Breakthroughs in statistics, Springer, 1992, pp. 196–202.
M. Hollander, D. A. Wolfe and E. Chicken, Nonparametric statistical methods. John Wiley & Sons, 2013, vol. 751
