A REVIEW OF METHODS FOR ENCODING NEURAL NETWORK

TOPOLOGIES IN EVOLUTIONARY COMPUTATION

Jozef Fekiač Ivan Zelinka Juan C. Burguillo

Tomas Bata University in Zlin, Faculty of Electrical Engineering E.T.S.E. Telecomunicación
Faculty of Applied Informatics, and Computer Science Universidad de Vigo
nám. [Link] 5555, Technical University in Ostrava Campus Universitario de Vigo
760 01- Zlín (Czech Republic) 17. listopadu 15 36310-Vigo (Spain)
Email: fekiac@[Link] 70833- Ostrava-Poruba (Czech Rep.) Email: jrial@[Link]
Email: [Link]@[Link]

seems easy to apply to any kind of structure, but crossing

KEYWORDS over two graphs is not so straightforward. Because of
artificial neural network, automata network, evolutionary that, it seems to be an advantage to separate the genotype
computation, genetic programming, genetic algorithm, and the phenotype. That means to use a simplified
network encoding, graph grammar representation of solution in chromosomes. This process
of converting a network into genes will be called
ABSTRACT encoding in the rest of this paper.
This paper describes various methods used to encode artificial
Encoding methods can be divided in three main
neural networks to chromosomes to be used in evolutionary
computation. The target of this review is to cover the main
groups according to the process of creating the network
techniques of network encoding and make it easier to choose from the encoded genome: direct, parametric and
one when implementing a custom evolutionary algorithm for indirect encoding. They are presented in the next
finding the network topology. Most of the encoding methods subsections. At the end we present the conclusions.
are mentioned in the context of neural networks; however all
of them could be generalized to automata networks or even II. DIRECT ENCODING
oriented graphs. We present direct and indirect encoding In direct encoding methods there exists a direct
methods, and given examples of their genotypes. We also genotype-phenotype mapping for the network. That
describe the possibilities of applying genetic operators of means that all parameters of the network are clearly
mutation and crossover to genotypes encoded by these understandable from the genes without any repeated
methods. Also, the dependencies of using special evolutionary
algorithms with some of the encodings were considered.
process of transcription or growing.
Some authors ([1]) differentiate between direct
I. INTRODUCTION encoding and structural encoding, but in this paper we
consider them being the same type of encodings. In [1],
Despite of frequent critics of artificial neural the main difference between direct and structural
networks as a black-box method, they are with no doubt
encoding is that direct encoding holds not only
useful in various applications from signal processing and
information about the presence of connections, but also
recognition to industrial control.
about their weights.
There are various specialized topologies of networks After deeper look at structural encodings, authors
used to solve different kinds of problems. But it can be considered that all of them could be extended to hold
assumed that there exist other topologies useful for the also weight information, though should be quite simply
types of problems that are not primarily solved by neural interchangeable. However, the encoding of the
networks at this time. But when a new topology is connection topology is the main concern of this paper.
needed, thanks to the almost black-box structure of
neural networks, it seems to be almost impossible to A. Connection matrix
manage it by standard analytic or engineering methods. Probably the simplest representation of a graph or a
Even the task of finding the number of neurons in the network is a connection matrix. It is a square matrix n x
hidden layer of a feed-forward neural network is often n, where n is equal to the number of nodes in the
only a matter of trying different possibilities. Therefore network. Then every number in the matrix at
this looks like an ideal situation to use the heuristics of coordinates [i, j] is the weight of connection between
an evolutionary algorithm.
node i and node j. It is obvious, that on the main
Evolutionary algorithms often work with direct diagonal lay the weights of the graph loops and under
representation of the solution. Example of this could be diagonal lay the weights of recurrent (backward)
genetic programming (GP), which uses program trees as connections. So, if necessary, connection matrix can be
a genotype, but the trees are also solutions. When we try limited to the upper triangular matrix to force the
to apply a similar approach to graphs (as neural networks network to be feed-forward (i.e. without backward
are), there will probably raise a problem in the connections).
application of genetic operators. The mutation operator

