A Fractional-Order Weighted and Self-Adaptive Max-Min Ant System with 3-Opt Algorithm for Traveling Salesman Problem

Shushu Chen; Yifei Pu

doi:doi:10.11648/j.ijiis.20160504.11

| Peer-Reviewed

A Fractional-Order Weighted and Self-Adaptive Max-Min Ant System with 3-Opt Algorithm for Traveling Salesman Problem

Shushu Chen, Yifei Pu

Published in International Journal of Intelligent Information Systems (Volume 5, Issue 4)

Received: 8 May 2016 Accepted: 31 May 2016 Published: 21 June 2016

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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.

Published in	International Journal of Intelligent Information Systems (Volume 5, Issue 4)
DOI	10.11648/j.ijiis.20160504.11
Page(s)	48-54
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2016. Published by Science Publishing Group

Keywords

Self-Adaptive, Max-Min Ant System, 3-Opt Algorithm, Fractional-Order, Tsp

References

[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.

Cite This Article

Plain Text BibTeX RIS

APA Style

Shushu Chen, Yifei Pu. (2016). 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, 5(4), 48-54. https://doi.org/10.11648/j.ijiis.20160504.11

Copy | Download

ACS Style

Shushu Chen; Yifei Pu. A Fractional-Order Weighted and Self-Adaptive Max-Min Ant System with 3-Opt Algorithm for Traveling Salesman Problem. Int. J. Intell. Inf. Syst. 2016, 5(4), 48-54. doi: 10.11648/j.ijiis.20160504.11

Copy | Download

AMA Style

Shushu Chen, Yifei Pu. A Fractional-Order Weighted and Self-Adaptive Max-Min Ant System with 3-Opt Algorithm for Traveling Salesman Problem. Int J Intell Inf Syst. 2016;5(4):48-54. doi: 10.11648/j.ijiis.20160504.11

Copy | Download

@article{10.11648/j.ijiis.20160504.11,
  author = {Shushu Chen and Yifei Pu},
  title = {A Fractional-Order Weighted and Self-Adaptive Max-Min Ant System with 3-Opt Algorithm for Traveling Salesman Problem},
  journal = {International Journal of Intelligent Information Systems},
  volume = {5},
  number = {4},
  pages = {48-54},
  doi = {10.11648/j.ijiis.20160504.11},
  url = {https://doi.org/10.11648/j.ijiis.20160504.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ijiis.20160504.11},
  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.},
 year = {2016}
}

Copy | Download

TY  - JOUR
T1  - A Fractional-Order Weighted and Self-Adaptive Max-Min Ant System with 3-Opt Algorithm for Traveling Salesman Problem
AU  - Shushu Chen
AU  - Yifei Pu
Y1  - 2016/06/21
PY  - 2016
N1  - https://doi.org/10.11648/j.ijiis.20160504.11
DO  - 10.11648/j.ijiis.20160504.11
T2  - International Journal of Intelligent Information Systems
JF  - International Journal of Intelligent Information Systems
JO  - International Journal of Intelligent Information Systems
SP  - 48
EP  - 54
PB  - Science Publishing Group
SN  - 2328-7683
UR  - https://doi.org/10.11648/j.ijiis.20160504.11
AB  - 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.
VL  - 5
IS  - 4
ER  -

Copy | Download

Author Information

Shushu Chen

College of Computer Science, Sichuan University, Chengdu, China
Yifei Pu

College of Computer Science, Sichuan University, Chengdu, China

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Shushu Chen, Yifei Pu. (2016). 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, 5(4), 48-54. https://doi.org/10.11648/j.ijiis.20160504.11

Copy | Download

ACS Style

Shushu Chen; Yifei Pu. A Fractional-Order Weighted and Self-Adaptive Max-Min Ant System with 3-Opt Algorithm for Traveling Salesman Problem. Int. J. Intell. Inf. Syst. 2016, 5(4), 48-54. doi: 10.11648/j.ijiis.20160504.11

Copy | Download

AMA Style

Shushu Chen, Yifei Pu. A Fractional-Order Weighted and Self-Adaptive Max-Min Ant System with 3-Opt Algorithm for Traveling Salesman Problem. Int J Intell Inf Syst. 2016;5(4):48-54. doi: 10.11648/j.ijiis.20160504.11

Copy | Download

@article{10.11648/j.ijiis.20160504.11,
  author = {Shushu Chen and Yifei Pu},
  title = {A Fractional-Order Weighted and Self-Adaptive Max-Min Ant System with 3-Opt Algorithm for Traveling Salesman Problem},
  journal = {International Journal of Intelligent Information Systems},
  volume = {5},
  number = {4},
  pages = {48-54},
  doi = {10.11648/j.ijiis.20160504.11},
  url = {https://doi.org/10.11648/j.ijiis.20160504.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ijiis.20160504.11},
  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.},
 year = {2016}
}

Copy | Download

TY  - JOUR
T1  - A Fractional-Order Weighted and Self-Adaptive Max-Min Ant System with 3-Opt Algorithm for Traveling Salesman Problem
AU  - Shushu Chen
AU  - Yifei Pu
Y1  - 2016/06/21
PY  - 2016
N1  - https://doi.org/10.11648/j.ijiis.20160504.11
DO  - 10.11648/j.ijiis.20160504.11
T2  - International Journal of Intelligent Information Systems
JF  - International Journal of Intelligent Information Systems
JO  - International Journal of Intelligent Information Systems
SP  - 48
EP  - 54
PB  - Science Publishing Group
SN  - 2328-7683
UR  - https://doi.org/10.11648/j.ijiis.20160504.11
AB  - 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.
VL  - 5
IS  - 4
ER  -

Copy | Download