Binary ant algorithm

ABSTRACT

When facing dynamic optimization problems the goal is no longer to find the extrema, but to track their progression through the space as closely as possible. Over these kind of over changing, complex and ubiquitous real-world problems, the explorative-exploitive subtle counterbalance character of our current state-of-the-art search algorithms should be biased towards an increased explorative behavior. While counterproductive in classic problems, the main and obvious reason of using it in severe dynamic problems is simple: while we engage ourselves in exploiting the extrema, the extrema moves elsewhere. In order to tackle this subtle compromise, we propose a novel algorithm for optimization in dynamic binary landscapes, stressing the role of negative feedback mechanisms. The Binary Ant Algorithm (BAA) mimics some aspects of social insects' behavior. Like Ant Colony Optimization (ACO), BAA acts by building pheromone maps over a graph of possible trails representing pseudo-solutions of increasing quality to a specific optimization problem. Main differences rely on the way this search space is represented and provided to the colony in order to explore/exploit it, while and more important, we enrol in providing strong evaporation to the problem-habitat. By a process of pheromone reinforcement and evaporation the artificial insect's trails over the graph converge to regions near the ideal solution of the optimization problem. Over each generation, positive feedbacks made available by pheromone reinforcement consolidate the best solutions found so far, while enhanced negative feedbacks given by the evaporation mechanism provided the system with population diversity and fast self-adaptive characteristics, allowing BAA to be particularly suitable for severe complex dynamic optimization problems. Experiments made with some well known test functions frequently used in the Evolutionary Algorithms' research field illustrate the efficiency of the proposed method. BAA was also compared with other algorithms, proving to be more able to track fast moving extrema on several test problems.

REFERENCES

• 1: Peter J. Angeline, Tracking Extrema in Dynamic Environments, Proceedings of the 6th International Conference on Evolutionary Programming VI, p.335-345, April 13-16, 1997
• 2: Thomas Bäck, Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms, Oxford University Press, Oxford, 1996
• 3: Shummet Baluja, Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, Carnegie Mellon University, Pittsburgh, PA, 1994
• 4: Jurgen Branke, Evolutionary Optimization in Dynamic Environments, Kluwer Academic Publishers, Norwell, MA, 1920
• 5: Bullheimer B., Ant Colony Optimization in Vehicle Routing, PhD Thesis, University of Vienna, 1999.
• 6: A. Colorni, M. Dorigo and V. Maniezzo, Distributed Optimization by Ant Colonies, In Proceedings of the 1st European Conference on Artificial Life, F.J. Varela and P. Bourgine (Eds.), MIT Press, Cambridge, MA, 134--142, 1992.
• 7: Colorni, A., Dorigo, M., Maniezzo, V., Trubian, M., Ant System for Job--shop Scheduling, Belgian Journal of Operations Research, Statistics and Computer Science, 34(1): 39--53, 1994.
• 8: Marco Dorigo , Christian Blum, Ant colony optimization theory: a survey, Theoretical Computer Science, v.344 n.2-3, p.243-278, 17 November 2005 [doi>10.1016/j.tcs.2005.05.020]
• 9: Eberhart R. C., Kennedy J., A new optimizer using particle swarm theory, In Proceedings of the 6th International Symposium on Micromachine and Human Science, Nagoya, Japan. pp. 39--43, 1995.
• 10: Fernandes C., Ramos V., Rosa A.C., Self-Regulated Artificial Ant Colonies on Digital Image Habitats, International Journal of Lateral Computing, 2(1): 1--8, 2005.
• 11: Michael Guntsch , Martin Middendorf, Applying Population Based ACO to Dynamic Optimization Problems, Proceedings of the Third International Workshop on Ant Algorithms, p.111-122, September 12-14, 2002
• 12: James Kennedy , Russell C. Eberhart, Swarm intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 13: Kong, M., Tian P. Introducing a Binary Ant Colony Optimization, In Proceedings of the 6th International Workshop on ACO and Swarm Intelligence, LNCS, 4150: 444--451, 2006.
• 14: Vittorio Maniezzo , Alberto Colorni, The Ant System Applied to the Quadratic Assignment Problem, IEEE Transactions on Knowledge and Data Engineering, v.11 n.5, p.769-778, September 1999 [doi>10.1109/69.806935]
• 15: Mitchell M., Holland J., Forrest S., When will a GA outperform Hillclimbing?, Advances in Neural Information Processing Systems, 6: 51--58, 1994.
• 16: Passino, K.M., Biomimicry of Bacterial Foraging for Distributed Optimization and Control, IEEE Control Systems Magazine, 52--67, 2002.
• 17: Ramos V., Merelo J.J., "Self-Organized Stigmergic Document Maps: Environment as a Mechanism for Context Learning", in E. Alba, F. Herrera, J.J. Merelo et al. (Eds.), AEB'2002,-- 1st Spanish Conf. on Evolutionary and Bio--Inspired Algorithms, pp. 284--293, 2002.
• 18: Ramos, V., Fernandes, C., Rosa, A.C., On Self--Regulated Swarms, Societal Memory, Speed and Dynamics, in L.M. Rocha, L.S. Yaeger, M.A. Bedau, D. Floreano, R.L. Goldstone and A. Vespignani (Eds.), Proc. of ALifeX, MIT Press, pp. 393--399, 2006.
• 19: Rocha L., Maguitman A., Huang C., Kaur J., and Narayanan S., An Evolutionary Model of Genotype Editing, In Proceedings of ALifeX, MIT Press, pp. 105--111, 2006.
• 20: Roth M., Wicker S., Asymptotic Pheromone Behavior in Swarm Intelligent MANETs: An Analytical analysis of Routing Behavior, Sixth IFIP IEEE International Conference on Mobile and Wireless Communications Network, 2004.
• 21: Socha K., Sampels M., Manfrin M., Ant Algorithms for the University Course Timetabling problem with regard to the state-of-the-art, In Proceedings of the EvoWorkshops 2003, LNCS, Berlin Springer, 334, 345, 2003.
• 22: Wedde H., Farooq M., Zhang Y., BeeHive: An Efficient Fault Tolerance Routing Algorithm under High Loads Inspired by Honey Bee Behavior, In Proceedings of the 4th International Workshop on Ant Colony and Swarm Intelligence (ANTS 2004), LNCS, 83--94, 2004.
• 23: Xiao J., Li J., Xu Q., Huang W., Lou H., ACS-based Dynamic Optimization for Curing of Polymeric Coating, in AIChE Journal, 52(4): 1410--1422, 2005.
• 24: Zlochin M., Birattari M., Meuleau N., Dorigo M., Model-based search for combinatorial optimization: A critical survey, in Annals of Operations Research, 131:373--395, 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Experimentation

Keywords:
ant algorithms, dynamic optimization, stigmergy, swarm intelligence