Proceedings 25th European Conference on Modelling and

Simulation ©ECMS Tadeusz Burczynski, Joanna Kolodziej
Aleksander Byrski, Marco Carvalho (Editors)
ISBN: 978-0-9564944-2-9 / ISBN: 978-0-9564944-3-6 (CD)
 One of the possibilities when using a connection B. Node-based encoding
matrix is to use the numbers on diagonal as identifiers 1) Schiffmann node-based encoding
of node types instead of representing the loop weights. One of the attempts to extend the low flexibility of
That would of course exclude loops, what is probably previous approach is node-based encoding. Instead of
useful only when designing feed-forward networks. describing the network connections by a matrix of all
The numbers in the connection matrix can be of possible connections, node-based encoding enumerates
course limited to contain only numbers from set {0, 1}. all nodes existing in the network only once, and for each
This simplification does not take the weights into node it enumerates all its inputs. This kind of encoding
account; it only creates connection between nodes requires a unique identifier to be assigned to each node.
containing number 1 in the matrix. Figure 1 shows the Then these identifiers are used in gene transcription to
process of transcription of a binary chromosome into a clearly identify both node and its inputs.
network phenotype. However, this intuitive encoding is only briefly
1
0 0 1 described in [7]. Only the application of the crossover
A) 001101010 B)
[ ]
1 0 1
0 1 0
C)
2
3
operator was described in detail. In this method,
crossing over means swapping parts of the genotype
Figure 1. Binary genotype (A) is rewritten into connection matrix delimited by the borders of node definitions. An
row-by-row (B), from which the network is created directly (C).
example of the encoding and the application of the
As can be seen on Figure 2, the genetic operator of crossover operator are in Figure 4.
mutation can be applied in the way of classical genetic The mutation operator then should be able to add
algorithms, when a random bit in the genotype is flipped new nodes and connections, or delete existing ones.
to its opposite value. Parent A Parent B
1 1
1 4 4
0 0 1
A) 001101010
[ ]
1 0 1
0 1 0 2
3 2

3
5

|
N1: N2: N3: N4: 1, 2 N5: 1, 2, 3
2

3
5

|
6

N1: 4 N2: N3: N4: 2 N5: 1, 3 N6: 2, 4, 5

1
0 1 1
B) 011101010
[ ]
1 0 1
0 1 0 2
3
Child A
1
Crossover
Child B
1
Figure 2. Application of mutation operator applied on connection 4 4
matrix encoded network. Random bit in original bit string (A) is 2 6 2
flipped to reach modified offspring (B). 5 5
3 3

The crossover operator is also applied in the |

