Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

CAAS: a novel collective action-based ant system algorithm for solving TSP problem

  • Methodologies and Application
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

To solve some problems of ant system algorithm, such as the slow speed of convergence and falling into the phenomenon of “ant colony group loss” easily, we introduce the collective action into the traditional ant system algorithm. Based on the collective action, we propose a novel collective action-based ant system algorithm, namely CAAS, for solving the traveling salesman problem. In the CAAS algorithm, a collective action “optimal solution approval” is defined for ant colony and each ant of the ant colony is assigned a threshold, and then each ant decides whether to join into the collective action according to its own threshold in the iteration process. When all ants approved the same solution, the iteration is stopped and output the final optimal solution. At last, we conduct extensive experiments on six public datasets to verify the performance of the proposed CAAS algorithm. The experimental results show that the CAAS algorithm can get a better solution under a less iteration.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Ahmed ZH (2010) Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator. Int J Biom Bioinform 3(6):96–105

    Google Scholar 

  • Carrabs F, Cerulli R, Speranza MG (2013) A branch-and-bound algorithm for the double TSP with two stacks. Networks 61(1):58–75

    Article  MathSciNet  MATH  Google Scholar 

  • Dorigo M, Gambardella LM (1997) Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evolut Comput 1(1):53–66

    Article  Google Scholar 

  • Dorigo M, Maniezzo V, Colorni A (1991) Ant system: an autocatalytic optimizing process technical report 91-016. Clustering 3(12):340

    Google Scholar 

  • Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybernet Part B: Cybernet 26(1):29–41

    Article  Google Scholar 

  • El-Naggar KM, Alrashidi MR, Alhajri MF, AI-Othman AK (2012) Simulated annealing algorithm for photovoltaic parameters identification. Sol Energy 86(1):266–274

    Article  Google Scholar 

  • Eusuff M, Lansey K, Pasha F (2006) Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization. Eng Optim 38(2):129–154

    Article  MathSciNet  Google Scholar 

  • Fan JH, Wei XL, Wang TX, Lan T, Subramaniam S (2017) Deadline-aware task scheduling in a tiered IoT infrastructure. In: 2017 IEEE global telecommunications conference

  • Fei T, Zhang LY, Li Y, Yang YL, Wang F (2014) The artificial fish swarm algorithm to solve traveling salesman problem. Int Conf Comput Sci Inf Technol (CSAIT) 255:679–685

    Google Scholar 

  • Granovetter M (1978) Threshold models of collective behavior. Am J Sociol 83(6):1420–1443

    Article  Google Scholar 

  • Guan BX, Zhao YH, Sun WJ (2018) Ant colony optimization with an automatic adjustment mechanism for detecting epistatic interactions. Comput Biol Chem 77:354–362

    Article  Google Scholar 

  • He JQ, Sun XJ, Li W, Chen J (2017) A new pheromone update strategy for ant colony optimization. J Intell Fuzzy Syst 32(5):3355–3364

    Article  Google Scholar 

  • Held M, Karp RM (1962) A dynamic programming approach to sequencing problems. J Soc Ind Appl Math 10(1):196–210

    Article  MathSciNet  MATH  Google Scholar 

  • Hsu CC, Wang WY, Chien YH, Hou RY (2018) FPGA implementation of improved ant colony optimization algorithm based on pheromone diffusion mechanism for path planning. J Marine Sci Technol Taiwan 26(2):170–179

    Google Scholar 

  • Ji WD, Wang KQ (2012) An improved particle swarm optimization algorithm. In: 2011 international conference on computer science and network technology, pp 585–589

  • Li DY, Wang XY, Huang PH (2018) A Max-Min ant colony algorithm for fractal dimension of complex networks. Int J Comput Math 95(10):1927–1936

    Article  MathSciNet  Google Scholar 

  • Lim YF, Hong PY, Ramli R, Khalid R (2013) Modified reactive tabu search for the symmetric traveling salesman problems. In: 2013 international conference on mathematical sciences and statistics vol 1557, pp 505–509

  • Liu YX, Gao C, Zhang ZL, Lu YX, Chen S, Liang MX, Tao L (2017) Solving NP-hard problems with physarum-based ant colony system. IEEE-ACM Trans Comput Biol Bioinform 14(1):108–120

    Article  Google Scholar 

  • Luan J, Yao Z, Zhao FT, Song X (2019) A novel method to solve supplier selection problem: hybrid algorithm of genetic algorithm and ant colony optimization. Math Comput Simul 156:294–309

    Article  MathSciNet  Google Scholar 

  • Mohajerani A, Gharavian D (2016) An ant colony optimization based routing algorithm for extending network lifetime in wireless sensor networks. Wirel Netw 22(8):2637–2647

    Article  Google Scholar 

  • Saenphon T, Phimoltares S, Lursinsap C (2014) Combining new fast opposite gradient search with ant colony optimization for solving travelling salesman problem. Eng Appl Artif Intell 35:324–334

    Article  Google Scholar 

  • Sayed S, Nassef M, Badr A, Farag I (2019) A nested genetic algorithm for feature selection in high-dimensional cancer microarray datasets. Expert Syst Appl 121:233–243

    Article  Google Scholar 

  • Shao Q, Xu CC, Zhu Y (2019) Multi-helicopter search and rescue route planning based on strategy optimization algorithm. Int J Pattern Recognit Artif Intell 33(1):1950002

    Article  Google Scholar 

  • Song CH, Lee K, Lee WD (2003) Extended simulated annealing for augmented TSP and multi-salesmen TSP. In: 2003 international joint conference on neural networks vol 3, pp 2340–2343

  • Stutzle T, Hoos H (1997) MAX-MIN ant system and local search for the traveling salesman problem. In: 1997 IEEE international conference on evolutionary computation, pp 309–314

  • Wang L, Xia XH, Cao JH, Liu X, Liu JW (2018) Improved ant colony-genetic algorithm for information transmission path optimization in remanufacturing service system. Chin J Mech Eng 31(1):107

    Article  Google Scholar 

  • Xu P, He G, Li Z, Zhang Z (2018) An efficient load balancing algorithm for virtual machine allocation based on ant colony optimization. Int J Distrib Sens Netw 14(12):1–9

    Article  Google Scholar 

  • Yao BZ, Chen C, Song XL, Yang XL (2019) Fresh seafood delivery routing problem using an improved ant colony optimization. Ann Cper Res 273(1-2):163–186

    Article  MathSciNet  MATH  Google Scholar 

  • Zhang ZL, Gao C, Liu YX, Qian T (2014) A universal optimization strategy for ant colony optimization algorithms based on the Physarum-inspired mathematical model. Bioinspiration Biomim 9(3):036006

    Article  Google Scholar 

  • Zhang JY, Fan XX, Li M, Zhou SS, Liu JM (2018) Ant system with negative for the hospital ward color planning. Wirel Pers Commun 102(2):1589–1601

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. College of Information and Electrical Engineering, China Agricultural University, 17 Tsinghua East Road, Beijing, 100083, China

    Sicong Li, Saihua Cai, Li Li, Ruizhi Sun & Gang Yuan

  2. Scientific Research Base for Integrated Technologies of Precision Agriculture (Animal Husbandry), The Ministry of Agriculture, Beijing, 100083, China

    Ruizhi Sun

Authors
  1. Sicong Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Saihua Cai
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Li Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ruizhi Sun
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Gang Yuan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ruizhi Sun.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Ethical approval

This article does not contain any studies with human participants or animals performed by any of the authors.

Informed consent

Informed consent was obtained from all individual participants included in the study.

Additional information

Communicated by V. Loia.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, S., Cai, S., Li, L. et al. CAAS: a novel collective action-based ant system algorithm for solving TSP problem. Soft Comput 24, 9257–9278 (2020). https://doi.org/10.1007/s00500-019-04452-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-019-04452-y

Keywords

Search

Navigation