PhD thesis,
Generative Representations for Evolutionary Design Automation
Brandeis University, Dept. of Computer Science, Boston, MA, USA, (February 2003)
Abstract
In this thesis the class of generative representations
is defined and it is shown that this class of
representations improves the scalability of
evolutionary design systems by automatically learning
inductive bias of the design problem thereby capturing
design dependencies and better enabling search of large
design spaces. First, properties of representations are
identified as: combination, control-flow, and
abstraction. Using these properties, representations
are classified as non-generative, or generative.
Whereas non-generative representations use elements of
encoded artifacts at most once in translation from
encoding to actual artifact, generative representations
have the ability to reuse parts of the data structure
for encoding artifacts through control-flow (using
iteration) and/or abstraction (using labelled
procedures). Unlike non-generative representations,
which do not scale with design complexity because they
cannot capture design dependencies in their structure,
it is argued that evolution with generative
representations can better scale with design complexity
because of their ability to hierarchically create
assemblies of modules for reuse, thereby enabling
better search of large design spaces. Second, GENRE, an
evolutionary design system using a generative
representation, is described. Using this system, a
non-generative and a generative representation are
compared on four classes of designs: three-dimensional
static structures constructed from voxels; neural
networks; actuated robots controlled by oscillator
networks; and neural network controlled robots. Results
from evolving designs in these substrates show that the
evolutionary design system is capable of finding
solutions of higher fitness with the generative
representation than with the non-generative
representation. This improved performance is shown to
be a result of the generative representation's ability
to capture intrinsic properties of the search space and
its ability to reuse parts of the encoding in
constructing designs. By capturing design dependencies
in its structure, variation operators are more likely
to be successful with a generative representation than
with a non-generative representation. Second, reuse of
data elements in encoded designs improves the ability
of an evolutionary algorithm to search large design
spaces.