N1: N2: N3: N4: 1, 2 N5: 1, 3 N6: 2, 4, 5 |
N1: 4 N2: N3: N4: 2 N5: 1, 2, 3
Figure 4. Example of node-based network encoding. Vertical lines in
straightforward way of classical genetic algorithms, as genotype transcription represent crossover points.
can be seen on Figure 3, where crossover with one cut
point can be seen. 2) Koza node-based encoding
Another possibility of node-based encoding is to use
1
0 0 1 genetic programming. Since GP is usually applied to
Parent 1 001101010
[ ]1 0 1
0 1 0 2
3
evolve program trees in LISP language, the network in
this method is represented as a tree, where the root is the
A)
0 1 1
1 output processing element (neuron) and the leaves
Parent 2 011011101
[ ]0 1 1
1 0 1 2
3
represent the input signals. The tree structure contains
all hidden nodes and connecting links with weights
(Figure 5). When a network with more outputs is
needed, then as a root of the genetic tree a LISP
Parent 1 0011 01010 Offspring 1 0011 11101
B) Crossover function LIST is used. This list should be holding all the
Parent 2 0110 11101 Offspring 2 0110 01010 outputs which are roots of their respective sub-trees.
Details of this method and more possibilities of creating
1 more complex topologies with “defined functions” are
0 0 1
Offspring 1 001111101
[ ]1 1 1
1 0 1 2
3 described in [6].
The genetic operators are defined by applying the
C) rules of genetic programming, as mentioned in [5].
0 1 1
1 Mutation is defined as a replacement of a sub-tree with
Offspring 2 011001010
[ ]0 0 1
0 1 0 2
3
a new randomly generated sub-tree. This random sub-
tree, as well as initial random population, has few
Figure 3. Application of crossover operator on connection matrix constraints to produce a well-formed network. As can
encoded network. Parent bit string chromosomes (A) are crossed over
at random position (B) to create offspring (C) like in classical genetic
be seen in Figure 5, under any processing unit (P) there
algorithm. must be a variable amount of weights (W) that represent
connections of processing units. Every W has two
arguments. The first of them is a number that represents path, deleting an existing path, adding a neuron or
the actual weight of created link. This can be a float removing a neuron from an already existing path.
number constant or a numerical expression tree. The The crossover operator is responsible for exchanging
second argument of W is the connection source element the paths between individuals and it cuts the
– input signal or another processing node. It can be chromosomes at two points between the path
easily derived that only float number constants and boundaries. Then, as usually, the paths between the cut
input signals are allowed as the leaves of a genetic tree. points are exchanged.
Crossover genetic operation is defined simply by 3 o1
swapping sub-trees of two genetic trees. The only i1
constraint is that both sub-trees have to be cut at an P1 = i1 - 2 - 1 - o2
element of the same type, e.g., the roots of both sub- A) P2 = i2 - 1 - 3 - o1 B) 2
trees have to be P. P3 = i1 - 3 - 2 - 1 - o1

(P (W (* 1.8 0.1) (P (W 1.1 D1))) i2 1 o2

A) (W (- 1.1 0.3) (P (W -1.3 D1) (W 0.3 D0)))) Figure 6. Example of path-based encoding. Paths (A) merged together
create the final network (B). Path P3 is displayed with wide gray lines
in the network.
P
D. Neuroevolution of augmenting topologies (NEAT)
W W
NEAT (described in [11]) is an evolutionary method
- P * P on its own, not only a method of encoding. However,
B) the encoding used by NEAT seems to be very useful
1.1 0.3 1.8 0.1
and flexible. But due to some of its properties
W W W mentioned below, it is limited to be used with the
NEAT evolutionary algorithm.
-1.3 D1 0.3 D0 1.1 D1 The genetic encoding applied by NEAT uses two
chromosomes – one of them holds the enumeration of
all available nodes in the network; the other one holds
0.3 the enumeration of edges between the nodes (Figure 7).
D0 P 0.8 Every gene in the “node chromosome” contains a
C) -1.3 P unique identifier of the node and the type of the node –
a node can be an input node (sensor, receptor), an output
D1 P 0.18 node (actuator) or a hidden node. Genes in “edge
1.1 chromosome” contain information about begin and end
Figure 5. Example of node-based encoding by the means of genetic
programming. LISP expression (A) is used as a tree (B) from which
nodes of the edge, weight of the edge, information about
the network is constructed (C). activation of the gene and a historical marker.
Activation of a gene simply tells if the edge described
C. Pathway-based encoding by a gene should be created or not and its meaning will
This approach can be used to evolve flexible and be mentioned later on. Historical marker is a global
recurrent networks. It looks at the network as a set of counter which tells which mutation in all history of
paths from inputs to outputs. Every one of these paths evolution caused creation of that gene.
begins in one of the inputs, continues through variable
Node 1 Node 2 Node 3 Node 4 Node 5
set of labeled nodes and ends in one of the output nodes. A)
Input Input Input Output Hidden
Of course, for one pair of a certain input and output,
many possible paths could exist. In 1 In 2 In 3 In 2 In 5 In 4
Out 4 Out 4 Out 4 Out 5 Out 4 Out 5
There is a context-free grammar proposed in [10], B) Weight 0.7 Weight 0.2 Weight 0.2 Weight 0.1 Weight 0.9 Weight 0.4
which describes the correct form of the paths in the Enabled
Innov 1
DISABLED
Innov 2
Enabled
Innov 3
Enabled
Innov 4
Enabled
Innov 5
Enabled
Innov 6
genotype.
The process of the network construction begins with 1
the input and the output nodes. Then it continues at the
input node specified by the beginning of the current C) 2 5 4
path. After that, for every node label in the path, a node
with the same label in the network is found. If the node 3
does not exist, it is created. This node is connected to Figure 7. Example of NEAT network encoding. Genome of the
the previous one in the path. Then another node label individual contains node enumeration (A) and connections
from the path is taken and the process repeats until the enumeration (B). Final network constructed from this genome can be
seen in the bottom (C).
end of the path is reached (output). An example of this
encoding can be seen in Figure 6. The genetic operator of mutation can influence the
The genetic operator of mutation has four genotype in many ways. One of the possibilities is
possibilities to change the genotype: creating a new adding of a new node. In that case, an existing edge is
“split” and the new node is inserted in the middle. That Learning rate
1
means deactivating the gene describing an existing edge 2
(turn to DISABLED) and inserting two new edges Momentum i1 o1

