International Journal of Modern Education and Computer Science (IJMECS)
IJMECS Vol. 5, No. 4, 8 Apr. 2013
Cover page and Table of Contents: PDF (size: 429KB)
Author(s)
Index Terms
Stigmergic, Forage, Pheromone, Combitorial Optimisation, GA, Artificial Ant, AI.
Abstract
Ant Algorithms are techniques for optimizing which were coined in the early 1990’s by M. Dorigo. The techniques were inspired by the foraging behavior of real ants in the nature. The focus of ant algorithms is to find approximate optimized problem solutions using artificial ants and their indirect decentralized communications using synthetic pheromones. In this paper, at first ant algorithms are described in details, then transforms to computational optimization techniques: the ACO metaheuristics and developed ACO algorithms. A comparative study of ant algorithms also carried out, followed by past and present trends in AAs applications. Future prospect in AAs also covered in this paper. Finally a comparison between AAs with well-established machine learning techniques were focused, so that combining with machine learning techniques hybrid, robust, novel algorithms could be produces for outstanding result in future.
Cite This Paper
Sangita Roy, Sheli Sinha Chaudhuri, "Bio-inspired Ant Algorithms: A review", International Journal of Modern Education and Computer Science (IJMECS), vol.5, no.4, pp. 25-35, 2013. DOI:10.5815/ijmecs.2013.04.04
Reference
[1]R.J.Mullen, D. Monekosso, S. Barman, P.Remagnino, “A review of ant algorithms”, R.J.Mullen, D. Monekosso, S. Barman, P.Remagnino. DOI:10.1016/j.eswa.2009.01.020
[2]M. Dorigo, V. Maniezzo, Ant System & A. Colorni, Ant System:optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1):29-41, 1996. DOI:10.1109/3477.484436
[3]M. Dorigo, System Elitist Ant, Optimization, Learning and Natural Algorithms. Ph.D.Thesis, Politecnico di Milano, Italy, [in Italian], 1992.; M.Dorigo, V. Maniezzo and A. Colorni, Ant System: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1), 29-41, 1996. DOI:10.1109/3477.484436
[4]L.M. Gambardella and M. Dorigo, Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem. Proceedings of ML-95, Twelfth International Conference on Machine Learning, Tahoe City, CA, A. Prieditis and S. Russell (Eds.), Morgan Kaufmann, 252-260,1995
[5]M. Dorigo, Ant Colony System& L.M. Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1(1):53-66, 1997. DOI:10.1109/4235.585892
[6]T. Stützle, Max-Min Ant Systemand H. H. Hoos, MAX-MIN Ant System, Future Generation Computer Systems. 16(8):889--914, 2000. DOI:10.1016/S0167-739X(00)00043-1
[7]B. Bullnheimer, R. F. Hartl, Rank-based Ant System, and C. Strauss, A New Rank Based Version of the Ant System: a Computational Study,Central European Journal for Operations Research and Economics, 7(1):25-38, 1999.
[8]V. Maniezzo, Ants, Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem, INFORMS Journal on Computing, 11(4), 358-369, 1999. DOI:10.1287/ijoc.11.4.358
[9]C. Blum, A. Roli,Hyper Cube –ACO and M. Dorigo. HC-ACO: The hyper-cube framework for Ant Colony Optimization. In Proceedings of the Fourth Metaheuristics International Conference, volume 2, pages 399-403, 2001. Later, a strongly extended version of this paper has been published in IEEE Transactions on Systems, Man, and Cybernetics -- Part B, 34(2):1161-1172, 2004. DOI:10.1109/TSMCB.2003.821450
[10]M. L. Pilat,T. White, Using Genetic Algorithms to Optimise ACS-TSP,Proceedings of Ant Algorithms,Third International workshop,2002. DOI:10.1007/3-540-45724-0_28
[11]White, T., Pagurek, B. and Oppacher, F. (1998). Connection management using adaptive mobile agents. Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA '98) (Arabnia, H. R., ed), pp. 802{809.CSREA Press.
[12]C.H. Papadimitriou, K.Steiglitz, Combitorial Optimisation: Algorithm and complexity, Prentice Hall, 1982.
[13]E. Bonabeau M., Dorigo, & G. Theraulaz, Swarm Systems: From Natural to Artificial Systems, Oxford University Press,1999.
[14]Xin-She Yang and Suash Deb, Cuckoo search via levy flight, Proc. of f IEEE, 2009. DOI:10.1109/NABIC.2009.5393690
[15]Dorigo M., G. Di Caro and L. M. Gambardella. Ant Algorithms for Discrete Optimization. Artificial Life, 5, 2, pp. 137-172, 1999. DOI:10.1162/106454699568728
[16]S. Kirkpatrick; C. D. Gelatt; M. P. Vecchi, Optimization by Simulated Annealing,Science, New Series, Vol. 220, No. 4598. (May 13, 1983), pp. 671-680.
[17]Fred Glover (1990). "Tabu Search - Part 2". ORSA Journal on Computing 2 (1): 4–32. DOI:10.1287/ijoc.2.1.4
[18]Fred Glover (1989). "Tabu Search - Part 1". ORSA Journal on Computing 1 (2): 190–206. DOI:10.1287/ijoc.1.3.190
[19]Helena R. Lourenco, Olivier C. Martin, Thomas Stuzle,Handbook of Metaheuristics (2002), pp. 321- 353.
[20]S. Gross, S.Aron, J. L. Deneubourg, J. M. Pasteels,Self- organised shortcuts in Argentine ANTS, Springer-Verlag, 1989. DOI:10.1007/BF00462870
[21]G. Di Caro and M. Dorigo. AntNet: A mobile agents approach to adaptive routing.Technical Report 97-12, Universit´e Libre de Bruxelles, 1997.
[22]Bernd Bullnheimer, Richard F. Hartl, Christine Strauß, A New Rank Based Version of the Ant System A Computational Study ,1996.
[23]Lessing, Dumitrescu, & Stutzle, A Comparison Between ACO Algorithms for the Set Covering Problem, ANTS Workshop'04. DOI:10.1007/978-3-540-28646-2_1
[24]Costa D.; Hertz A, Ant can colour graphs, Journal of the operation research society, 1997.
[25]Bernd Bullnheimer, Richard F. Hartl, Christine Strauss, Applying the Ant System to the Vehicle Routing Problem, 1999. DOI:10.1007/978-1-4615-5775-3_20
[26]L. M. Gambardella, É. Taillard, G. Agazzi, A multiple ant colony system for vehicle routing problems with time windows, Mcgraw-Hill'S Advanced Topics In Computer Science Series, 1999.
[27]Luca Maria Gambardellaa, b, Andrea E. Rizzolia, b, Fabrizio Oliveriob,Norman Casagrandea, Alberto V. Donatia, Roberto Montemannia, Enzo Lucibellob, Ant Colony Optimization for vehicle routing in advanced logistics systems,IEEE Transactions2003.
[28]Krzysztof Socha: ACO for Continuous and Mixed- Variable Optimization, ANTS Workshop 2004: 25-36. DOI:10.1007/978-3-540-28646-2_3
[29]Krzysztof Socha, Christian Blum: An ant colony optimization algorithm for continuous optimization: application to feed-forward neural network training. Neural Computing and Applications 16(3): 235-247 (2007). DOI:10.1007/s00521-007-0084-z
[30]Max Manfrin, Mauro Birattari, Thomas St¨utzle, and Marco Dorigo, Parallel Ant Colony Optimization for the Traveling Salesman Problem, ANTS 2006, LNCS 4150, pp. 224–234, 2006.@ Springer-Verlag Berlin Heidelberg 2006. DOI:10.1007/11839088_20
[31]Talbi E-G., Roux O., Fonlupt C., Robillard D., Parallel ant colonies for combinatorial optimization problems, BioSP3 Workshop on Biologically Inspired Solutions to Parallel Processing Systems, in IEEE IPPS/SPDP'99. DOI:10.1007/BFb0097905
[32]Mas, J. and Fernandez, G. (2003). Video shot boundary detection based on color histogram, In TRECVid Workshop.
[33]Fernandez, D.C., 2005. Delineating Fluid-filled region boundaries in optical coherence tomography images of the retina. IEEE Trans. Med. Imag., 24: 929-945. DOI:10.1109/TMI.2005.848655
[34]H. Nezamabadi-Pour, S. Saryazdi, and E. Rashedi, “Edge detection using ant algorithms,” Soft Computing, vol. 10, pp. 623–628, May 2006. DOI:10.1007/s00500-005-0511-y
[35]Ramos, V. and Almeida, F. (2000). Artificial ant colonies in digital image habitats: A mass behavior effect study on pattern recognition, In Dorigo, M., Middendorf, M.,and Stuzle, T., editors, From Ant Colonies to Artificial Ants - 2nd Int. Wkshp. on Ant Algorithms, pages 113–116.
[36]Channa, A. H., Rajpoot, N. M., & Rajpoot, K. M. (2006). Texture segmentation using ant tree clustering. In 2006 IEEE international conference on engineering of intelligent systems, ICEIS 2006 (pp. 1–6). Piscataway: IEEE Press. DOI:10.1109/ICEIS.2006.1703192
[37]Salima Ouadfel, Mohamed Batouche, Unsupervised Image Segmentation Using a Colony of Cooperating Ants, Biologically Motivated Computer Vision Lecture Notes in Computer Science Volume 2525, 2002, pp 109-116 .DOI:10.1007/3-540-36181-2_11
[38]Malisia, A. R. and Tizhoosh, H. R. (2006). Image thresholding using ant colony optimization. In Proceedings of the 3rd Canadian Conference on Computer and Robot Vision (CRV’06). DOI:10.1109/CRV.2006.42
[39]Antonio Plaza, David Valencia, Javier Plaza, Pablo Martinez, Commodity cluster-based parallel processing of hyperspectral imagery,Journal of Parallel and Distributed Computing,Volume 66, Issue 3, March 2006, Pages 345–358. DOI:10.1016/j.jpdc.2005.10.001
[40]Kit Fun Lau , Ken A. Dill, A lattice statistical mechanics model of the conformational and sequence spaces of proteins,Macromolecules, 1989, 22 (10), pp 3986–3997. DOI:10.1021/ma00200a030
[41]Shmygelska A, Hoos H, An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem, BMC Bioinformatics 2005. DOI:10.1186/1471-2105-6-30
[42]Fidanova S. ,3D HP Protein Folding Problem using Ant Algorithm, BioPS’06, October 24-25, III.19-II.26.
[43]Shmygelska A, Hoos H, An Improved Ant Colony Optimisation for the 2D HP Protein folding problem, Springer Berlin, 2003. DOI:10.1007/3-540-44886-1_30
[44]Usama Fayyad, Gregory Piatetsky-Shapiro, and Padhraic Smyth, From Data Mining to Knowledge Discovery in Databases, American Association for Artificial Intelligence. All rights reserved. 0738-4602-1996.
[45]Herbert A.Edelstein (1999): Introduction to Data Mining and Knowledge Discovery, Third dition. U. S. A:Two Crows Corporation, pp: 8-9, 2005.
[46]A. A. Freitas, R. S. Parpinelli, and H. S. Lopes, Ant colony algorithms for data classification, in encyclopedia of Information Science and Technology, M. Khosrou-Pour, Ed., pp. 420–424, IGI Publishing, Hershey, Pa, USA, 2nd edition, 2005. DOI:10.4018/978-1-60566-026-4.ch027
[47]Ji X, Bailey J, Dong G, Mining minimal distinguishing subsequence patterns with gap constraints, In: Proceeding of the 2005 international conference on data mining (ICDM’05), Houston,TX, pp 194–201. DOI:10.1109/ICDM.2005.96
[48]PARPINELL, R.S., LOPES, H.S. and FREITAS, A.A., 2002, Data mining with an ant colony optimization algorithm.IEEE Transaction on Evolutionary Computation, 6, pp.321–332. DOI:10.1109/TEVC.2002.802452
[49]James Smaldon, Alex Alves Freitas, A new version of the ant-miner algorithm discovering unordered rule sets. GECCO 2006: 43-50. DOI:10.1145/1143997.1144004
[50]Smaldon, J. & Freitas, A.A. (2006). A new version of theAnt-Miner algorithm discovering unordered rule sets.Proc. Geneticand Evolutionary Computation Conf. (GECCO-2006), 43-50. San Francisco, CA: MorganKaufmann. DOI:10.1145/1143997.1144004
[51]Cordon,O. et al. (2002) Linguistic modeling by hierarchical systems of linguistic rules.IEEE Trans. Fuzzy Syst., 10, 2–20. DOI:10.1109/91.983275
[52]T. Mitchell, Machine Learning, Handbook on Machine Learning,1997.
[53]Monekosso, N. and Remagnino, P. (2004), The analysis and performance evaluation of the pheromone-Q-learning algorithm. Expert Systems 21(2):80-91. DOI:10.1111/j.1468-0394.2004.00265.x
[54]D. N. Monekosso, P. Remagnino, Chapter “Phe-Q : A pheromone based Q-Learning” in ‘AI 2001: Advances in Artificial Intelligence’, Lecture Notes in Computer Science Edited by Stumptner, M.;Corbett, D.;Brooks, M., Springer, December/10, Adelaide, Australia, pp. 345-356. DOI http://dx.doi.org/10.1007/3-540-45656-2_30 (2001).
[55]Mitchell-Olds T. Genetic constraints on life-history evolution: Quantitative-Trail Loci influencing growth and flowering in Arabidopsis thaliana. Evolution. 1996; 50: 140–145.