Stigmergic optimization in dynamic binary landscapes

ABSTRACT

Hereafter we introduce a novel algorithm for optimization in dynamic binary landscapes. The Binary Ant Algorithm (BAA) mimics some aspects of real social insects' behavior. Like Ant Colony Optimization (ACO), BAA acts by building pheromone maps over a grid of possible trails that represent solutions to an optimization problem. Main differences rely on the way this search space is represented and provided to the colony in order to explore/exploit it. Then, by a process of pheromone reinforcement and evaporation the artificial insect trails converge to regions near the problem solution or extrema. The negative feedback granted by the evaporation mechanism provides the self-organized system with population diversity and self-adaptive characteristics, allowing BAA to be particularly suitable for hard Dynamic Optimization Problems (DOP), where extrema continuously changes at severe speeds.

REFERENCES

• 1: Ajith Abraham , Crina Grosan , Vitorino Ramos, Stigmergic Optimization (Studies in Computational Intelligence), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 2: 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]
• 3: Fernandes, C., Ramos, V., Rosa, A. C. Varying the Population Size of Artificial Foraging Swarms on Time Varying Landscapes. In Art. Neural Networks: Biological Inspirations, LNCS, Vol. 3696, pp. 311--316, 2005.
• 4: Kong, M., Tian P. Introducing a Binary Ant Colony Optimization. In Proc. of the 6^th Int. Workshop on ACO and Swarm Intelligence, LNCS, Vol. 4150, pp. 444--451, 2006.
• 5: Ramos, V., Fernandes, C., Rosa, A. C. On Self-Regulated Swarms, Societal Memory, Speed and Dynamics, In Proc. ALife-X, MIT Press, pp. 393--399, 2006.
• 6: Rocha, L., Maguitman, A., Huang, C., Kaur, J., Narayanan, S., An Evolutionary model of Genotype Editing, In Proc. ALife-X, MIT Press, pp. 105--111, 2006.

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