Autosoft Journal

Online Manuscript Access


Reactive max-min ant system with recursive local search and its application to TSP and QAP


Authors



Abstract

Ant colony optimization is a successful metaheuristic for solving combinatorial optimization problems. However, the drawback of premature exploitation arises in ant colony optimization when coupled with local searches, in which the neighborhood2019s structures of the search space are not completely traversed. This paper proposes two algorithmic components for solving the premature exploitation, i.e. the reactive heuristics and recursive local search technique. The resulting algorithm is tested on two well-known combinatorial optimization problems arising in the artificial intelligence problems field and compared experimentally to six (6) variants of ACO with local search. Results showed that the enhanced algorithm outperforms the six ACO variants.


Keywords


Pages

Total Pages: 8
Pages: 127-134

DOI
10.1080/10798587.2016.1177914


Manuscript ViewPdf Subscription required to access this document

Obtain access this manuscript in one of the following ways


Already subscribed?

Need information on obtaining a subscription? Personal and institutional subscriptions are available.

Already an author? Have access via email address?


Published

Volume: 23
Issue: 1
Year: 2016

Cite this document


References

Battiti R. Reactive search and intelligent optimization

Blum, Christian et al. "Hybrid Metaheuristics in Combinatorial Optimization: A Survey." Applied Soft Computing 11.6 (2011): 4135-4151. Crossref. Web. https://doi.org/10.1016/j.asoc.2011.02.032

Burkard, Rainer E., Stefan E. Karisch, and Franz Rendl. Journal of Global Optimization 10.4 (1997): 391-403. Crossref. Web. https://doi.org/10.1023/A:1008293323270

Chandra Mohan, B., and R. Baskaran. "A Survey: Ant Colony Optimization Based Recent Research and Implementation on Several Engineering Domain." Expert Systems with Applications 39.4 (2012): 4618-4627. Crossref. Web. https://doi.org/10.1016/j.eswa.2011.09.076

Chen, Shyi-Ming, and Chih-Yao Chien. "Solving the Traveling Salesman Problem Based on the Genetic Simulated Annealing Ant Colony System with Particle Swarm Optimization Techniques." Expert Systems with Applications 38.12 (2011): 14439-14450. Crossref. Web. https://doi.org/10.1016/j.eswa.2011.04.163

Cheng, Chi-Bin, and Chun-Pin Mao. "A Modified Ant Colony System for Solving the Travelling Salesman Problem with Time Windows." Mathematical and Computer Modelling 46.9-10 (2007): 1225-1235. Crossref. Web. https://doi.org/10.1016/j.mcm.2006.11.035

Črepinšek, Matej, Shih-Hsi Liu, and Marjan Mernik. "Exploration and Exploitation in Evolutionary Algorithms." ACM Computing Surveys 45.3 (2013): 1-33. Crossref. Web. https://doi.org/10.1145/2480741.2480752

Derrac, Joaquín et al. "A Practical Tutorial on the Use of Nonparametric Statistical Tests as a Methodology for Comparing Evolutionary and Swarm Intelligence Algorithms." Swarm and Evolutionary Computation 1.1 (2011): 3-18. Crossref. Web. https://doi.org/10.1016/j.swevo.2011.02.002

Dorigo, Marco et al., eds. "Ant Colony Optimization and Swarm Intelligence." Lecture Notes in Computer Science (2004): n. pag. Crossref. Web. https://doi.org/10.1007/b99492

Gendreau, Michel, and Jean-Yves Potvin, eds. "Handbook of Metaheuristics." International Series in Operations Research & Management Science (2010): n. pag. Crossref. Web. https://doi.org/10.1007/978-1-4419-1665-5

Dorigo, M., V. Maniezzo, and A. Colorni. "Ant System: Optimization by a Colony of Cooperating Agents." IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics) 26.1 (1996): 29-41. Crossref. Web. https://doi.org/10.1109/3477.484436

Gambardella, L.M., R. Montemanni, and D. Weyland. "Coupling Ant Colony Systems with Strong Local Searches." European Journal of Operational Research 220.3 (2012): 831-843. Crossref. Web. https://doi.org/10.1016/j.ejor.2012.02.038

Liu X. Journal of Computational Information Systems

López-Ibáñez, Manuel, and Thomas Stützle. "An Experimental Analysis of Design Choices of Multi-Objective Ant Colony Optimization Algorithms." Swarm Intelligence 6.3 (2012): 207-232. Crossref. Web. https://doi.org/10.1007/s11721-012-0070-7

Pellegrini P. Tuning MAX—MIN ant system with off-line and on-line methods

Reinelt, Gerhard. "TSPLIB—A Traveling Salesman Problem Library." ORSA Journal on Computing 3.4 (1991): 376-384. Crossref. Web. https://doi.org/10.1287/ijoc.3.4.376

Solnon, Christine, and Narendra Jussien, eds. "Ant Colony Optimization and Constraint Programming." (2013): n. pag. Crossref. Web. https://doi.org/10.1002/9781118557563

Stützle, T. (1999). Local search algorithms for combinatorial problems: Analysis, improvements, and new applications . Unpublished doctoral dissertation. Technische Universit, Darmstadt, German.

Stützle, Thomas, and Holger H. Hoos. "- Ant System." Future Generation Computer Systems 16.8 (2000): 889-914. Crossref. Web. https://doi.org/10.1016/S0167-739X(00)00043-1

Stützle T. Wiley Encyclopedia of Operations Research and Management Science

UÄŸur, Aybars, and DoÄŸan Aydin. "An Interactive Simulation and Analysis Software for Solving TSP Using Ant Colony Optimization Algorithms." Advances in Engineering Software 40.5 (2009): 341-349. Crossref. Web. https://doi.org/10.1016/j.advengsoft.2008.05.004

Wang, Hongwei et al. "A Novel Aco-Based Multicast Path Algorithm In Hypercube Networks." Intelligent Automation & Soft Computing 17.5 (2011): 541-549. Crossref. Web. https://doi.org/10.1080/10798587.2011.10643168

Yang, Jinhui et al. "An Ant Colony Optimization Method for Generalized TSP Problem." Progress in Natural Science 18.11 (2008): 1417-1422. Crossref. Web. https://doi.org/10.1016/j.pnsc.2008.03.028

JOURNAL INFORMATION


ISSN PRINT: 1079-8587
ISSN ONLINE: 2326-005X
DOI PREFIX: 10.31209
10.1080/10798587 with T&F
IMPACT FACTOR: 0.652 (2017/2018)
Journal: 1995-Present




CONTACT INFORMATION


TSI Press
18015 Bullis Hill
San Antonio, TX 78258 USA
PH: 210 479 1022
FAX: 210 479 1048
EMAIL: tsiepress@gmail.com
WEB: http://www.wacong.org/tsi/