 |
    |
Evolvability Analysis of the Linkage Tree Genetic Algorithm
Dirk Thierens1 and Peter A.N. Bosman2
1Institute of Information and Computing Sciences Universiteit Utrecht, The Netherlands
D.Thierens@uu.nl
2Centre for Mathematics and Computer Science P.O. Box 94079, 1090 GB, Amsterdam, The Netherlands
Peter.Bosman@cwi.nl
Abstract. We define the linkage model evolvability and the evolvability-based fitness distance correlation. These measures give an insight in the search characteristics of linkage model building genetic algorithms. We apply them on the linkage tree genetic algorithm for deceptive trap functions and the nearest-neighbor NK-landscape problem. Comparisons are made between linkage trees, based on mutual information, and random trees which ignore similarity in the population. On a deceptive trap function, the measures clearly show that by learning the linkage tree the problem becomes easy for the LTGA. On the nearest-neighbor NK-landscape the evolvability analysis shows that the LTGA does capture enough of the structure of the problem to solve it reliably and efficiently even though the linkage tree cannot represent the overlapping epistatic information in the NK-problem. The linkage model evolvability measure and the evolvability-based fitness distance correlation prove to be useful tools to get an insight into the search properties of linkage model building genetic algorithms.
LNCS 7491, p. 286 ff.
lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012