Inferring and Exploiting Problem Structure with Schema Grammar

Chris R. Cox and Richard A. Watson

Abstract. In this work we introduce a model-building algorithm that is able to infer problem structure using generative grammar induction. We define a class of grammar that can represent the structure of a problem space as a hierarchy of multivariate patterns (schemata), and a compression algorithm that can infer an instance of the grammar from a collection of sample individuals. Unlike conventional sequential grammars the rules of the grammar define unordered set-membership productions and are therefore insensitive to gene ordering or physical linkage. We show that when grammars are inferred from populations of fit individuals on shuffled nearest-neighbour NK-landscape problems, there is a correlation between the compressibility of a population and the degree of inherent problem structure. We also demonstrate how the information captured by the grammatical model from a population can aid evolutionary search. By using the lexicon of schemata inferred into a grammar to facilitate variation, we show that a population is able to incrementally learn and then exploit its own structure to find fitter regions of the search space, and ultimately locate the global optimum.

Keywords: Generative grammar, compression, evolutionary algorithm, estimation of distribution algorithm, NK fitness landscape

LNCS 8672, p. 404 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer International Publishing Switzerland 2014