Nature Inspired Systems (B):

Exploration vs Exploitation in Naturally Inspired Search (Exp2)

4th April

part of

AISB'06: Adaptation in Artificial and Biological Systems

University of Bristol, Bristol, England

Nature-inspired systems: Nature-inspired systems such as genetic algorithms, particle swarm optimisation and ant colony algorithms are the state-of-the-art solution techniques for some problems. The Nature Inspired Systems meeting at AISB '06 comprises of two linked symposia: the morning session, NISPADE, examines nature inspired systems for parallel, asynchronous and decentralised environments, whereas the afternoon session, (Exp2), is concerned with a fundamental problem in natural systems - the balance of system resources between exploration of the search space and exploitation of potentially good problem solutions.

Exploration vs Exploitation in Naturally Inspired Search, (Exp2): Any method can solve a search problem given infinite time. This does not demonstrate intelligence; intelligent search is resource limited. Intelligent search must combine exploration of the new regions of the space with evaluation of potential solutions already identified. This necessitates in balancing exploration with exploitation. Too much stress on exploration results in a pure random search whereas too much exploitation results in a pure local search. Clearly, intelligent search methods must reside somewhere in the continuous spectrum in between these extremes.

Evolutionary algorithms (EAs) provide one example population-based framework in which this issue has been explored for many years. EAs are often discussed as a Naturally Inspired Search (NIS) methodology which is effective because it strikes the exploration/exploitation balance in a good position between local and random search. More recently, other population-based NIS algorithms - such as Ant Colony Optimisation, Mimetic Algorithms, Particle Swarm Optimisation etc - are also believed to find an effective exploration/exploitation ratio.

However, this begs the question do NIS algorithms indeed strike an effective exploration/exploitation balance and if so are there common principles that could provide a theoretical justification for this characteristic. This symposium aims at addressing such issues from an explicitly theoretical rather than heuristic perspective.

Exp2: The Provisional Timetable

1.30-2.30pm LUNCH 4.30pm COFFEE & CLOSE