connecting two existing nodes with a new one. Another A) 5 0.2 0.1 B) 3
possibility is to add a new edge, what means creating a i2 o2
4
new connection gene from one existing node to another. Number of
To fine-tune the weights of a created network, the hidden neurons 5
algorithm can also mutate the weights in the “edge Figure 9. Simple encoding of feed-forward network with one hidden
chromosome”. layer and the back-propagation learning algorithm. Chromosome (A)
Crossover in NEAT uses the aforementioned contains the number of hidden neurons and parameters of the learning
algorithm. Final network (B) for the example genome has 5 neurons in
historical markers to align genes. It improves the the hidden layer.
validity of the offspring, since only compatible
modifications are crossed-over (Figure 8). B. Layer-based encoding
1 => 4 2 => 4 3 => 4 2 => 5 5 => 4 1 => 5
For some neural network applications it can be
Parent 1 Innov 1 Innov 2 Innov 3 Innov 4 Innov 5 Innov 8
DISAB
assumed that the optimal solution will be found as a
1 => 4 2 => 4 3 => 4 2 => 5 5 => 4 5 => 6 6 => 4 3 => 5 1 => 6
multi-layer feed-forward network. In that case, it might
Parent 2 Innov 1 Innov 2 Innov 3 Innov 4 Innov 5 Innov 6 Innov 7 Innov 9 Innov 10
DISAB DISAB
be useful to apply the layer-based encoding. This
encoding supposes a multi-layer feed-forward
architecture and the back-propagation learning
Parent 1 1 => 4 2 => 4 3 => 4 2 => 5 5 => 4
algorithm. The genotype of this encoding contains back-
1 => 5
(aligned) Innov 1 Innov 2 Innov 3 Innov 4 Innov 5 Innov 8 propagation learning parameters (learning rate and
DISAB
momentum) and parameters of a variable number of
1 => 4 2 => 4 3 => 4 2 => 5 5 => 4 5 => 6 6 => 4 3 => 5 1 => 6
Parent 2 Innov 1 Innov 2 Innov 3 Innov 4 Innov 5 Innov 6 Innov 7 Innov 9 Innov 10 individual layers (Figure 10). Layer parameters contain
(aligned) DISAB DISAB
(disjoint) (disjoint) (excess) (excess)
information about the number of neurons in the layer
and information about the output connections (to the
1 => 4 2 => 4 3 => 4 2 => 5 5 => 4 5 => 6 6 => 4 1 => 5 3 => 5 1 => 6
Offspring Innov 1 Innov 2 Innov 3 Innov 4 Innov 5 Innov 6 Innov 7 Innov 8 Innov 9 Innov 10 following layer) and the input connections (from
DISAB DISAB
previous layers).
Figure 8. Aligned crossover of networks encoded by NEAT encoding.
An one-point crossover operator is used to exchange
III. PARAMETRIC ENCODING layers between individuals. A two-point crossover
operator is used to exchange bigger parts of genotypes
The following approaches describe networks as between individuals. To maintain the consistency of the
genes with a set of parameters, from which the network chromosomes, they are cut at the layer level.
is created by given rules. In this case, the topology of This encoding uses relative mutation operator, which
the network can be assumed from the problem domain, slowly changes genes of randomly chosen individuals.
but the evolutionary algorithm is used to fine-tune the Besides the minimum and the maximum value, all genes
setting of the network. contain also the maximum amount of change.
A. Simple feedforward network encoding
B) Learning Rate Momentum
Typical example of parametric encoding is a simple
encoding of a feed-forward network with one hidden Network
A) Layer 1 Layer N
layer. When designing this kind of network, the back- Parameters

