Dynamic Maximum Tree Depth

A Simple Technique for Avoiding Bloat in Tree-Based GP

Sara Silva¹ and Jonas Almeida^1,2

¹Biomathematics Group
Instituto de Tecnologia Química e Biológica
Universidade Nova de Lisboa
PO Box 127
2780-156 Oeiras, Portugal
sara@itqb.unl.pt
http://www.itqb.unl.pt:1111

²Dept Biometry & Epidemiology
Medical Univ South Carolina
135 Cannon Street
Suite 303
PO Box 250835
Charleston SC 29425, USA
almeidaj@musc.edu
http://bioinformatics.musc.edu

Abstract. We present a technique, designated as dynamic maximum tree depth, for avoiding excessive growth of tree-based GP individuals during the evolutionary process. This technique introduces a dynamic tree depth limit, very similar to the Koza-style strict limit except in two aspects: it is initially set with a low value; it is increased when needed to accommodate an individual that is deeper than the limit but is better than any other individual found during the run. The results show that the dynamic maximum tree depth technique efficiently avoids the growth of trees beyond the necessary size to solve the problem, maintaining the ability to find individuals with good fitness values. When compared to lexicographic parsimony pressure, dynamic maximum tree depth proves to be significantly superior. When both techniques are coupled, the results are even better.

LNCS 2724, p. 1776 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003