nach oben

Soft Computing

Erschienen in:

11.11.2019 | Methodologies and Application

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

verfasst von: Sicong Li, Saihua Cai, Li Li, Ruizhi Sun, Gang Yuan

Erschienen in: Soft Computing | Ausgabe 12/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel On the effects of pseudorandom and quantum-random number generators in soft computing

Nächster Artikel Enhancing differential evolution algorithm with repulsive behavior

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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

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

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

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

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–41CrossRef

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

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

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

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

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

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–3364CrossRef

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

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

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–1936MathSciNetCrossRef

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–120CrossRef

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–309MathSciNetCrossRef

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–2647CrossRef

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–334CrossRef

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–243CrossRef

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):1950002CrossRef

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):107CrossRef

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–9CrossRef

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–186MathSciNetMATHCrossRef

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):036006CrossRef

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–1601CrossRef

Titel: CAAS: a novel collective action-based ant system algorithm for solving TSP problem
verfasst von: Sicong Li
Saihua Cai
Li Li
Ruizhi Sun
Gang Yuan
Publikationsdatum: 11.11.2019
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 12/2020
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-019-04452-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 12/2020

Correction to: On ε-soft topological semigroups

Some new information measures for hesitant fuzzy PROMETHEE method and application to green supplier selection

Clustering data stream with uncertainty using belief function theory and fading function

Modeling and stability analysis methods of neutrosophic transfer functions

De-risking long-term care insurance

A two-layer algorithm based on PSO for solving unit commitment problem