Volume 5, Issue 4, August 2016, Page: 48-54
A Fractional-Order Weighted and Self-Adaptive Max-Min Ant System with 3-Opt Algorithm for Traveling Salesman Problem
Shushu Chen, College of Computer Science, Sichuan University, Chengdu, China
Yifei Pu, College of Computer Science, Sichuan University, Chengdu, China
Received: May 8, 2016;       Accepted: May 31, 2016;       Published: Jun. 21, 2016
DOI: 10.11648/j.ijiis.20160504.11      View  3808      Downloads  106
Abstract
In this paper, a Fractional-order weighted and Self-adaptive Max-Min Ant System (FS-MMAS) is proposed to make full use of spatial information of the traveling salesman problem. Furthermore, it is realized so that ants can select next city according to the complex topography. Most advanced algorithms based on Ant Colony Optimization can't take advantage of spatial information during the traverse tour, which easily leads to local minimums. Through the multi-scale and self-adaptive search, ants can take advantage of information which contributes to finding the global optimization. Finally, the 3-Opt algorithm is used to improve local solutions. The performance of proposed method was investigated on eight different benchmark problems taken from a literature and proved to be better than other well-known methods in terms of solution quality and robustness.
Keywords
Self-Adaptive, Max-Min Ant System, 3-Opt Algorithm, Fractional-Order, Tsp
To cite this article
Shushu Chen, Yifei Pu, A Fractional-Order Weighted and Self-Adaptive Max-Min Ant System with 3-Opt Algorithm for Traveling Salesman Problem, International Journal of Intelligent Information Systems. Vol. 5, No. 4, 2016, pp. 48-54. doi: 10.11648/j.ijiis.20160504.11
Copyright
Copyright © 2016 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Reference
[1]
G. Laporte, The Traveling Salesman Problem – an overview of exact and approximate algorithms, Eur. J. Oper. Res. 59, 1992, pp. 231–247.
[2]
Wikipedia, Traveling Salesman Problem. Available: http://en.wikipedia.org/wiki/Travelling_salesman_problem
[3]
X. T. Geng, Z. H. Chen, W. Yang, D. Q. Shi, K. Zhao, "Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search", Appl. Soft Comput. 11, 2011, pp. 3680–3689.
[4]
J. Grefenstette, R. Gopal, B. Rosmaita, D. Van Gucht, "Genetic algorithms for the traveling salesman problem", in Proceedings of the First International Conference on Genetic Algorithms and their Applications, Lawrence Erlbaum, NJ, 1985, pp. 160–168.
[5]
Dorigo. M, Maniezzo. V, Colorni. A, "Ant system: optimization by a colony of cooperating agents", IEEE Trans. Syst. Man Cybern. B 26, 1996, pp. 29–41.
[6]
X. H. Shi, Y. C. Liang, H. P. Lee, C. Lu, Q. X. Wang, "Particle swarm optimization based algorithms for TSP and generalized TSP", Inf. Process. Lett. 103, 2007, pp. 169–176.
[7]
Dorigo, M., & Gambardella, L. M, "Ant Colony System: A cooperating learning approach to the traveling salesman problem", IEEE Transactions on Evolutionary Computation, 1 January 1997, pp. 53–66.
[8]
Bullnheimer, B., Hartl, R. F., & Strauss, C., "A new rank-based version of the Ant System: A computational study", Central European Journal for Operations Research and Economics, 7 January 1996, pp. 25–38.
[9]
Stutzle, T., & Hoos, H. H., "Max–min ant system", Future Generation Computer Systems, 16 August 2000, pp. 889–914.
[10]
M. Dorigo, V. Maniezzo, A. Colorni, V. Maniezzo, Positive Feedback as a Search Strategy, 1991.
[11]
Oldham K B, Spanier J., The Fractional Calculus, New York and London: Academic Press, 1974.
[12]
Wikipedia, 3-Opt Algorithm. Available: http://en.wikipedia.org/wiki/3-Opt
[13]
G. Reinelt, "TSPLIB—a traveling salesman problem library", ORSA J. Comput. 3, 1991, pp. 376–384.
[14]
C. F. Tsai, C. W. Tsai, C. C. Tseng, "A new hybrid heuristic approach for solving large traveling salesman problem", Inf. Sci. 166, 2004, pp. 67–81.
[15]
R. Pasti, L. N. De Castro, "A neuro-immune network for solving the traveling sales-man problem", in International Joint Conference on Neural Networks, 2006. IJCNN’06, IEEE, 2006, pp. 3760–3766.
[16]
T. A. S. Masutti, L. N. de Castro, "A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem", Inf. Sci. 179, 2009, pp. 1454–1468.
[17]
S. M. Chen, C. Y. Chien, "Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques", Expert Syst. Appl. 38, 2011, pp. 14439–14450.
[18]
K. Jun-man, Z. Yi, "Application of an improved Ant Colony Optimization on generalized Traveling Salesman Problem", Energy Proc. 17, 2012, pp. 319–325.
[19]
Z. A. Othman, A. I. Srour, A. R. Hamdan, P. Y. Ling, "Performance water flow-like algorithm for TSP by improving its local search", Int. J. Adv. Comput. Technol. 5, 2013.
[20]
M. Peker, B. Sen, P. Y. Kumru, "An efficient solving of the traveling salesman problem: the ant colony system having parameters optimized by the Taguchi method", Turk. J. Electr. Eng. Comput. 21, 2013, pp. 2015–2036.
[21]
M. Gunduz, M. S. Kiran, E. Ozceylan, "A hierarchic approach based on swarm intelligence to solve traveling salesman problem", Turk. J. Electr. Eng. Comput. Sci., 2014.
Browse journals by subject