Finding Building Blocks through Eigenstructure Adaptation

Computational Synthesis: From Basic Building Blocks to High Level Functionality

Volume

Papers from the 2003 AAAI Spring Symposium

Contents

A fundamental aspect of many evolutionary approaches to synthesis of complex systems is the need to compose atomic elements into useful higher-level building blocks. However, the ability of genetic algorithms to promote useful building blocks is based critically on genetic linkage -- the assumption that functionally related alleles are also arranged compactly on the genome. In many practical problems, linkage is not known a priori or may change dynamically. Here we propose that the problems’ Hessian matrix reveals this linkage, and that an eigenstructure analysis of the Hessian provides a transformation of the problem to a space where first-order genetic linkage is optimal. Genetic algorithms that dynamically transform the problem space can operate much more efficiently. We demonstrate the proposed approach on a real-valued adaptation of Kaufmann’s NK landscapes.