Block Based Imperial Competitive Algorithm with Greedy Search for Traveling Salesman Problem

Authors: Meng-Hui Chen, Chiao-Wei Yu, Pei-Chann Chang

Abstract:

Imperial competitive algorithm (ICA) simulates a multi-agent algorithm. Each agent is like a kingdom has its country, and the strongest country in each agent is called imperialist, others are colony. Countries are competitive with imperialist which in the same kingdom by evolving. So this country will move in the search space to find better solutions with higher fitness to be a new imperialist. The main idea in this paper is using the peculiarity of ICA to explore the search space to solve the kinds of combinational problems. Otherwise, we also study to use the greed search to increase the local search ability. To verify the proposed algorithm in this paper, the experimental results of traveling salesman problem (TSP) is according to the traveling salesman problem library (TSPLIB). The results show that the proposed algorithm has higher performance than the other known methods.

Keywords: Traveling Salesman Problem, Artificial Chromosomes, Greedy Search, Imperial Competitive Algorithm.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1093366

References:

[1] M. Mavrovouniotis and S. Yang, "Ant colony optimization with direct communication for the traveling salesman problem,” in Proc. of the 2010 UK Workshop on Computational Intelligence (UKCI2010),2010.
[2] A. Shakeel, S. Yang. "A hybrid genetic algorithm and inver over approach for the travelling salesman problem,” Evolutionary Computation (CEC), 2010 IEEE Congress on. IEEE, pp. 1-8,2010.
[3] J. T. Tsai, W. H. Ho, T. K. Liu, and J. H. Chou, "Improved immune algorithm for global numerical optimization and job-shop scheduling problems,” Applied Mathematics and Computation, Vol. 194, pp. 406-424, Dec. 2007.
[4] J. S. Chun, H. K. Jung and S. Y. Hahn, "A Study on Comparison of Optimization Performances between Immune Algorithm and other Heuristic Algorithms,” IEEE Transactions on Magnetics, vol. 34, No. 5, Sept. 1998.
[5] J. H. Holland, "Genetic Algorithms and the Optimal Allocation of Trials,” SIAM J. Comput, vol. 2, pp. 88-105, 1973.
[6] D. E. Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning (Book style),” Boston, MA: Addison-Wesley, 1989.
[7] Atashpaz-Gargari, E. Lucas, C. 2007. Imperialist Competitive Algorithm: An algorithm for optimization inspired by imperialistic competition. IEEE Congress on Evolutionary Computation, pp.4661–4667.
[8] Shirin Nozarian and Majid Vafaei Jahan , "A Novel Memetic Algorithm with Imperialist Competition as Local Search,” IACSIT Hong Kong Conferences vol. 30 (2012).
[9] B. Selman, & H. A. Kautz, "An empirical study of greedy local search for satisfiability testing,” AAAI, vol.93, pp.46-51, 1993.
[10] X. Geng, Z. Chen, W. Yang, D. Shi, K. Zhao, "Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search,” Applied Soft Computing, vol.11, pp. 3680-3689,2011.
[11] Z. Wang, H. Duan, X. Zhang, "An Improved Greedy Genetic Algorithm for Solving Travelling Salesman Problem,” Natural Computation, ICNC'09 Fifth International Conference on, vol.5, pp.374-378, 2009.
[12] Huang, Wei-Hsiu Chang, Pei-Chann, Wang, Lien-Chun, "A Fast Block-based Evolutional Algorithm for Combinatorial Problems,” World Academy of Science, Engineering and Technology 67 (2012).
[13] R. Pasti, L. N. de. Castro, "A Neuro-immune network for solving the traveling salesman problem,” Proceedings of International Joint Conference on Neural Networks, vol. 6, pp. 3760-3766, 2006.
[14] S. Somhom, A. Modares, T. Enkawa, "A self-organizing model for the travelling salesman problem,” Journal of the Operational Research Society, vol. 48, pp. 919-928, 1997.