propagation learning algorithm is typically used. Inputs

Layer Size Output Connections Input Connections
and outputs that define the problem are usually given,
too. Then the search space for an ideal network solving
C) Radius Density Destination Radius Density
the given problem consists of finding an acceptable
number of neurons in the hidden layer and finding the
learning algorithm parameters, which would not get Destination Radius Density
stuck in local optima in the learning phase.
Figure 10. Scheme of a layer-encoded genotype. Genotype (A)
Figure 9 shows an example of feed-forward neural includes common network learning parameters (B) and layer
network with one hidden layer, encoded simply in one parameters (C).
gene (part A – number 5). Other two genes in the
chromosome contain parameters of the back- IV. INDIRECT ENCODING
propagation learning algorithm used to train this When trying to evolve networks able to solve
network, so together with the size of the hidden layer, complex problems, the complexity of the network is
also the ideal type of learning algorithm could be usually not big enough with the use of direct and
evolved. parametric encoding of networks. Every method
mentioned above (except connection matrix) supports
adding new nodes and links to the network; however,
there is only a little chance that any kind of regularity or
modularity could evolve. Searching the space of all
possibilities with direct encoding becomes very slow for B. Matrix rewriting
very large networks. According to [9], L-systems can be generalized and
A. Lindenmayer systems applied to matrices. That can be used to grow a
connection matrix of a network, dynamically changing
Lindenmayer systems (L-systems) are used for
its size according to the problem. Figure 12 show the
describing many biological processes in computer
derivation of a connection matrix (B.4) from genotype
environments. Their most common use is in the
(A). The derivation process starts with single symbol S
simulation of plants growth [3].
(B.1) and the rewrite rules are iteratively applied until
L-systems are based on formal grammars, that
only terminals (1’s and 0’s) are left in the generated
means, they use productions (rewrite rules) that are
matrix.
iteratively applied on the starting string (axiom). The
main difference is that L-systems use parallel rewriting
Mutation and crossover operators are not exactly
of the string, i.e., all occurrences of the left sides of the
specified in the literature, however looking at the
production rules are applied at once.
rewrite rules, their design should be intuitive and
In [2], context-sensitive L-systems are used to
straightforward.
produce modular ANNs. The growth of the network
starts with an axiom, on which the rewrite rules from A)
chromosome are applied until the string contains only S
AB
[ ]
CD
A
cp
[ ]
ac
B [ ] aa
ae
C
aa
[ ]
aa
D
aa
[ ]
ad
terminals. Context sensitivity of the system means that
00 00 10 01 11
one symbol can be rewritten in different ways, a [ ]
00
b [ ]
01
c [ ] 00
e [ ]
01
p [ ]
11
according to its neighboring symbols. However,
neighbors in this method are not considered as string
neighbors, but final network neighbors. That means that B)
in every stage of the rewriting there have to exist also 1) S 2) AB 3) cpaa
network interpretation of the current string. Modules CD acae
aaaa
that are connected to the current module are considered aaab
to be the left-side neighbors, while the modules to
whom the current module is connected are considered 4) 10110000 5)
to be the right-side neighbors. 01110000
Each node is represented by an alphabet letter in the 00100001 0 2
string. Modules are defined as groups of nodes. As this 00010001
7
00000000
encoding is designed for evolving feed-forward 00000000 1 3
networks, all modules are connected from left to right. 00000000
Nodes in the module are automatically connected, until 00000001
they are separated by a comma in the genotype.
Figure 12. Example of a matrix-rewriting encoding method. A set of
An example of the network derivation from axiom rewrite rules (A) is repeatedly applied to the starting symbol (B.1)
through production rules can be seen on Figure 11. Part until the generated matrix contains only terminals (B.4). This matrix is
(A) displays the production rules; part (B) shows the used as connectivity matrix and the network (B.5) is created according
to it.
iterations of the string rewriting process and on (C) the
final network can be seen. In part (B.2) and (B.3), the
C. Cellular encoding
brackets denote modules that are connected from left to
right. Number “1” denotes a feed-forward connection Cellular encoding is inspired by the cell splitting in
skipping 1 module – so the node from first module is the process of a living organism growth and is proposed
connected to the third module (which consists only of in [12]. This encoding is based on a simple graph
one node). grammar, which is represented by a grammar tree. This
graph grammar tree encodes the growth process of
A BBB
0) A
whole network from one initial cell. This tree can also
B>B [C,D]
A) B C B)
1) BBB
C)
C C contain control commands to influence the growth of
2) [C,D][C,D]C
D>C C1
3) [C,C1][C,C]C
C
the network. Basic commands and instructions are:
C< D C C C
• Sequential division (SEQ) – splits the current
Figure 11. Example of L-system-based encoding. Rewrite rules (A)
are applied to starting symbol (B.1) until the generated string contains cell in two, connected in series.
only terminals (B.5). Then the network is constructed (C). • Parallel division (PAR) – splits the current cell
in two, connected in parallel.
The authors of this approach use another encoding to • End program (END) – makes a neuron from the
transform production rules to bit strings, on which the current cell and stops rewriting.
genetic operators are applied as in classical genetic • Recursive derivation (REC) – starts applying
algorithms ([4]). This seems to be an unnecessary the rewrite rules from the root of the grammar
overhead, since all production rules could be stored in tree, until a given recursion level is reached.
dynamic data types, making the recognition of their • Increment/decrement the neuron threshold value
meaning more clear. However, new genetic operators (INCBIAS / DECBIAS).
would have to be designed.
 s
