Synthetic Genes for Artificial Ants. Diversity in Ant Colony Optimization Algorithms

Authors

  • Sorin C. Negulescu "Lucian Blaga" University of Sibiu, "Hermann Oberth" Faculty of Engineering 10, Victoriei Bd, 550024 Sibiu, Romania
  • Ioan Dzitac "Aurel Vlaicu" University of Arad, Faculty of Exact Sciences, Department of Mathematics-Informatics, Str. Elena Dragoi, Nr. 2, Complex Universitar M, Arad, Romania and R&D Agora Ltd. Oradea [Cercetare Dezvoltare Agora] 8, Piata Tineretului, 410526 Oradea, Romania
  • Alina E. Lascu "Lucian Blaga" University of Sibiu, "Hermann Oberth" Faculty of Engineering 10, Victoriei Bd, 550024 Sibiu, Romania

Keywords:

Ant Colony Optimization, Genetic Algorithms, Multiagent Systems, Stigmergy

Abstract

Inspired from the fact that the real world ants from within a colony are not clones (although they may look alike, they are different from one another), in this paper, the authors are presenting an adapted ant colony optimisation (ACO) algorithm that incorporates methods and ideas from genetic algorithms (GA). Following the first (introductory) section of the paper is presented the history and the state of the art, beginning with the stigmergy and genetic concepts and ending with the latest ACO algorithm variants as multiagent systems (MAS). The rationale and the approach sections are aiming at presenting the problems with current stigmergy-based algorithms and at proposing a (possible - yet to be fully verified) solution to some of the problems ("synthetic genes" for artificial ants). A model used for validating the proposed solution is presented in the next section together with some preliminary simulation results. Some of the conclusions regarding the main subject of the paper (synthetic genes: agents within the MAS with different behaviours) that are closing the paper are: a) the convergence speed of the ACO algorithms can be improved using this approach; b) these "synthetic genes" can be easily implemented (as local variables or properties of the agents); c) the MAS is self-adapting to the specific problem that needs to be optimized.

References

Bărbat B.E, Moiceanu A., Pleșca S., Negulescu S.C., Affordability and Paradigms in Agent-Based Systems, Computer Sc. J. of Moldova, 15, 2(44):178-201, 2007.

Bărbat B.E., Negulescu S.C., From Algorithms to (Sub-)Symbolic Inferences in Multi-Agent Systems. International Journal of Computers, Communications and Control, 1(3):5-12, 2006. http://dx.doi.org/10.15837/ijccc.2006.3.2290

Bărbat B.E., Negulescu S.C., Zamfirescu C.B., Human-Driven Stigmergic Control. Moving the Threshold. In N. Simonov (Ed.), Proc. of the 17th IMACS World Congress (Scientific Computation, Applied Mathematics and Simulation), Paris, pp.86-92, 2005.

Bonabeau E., Dorigo M., Theraulaz G., Swarm Intelligence: From Natural to Artificial Systems, New York: Oxford University Press, 1999.

Deborah Gordon (2008), Dig ants, Retrived 11.2009, from TED. Ideas worth spreading. Web site: http://www.ted.com/talks/lang/eng/deborah_gordon_digs _ants.html.

Dorigo M., Maniezzo V., Colorni A., The Ant System: Optimisation by a Colony of Cooperating Agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B, 26 (1):29-42, 1996.

Dorigo, M., Optimization, Learning and Natural Algorithms, PhD thesis. Italy: Politecnico di Milano, 1992.

Dzitac I., Bărbat B.E., Artificial Intelligence + Distributed Systems = Agents, International Journal of Computers, Communications and Control, 4(1):17-26, 2009. http://dx.doi.org/10.15837/ijccc.2009.1.2410

Dzitac I., Moisil I., Advanced AI Techniques for Web Mining, Proceedings of the 10th WSEAS international conference on Mathematical methods, computational techniques and intelligent systems, Corfu, pp.343-346, 2008.

Gambardella L.M., Di Caro G. (2005), The Ant Colony Optimization (ACO) Metaheuristic: a Swarm Intelligence Framework for Complex Optimization Tasks. Retrived 2008, from University of Bologna: First Summer School on Aspects of Complexity. Web site: http://www.cs.unibo.it/ fioretti/AC/AC2005/ docs/slides_ dicaro.pdf.

Negulescu S.C., Bărbat B.E., Enhancing the effectiveness of simple multi-agent systems through stigmergic coordination, In ICSC-NAISO (Ed.), Fourth International ICSC Symposium on Engineering Of Intelligent Systems (EIS 2004), Canada: ICSC-NAISO Academic Press, pp.149-156, 2004.

Negulescu S.C., Zamfirescu C.B., Bărbat B.E., User-Driven Heuristics for nondeterministic problems. Studies in Informatics and Control (Special issue dedicated to the 2nd Romanian-Hungarian Joint Symp. on Applied Computational Intelligence), 15(3):289-296, 2006.

Negulescu, S.C., Kifor, C.V., Oprean, C., Ant Colony Solving Multiple Constraints Problem: Vehicle Route Allocation. International Journal of Computers, Communications and Control (IJCCC), 3(4):366-373, 2008. http://dx.doi.org/10.15837/ijccc.2008.4.2404

Negulescu, S.C., Oprean, C., Kifor, C.V., Carabulea, I., Elitist ant system for route allocation problem. In Mastorakis, N.E. et al (Ed.), Proceedings of the 8th conference on Applied Informatics and Communications, Greece: World Scientific and Engineering Academy and Society (WSEAS), pp.62-67, 2008.

Secui, D.C., Dzitac, S., Bendea, G.V., Dzitac, I., An ACO Algorithm for Optimal Capacitor Banks Placement in Power Distribution Networks. Studies in Informatics and Control, 18(4):305-314, 2009.

Stützle T., Hoos H.H., MAX-MIN Ant System, Future Generation Computer Systems, 16 (8):889-914, 2000.

Wikipedia, the free encyclopedia (2009), Ant colony optimization. Retrived 11.2009, from WIkipedia. Web site: http://en.wikipedia.org/wiki/ Ant_colony_optimization.

Published

2010-06-01

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.