Page 152 - Biomimetics : Biologically Inspired Technologies

Bar-Cohen : Biomimetics: Biologically Inspired Technologies DK3163_c004 Final Proof page 138 21.9.2005 9:37am

138 Biomimetics: Biologically Inspired Technologies

4.4 MORPHOLOGY REPRESENTATIONS

The examples above used mostly a direct encoding — a representation of the morphology and
control that evolution uses to explicitly modify each aspect of the design, adding, removing, and
modifying components and parameters directly. Clearly, however, such an approach would not
work in nature, for an average animal body contains billions of cells. Nature typically uses a more
compact representation — a genotype — to encode for a much more complex machine — the
phenotype. The genotype does not directly encode the phenotype, but instead it encodes informa-
tion for growing or developing, a phenotype. This is one form of an indirect representation that
maps between a genotype and a phenotype. In nature, these maps are evolving themselves and
several hierarchical layers of mappings are used before a real DNA yields a working phenotype.
The use of a genotype–phenotype mapping allows for many advantages, primarily the com-
pactness of a description and the ability to reuse components (more on that later). How can we use
these representations computationally?
Mechanisms and neural networks can both be described as graphs. Luke and Spector (1996)
survey a number of different representations used to describe or ‘‘grow’’ graphs, such as neural
networks. Some methods use context-free grammars, L-systems, and parse trees operating on nodes
and edges. Most of the existing representations for encoding networks generate highly connected
architectures that are suitable for computational networks, but which are less suitable for kinematic
machines because they over-constrain the motion and create deadlocked mechanisms. Using these
representations, the likelihood of generating a mechanism with a specific number of degrees of
freedom (DoF) is vanishingly small. In order to allow an evolutionary algorithm to explore the
space of one DoF mechanisms more efficiently, a more suitable representation is required.
A second consideration in the choice of representation is evolvability. Many of the representa-
tions cited above result in context-sensitive and order-sensitive description of a network. For
example, the structure generated by a branch in Gruau’s cellular encoding depends on whether it
is parsed before or after its sibling branch. If that branch is transplanted by cross-over into another
tree, it may produce an entirely different structure. Such behavior hampers the effectiveness of
recombinative operators by precluding the formation of modular components that are discovered by
the search in one place and then reused elsewhere. A representation where the structure produced by
a branch of the tree is minimally affected by its context may thus be more evolvable.

4.4.1 Tree Representations

Tree-based representations can describe a set of operations to construct a phenotype in a top-down
or bottom-up manner. A top-down representation starts with an initial structure (an embryo) and
specifies a sequence of operations that progressively modify it into its final form. Figure 4.5a shows
a top-down tree that specifies the construction of an electric circuit, starting with an initial circuit
and recursively replacing circuit segments with serial and parallel arrangements of electrical
components (Koza, 1992). Each node of the tree is either an operator that modified the circuit
and passes segments to its child nodes, or a terminal electrical component. The specific parallel
and serial operators cannot be used for construction of mechanisms as they will immediately create
over- and under-constrained kinematic chains. Because of the physics of electric circuits, ordering
of children under a parent does not matter. This tree is thus both order independent and context
independent. In a top-down tree, parent nodes must be constructed before their children. Figure 4.5a
also shows a bottom-up construction of a symbolic expression. Here terminal nodes represent
constants or variables, and parent nodes represent mathematical operators. Because of the nature
of mathematical expressions, parsing order is important, and swapping order of some child nodes
would result in a mathematically different expression. The terms are unchanged, however, by the
content of their siblings. This tree is thus order dependent but context independent. In a bottom-up
tree, child nodes must be constructed before their parents.