• Create recursive link (CYC) – creates a link s s
from the current cell’s outputs to its inputs. This b b b
instruction fulfills the need for a recursive t t t
network topology. s s
• Increment/decrement link register (INCLR /
A) NG TA NB
DECLR). The link register stores current link
from/to current cell, on which one of the t t
following operation could be applied.
s s s
• Set positive/negative weight (VAL+ / VAL-) –
e e e
sets the link in the link register to +1 or -1.
t t
• Delete link (CUT) – deletes the link stored in t
the link register.
Figure 13 shows the derivation of a network from a
simple grammar tree. Only four cellular instructions are 0.74
0.48 0.22
applied in this case, what is enough to create a simple 0.11 Target Labels
feed-forward network.
0.06 0.62 Outter
B) 0.16
0.23 Cellular
1) 2) 3) 4)
0.3 Graph
Input Input Input Input 9
SEQ Source Labels
1 1 2 1 4 2

A) PAR END B) 0 0 0 3
SEQ PAR REC Embedded Cellular Graph
0 Figure 14. Basic elements of a cellular graph grammar encoding. (A)
REC END displays a general rewrite rule with non-terminal on the left side and a
Output Output Output Output
cellular graph on the right side with possible connections for source
Figure 13. Example of a cellular encoded network. Instructions of the
and target labels. When NB in the rewrite rule is replaced by another
genetic tree (A) are sequentially applied to the nodes of the growing
cellular graph, the embedded cellular graph is connected to the outer
network (B). Basic instructions include SEQ – serial splitting of node
by similar source and target labes (B).
(B.2), PAR – parallel splitting of node (B.3), REC – repeated
application of genetic tree instructions (B.4) and END – replacing
node by terminal and finishing its growth (e.g. node 0 in B.2). To make the encoding flexible enough to handle the
most possible situations during evolution, all rewrite
Crossover and mutation operation are applied rules evolved by grammar have added sets of labels.
according to the common GP paradigm. That means that Then, when embedding a new sub-graph into actually
when mutating a chromosome tree, a random node of growing network, all the connections are created by the
the tree is chosen and it is replaced by a different similarity of the labels on appropriate positions. This
instruction of the same arity, or the whole sub-tree embedding principle is shown on Figure 14. In the top
under it is replaced by a random sub-tree. Crossover is part (A), there is a single cellular grammar production
done by exchanging random sub-trees between rule. NG on the left side is a label a hyper-edge to
chromosomes of two individuals. rewrite. The right side of the rule is a cellular graph, by
which the hyper-edge will be replaced. In this graph, b
D. Cellular graph grammars
denotes begin nodes, e denotes end nodes, TA is a
The cellular graph grammar approach to evolve terminal symbol and NB is a label of another non-
network topology proposed in [13] is also based on the terminal hyper-edge (of course, the cellular graph can
similarity of the network growing with the biological contain a different set of terminals and non-terminals).
processes of growth. However, instead of a fixed set of As mentioned above, after the replacement of a hyper-
rules (like in the cellular encoding), also the grammar edge, the embedded cellular graph is connected to the
generating the networks evolves through generations. outer graph through its begin and end nodes by the
Another notable difference is the use of hyper-edge similar source (s) and target (t) labels. Direction and
replacement instead of node replacement. That means available levels of connections are displayed by gray
that in the beginning of the growth process, there exist arrows in the cellular graph. Part (B) of the image
only one hyper-edge connecting inputs with outputs, shows the way of label matching in detail. Two labels
instead of a cell connecting them. Then all of the rewrite are matched (and then connected), when their Euclidian
rules are applied on hyper-edges and the final network distance is smaller than a given threshold.
nodes (neurons) are also created by replacing a hyper- In this approach, only the genetic operator of
edge with a grammar terminal. mutation has been left. That is caused by using only a
single grammar for the whole population and the
individuals defined only by the label of the starting
hyper-edge. Then the movement of genetic material
caused by the crossover operator is also handled by the
operator of mutation, because mutating one production
rule modifies all individuals using that rule in their
growth.
 The operator of mutation operates on a single [9] Kitano, H. “Designing neural networks using genetic algorithms
