 |
    |
Barrier Trees for Search Analysis
Jonathan Hallam and Adam Prügel-Bennett
Southampton University
Southampton SO17 1BJ, UK
jbh02r@ecs.soton.ac.uk
apb@ecs.soton.ac.uk
Abstract. The development of genetic algorithms has been hampered by the lack of theory describing their behaviour, particularly on complex fitness landscapes. Here we propose a method for visualising and analysing the progress of a search algorithm on some hard optimisation problems using barrier trees. A barrier tree is a representation of the search space as a tree where the leaves of the tree represent local optima and nodes of the tree show the fittest saddle points between subtrees. The depth of the leaves and nodes corresponds to the fitness of the local optima and saddle points. Each configuration in search space can be mapped to a position on the tree depending on which optima are accessible without ever decreasing the fitness below its starting value. Having computed a barrier tree we can easily visualise how any search algorithm explores the search space.
LNCS 2724, p. 1586 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003