|
Binary Ant Algorithm
69. Fernandes, C.,
Rosa, A.C., Ramos V., Binary Ant Algorithm, in Dirk Thierens et al.
(Eds.), GECCO´07 - Genetic and Evolutionary
Computation Conference, Vol. 1, pp. 41-48, ACM
Press, London, UK, 7-11 July, 2007.
PDF
file: paper
(631 Kb)
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.
Keywords: Combinatorial Dynamic Optimization, Distributed Search, Swarm Intelligence and Perception, Self-Organization,
Stigmergy, Social Cognitive Maps,
Social Foraging.
Cited
by:
º
Xiaodong Zhuang, Guowei Yang, Dongqing Wang, Liyan Xu, "The Emergent
Patterns of Artificial Ant Colony's Collective Behavior in Gray-Scale
Images for Feature Extraction", in ICNSC 08, IEEE International
Conference on Networking, Sensing and Control, IEEE Press, ISBN:
978-1-4244-1685-1, pp. 1227-1232, April 2008.
Related
Works:
70. Computational
Chemotaxis
in Ants and Bacteria
over Dynamic
Environments.
64. Societal
Implicit Memory and his
Speed on Tracking Extrema over Dynamic Environments using
Self-Regulatory Swarms.
61. On
Self-Regulated Swarms, Societal
Memory, Speed and Dynamics.
56. Varying
the
Population Size of
Artificial Foraging Swarms on Time Varying Landscapes.
63. Social
Cognitive Maps, Swarm
Collective Perception and Distributed Search on Dynamic Landscapes.
58. On
Ants,
Bacteria and Dynamic
Environments.
65. Stigmergic
Optimization in
Dynamic Binary
Landscapes.
|