with graph generation systems,” Complex Systems, vol. 4, issue
production rule, where it modifies one of the following 4, pp. 461-476, 1990.
lists: list of non-terminals, list of terminals, list of begin [10] Jacob Ch. and Rehder J. “Evolution of neural net architectures
nodes and list of end nodes. It randomly removes an by a hierarchical grammar-based genetic system,” Proc.
existing item from the list or adds a new item to it. International Conference on Artificial Neural Networks and
Genetic Algorithms, pp. 72-79, 1993.
V. CONCLUSIONS [11] Stanley K. [Link] Miikkulainen R. “Evolving neural networks
through augmenting topologies,” Evolutionary Computation,
As can be seen along this paper , the differences in MIT Press, vol. 10, number 2, pp. 99-127, 2002.
the three types of encoding methods are quite [12] Gruau F. 1994. “Neural network synthesis using cellular
significant. Each of them is predetermined to solve encoding and the genetic algorithm.” Dissertation, l’Ecole
different kind of problems. Among them, the most Normale Superieure de Lyon , France, 159 p.
flexible one seems to be cellular encoding and cellular [13] Luerssen M. “Experimental Investigations into Graph Grammar
Evolution : A Novel Approach to Evolutionary Design.
graph grammar-based encoding. However, the Saarbrucken.” Saarbrucken : VDM Verlag Dr. Müller, 2009,
implementation of such sophisticated algorithms and 204 p.
their need for modularity might be a big overhead for
real use in automation and control industry. For control AUTHOR BIOGRAPHIES
purposes, well known topologies are typically used and
their parameters can be found by an evolutionary JOZEF FEKIAČ is a postgraduate
algorithm using the parametric encoding. student at Tomas Bata University in
When a network designer does not design the Zlin. Topic of his thesis is the use of
network directly and he decides to use evolutionary artificial life methods in optimisation.
heuristics, he is facing the problem of selecting the right His research is concerned in modular
method of encoding; what is still some kind of “black neural network evolution for inteligent agent control
art” and has to be done intuitively. However, we believe and synthesis of networks used in stegoanalysis. His e-
that this paper will make the process of choosing the mail address is: jfekiac@[Link]
right method more straightforward.
Presently we are working on a hybrid method of IVAN ZELINKA was born in Czech
network encoding, combining the standard GP approach Republic, and went to the Technical
of the cellular encoding and the flexibility of the cellular University of Brno, where he studied
graph grammar evolution to design large modular technical cybernetics and obtained his
networks that could be described by a single compact degree in 1995. He obtained his Ph.D.
genotype. degree in Technical Cybernetics in 2001
at Tomas Bata University in Zlin, He is now a Professor
ACKNOWLEDGMENT at the Technical University in Ostrava, Czech Republic.
This research is supported by the Internal Grant His specialization is artificial intelligence and its
Agency of Tomas Bata University under the project interdisciplinary use and applications. His e-mail
Artificial Life in Optimization No. IGA/28/FAI/10/D address is: [Link]@[Link] and his Web-site is
and by the European Regional Development Fund under at: [Link]
the Project CEBIA-Tech No. CZ.1.05/2.1.00/03.0089.
JUAN C. BURGUILLO received the
REFERENCES [Link]. degree in Telecommunication
[1] Hussain T. S. and Browse R. A. “Genetic Encoding of Neural Engineering in 1995, and the Ph.D.
Networks using Attribute Grammars,”
degree in Telematics (cum laude) in
[2] Boers, E. J. W. and Kuiper H. 1992. “Biological metaphors and
the design of modular artificial neural networks.” Mater’s thesis,
2001; both at the University of Vigo,
Leiden University, the Netherlands, 104p. Spain. He is currently an associate
[3] Lindenmayer, A. and Prusinkiewicz P. “The algorithmic beauty professor at the Department of Telematic Engineering at
of plants.” New York: Springer-Verlag, 1990, 240 p. the same university. He has participated in several R&D
[4] Holland, J. H. “Adaptation in natural and artificial systems.” projects in the areas of Telecommunications and
Ann Arbor: University of Michigan Press, 1975, 228 p. Software Engineering, and has published more than one
[5] Koza, J. R. “Genetic programming: A paradigm for genetically hundred papers in journals and conference proceedings.
breeding populations of computer programs to solve problems.”
Stanford: Stanford University, 1990, 131 p. His research interests include game theory,
[6] Koza, J. R. and Rice, J. P. “Genetic generation of both the optimization, telematic services, autonomous agents and
weights and architecture for a neural network,” in Seattle multi-agent systems. His e-mail address is:
International Joint Conference on Neural Networks, vol. 2, pp. jrial@[Link] and his Web-site is at:
397-404, Jule 1991. [Link]
[7] Schiffmann, W. “Encoding Feedforward Networks for Topology
Optimization by Simulated Evolution,” Fourth International
Conference on Knowledge-Based Intelligent Information
Engineering Systems & Allied Technologies, pp. 361-364, 2000.
[8] Mandischer, M. “Representation and Evolution of Neural
Networks,” Proceedings of the International Joint Conference on
Neural Networks and Genetic Algorithms, pp. 643-694, 1993.