Exploiting Modularity, Hierarchy, and Repetition in Variable-Length Problems

Edwin D. de Jong and Dirk Thierens

Abstract. Current methods for evolutionary computation can reliably address problems for which the dependencies between variables are limited to a small order k. Furthermore, several recent methods can address certain hierarchical problems which feature dependencies between all variables. In addition to modularity and hierarchy, a third problem feature that can be exploited when present is repetition. To enable the study of these problem features in isolation, two test problems for modularity and hierarchy detection by variable length problems are introduced. To explore how a variable length method can exploit these three problem features, a module formation algorithm is investigated. It is found that the algorithm identifies all three forms of problem structure to a substantial degree, leading to significant performance improvements for both the hierarchical and repetitive test problems. The experimental results indicate that the simultaneous exploitation of hierarchy and repetition will require both position-specific module testing and position-independent module use.

Keywords: Modularity, hierarchy, repetition, SEQ problem, HSEQ problem

LNCS 3102, p. 1030 ff.

Full article in PDF

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