Engelbrecht Andries P. Computational Intelligence: An Introduction

Подождите немного. Документ загружается.

178 10. Genetic Programming

Table 10.1 XOR Truth Table

Target Output

000

AND AND

NOT NOT

Figure 10.1 Tree-Representation of XOR

As mentioned above, a grammar forms an important part of chromosome represen-

tation. As part of the grammar, a terminal set, function set, and semantic rules

need to be deﬁned. The terminal set speciﬁes all the variables and constants, while

the function set contains all the functions that can be applied to the elements of the

terminal set. These functions may include mathematical, arithmetic and/or Boolean

functions. Decision structures such as if-then-else and loops can also be included in

the function set. Using tree terminology, elements of the terminal set form the leaf

nodes of the evolved tree, and elements of the function set form the non-leaf nodes.

For a speciﬁc problem, the search space consists of the set of all possible trees that

can be constructed using the deﬁned grammar.

Two examples are given next to illustrate GP representations. One of the ﬁrst appli-

cations of GP was to evolve Boolean expressions. Consider the expression,

AND NOT x

)OR(NOTx

AND x

)

and given a data set of interpretations and their associated target outputs (as given

in Table 10.1), the task is to evolve this expression. The solution is represented in

Figure 10.1. For this problem, the function set is deﬁned as {AND, OR,NOT},and

the terminal set is {x

} where x

∈{0, 1}.

10.2 Initial Population 179

3.5/

expsin

Figure 10.2 Tree-Representation for Mathematical Expressions

The next example considers the problem of evolving a mathematical expression. Con-

sider the task of evolving the program,

y:=x*ln(a)+sin(z)/exp(-x)-3.4;

The terminal set is speciﬁed as {a, x, z, 3.4} with a, x, z ∈ R. The minimal function set

is given as {−, +, ∗,/,sin, exp, ln}. The global optimum is illustrated in Figure 10.2.

In addition to the terminal and function sets, rules can be speciﬁed to ensure the

construction of semantically correct trees. For example, the logarithmic function, ln,

can take only positive values. Similarly, the second parameter of the division operator

can not be zero.

10.2 Initial Population

The initial population is generated randomly within the restrictions of a maximum

depth and semantics as expressed by the given grammar. For each individual, a root

is randomly selected from the set of function elements. The branching factor (the

number of children) of the root, and each non-terminal node, are determined by the

arity of the selected function. For each non-root node, the initialization algorithm

randomly selects an element either from the terminal set or the function set. As soon

as an element from the terminal set is selected, the corresponding node becomes a leaf

node and is no longer considered for expansion.

180 10. Genetic Programming

Instead of initializing individuals as large trees, individuals can be initialized to be

as simple as possible. During the evolutionary process these individuals will grow if

increased complexity is necessary (refer to Section 10.6). This facilitates creation of

simple solutions.

10.3 Fitness Function

The ﬁtness function used for GP is problem-dependent. Because individuals usually

represent a program, calculation of ﬁtness requires the program to be evaluated against

a number of test cases. Its performance on the test cases is then used to quantify the

individual’s ﬁtness. For example, refer to the problems considered in Section 10.1.

For the Boolean expression, ﬁtness is calculated as the number of correctly predicted

target outputs. For the mathematical expression a data set of sample input patterns

and associated target output is needed. Each pattern contains a value for each of the

variables (a, x and z) and the corresponding value of y. For each pattern the output of

the expression represented by the individual is determined by executing the program.

The output is compared with the target output to compute the error for that pattern.

The MSE over the errors for all the patterns gives the ﬁtness of the individual.

As will be shown in Section 10.6, GP can also be used to evolve decision trees. For

this application each individual represents a decision tree. The ﬁtness of individuals

is calculated as the classiﬁcation accuracy of the corresponding decision tree. If the

objective is to evolve a game strategy in terms of a computer program [479, 481], the

ﬁtness of an individual can be the number of times that the individual won the game

out of a total number of games played.

In addition to being used as a measure of the performance of individuals, the ﬁtness

function can also be used to penalize individuals with undesirable structural properties.

For example, instead of having a predetermined depth limit, the depth of a tree can

be penalized by adding an appropriate penalty term to the ﬁtness function. Similarly,

bushy trees (which result when nodes have a large branching factor) can be penalized

by adding a penalty term to the ﬁtness function. The ﬁtness function can also be used

to penalize semantically incorrect individuals.

10.4 Crossover Operators

Any of the previously discussed selection operators (refer to Section 8.5) can be used

to select two parents to produce oﬀspring. Two approaches can be used to generate

oﬀspring, each one diﬀering in the number of oﬀspring generated:

• Generating one offspring: A random node is selected within each of the

parents. Crossover then proceeds by replacing the corresponding subtree in the

one parent by that of the other parent. Figure 10.3(a) illustrates this operator.

10.4 Crossover Operators 181

z sin

Parent 1

sin

3.4 a

Parent 2

Offspring

exp

3.4 x

z sin

3.4

exp

3.4 x

(a) Creation of one oﬀspring

Parent 1 Parent 2

3.4

Offspring 1

Offspring 2

z sin

exp

3.4 x

exp

3.4 x

z sin

3.4

sin

3.4 a

sin

3.4 a

(b) Creation of two oﬀspring

Figure 10.3 Genetic Programming Crossover

182 10. Genetic Programming

• Generating two offspring: Again, a random node is selected in each of the

two parents. In this case the corresponding subtrees are swapped to create the

two oﬀspring as illustrated in Figure 10.3(b).

10.5 Mutation Operators

Mutation operators are usually developed to suit the speciﬁc application. However,

many of the mutation operators developed for GP are applicable to general GP rep-

resentations. With reference to Figure 10.4(a), the following mutation operators can

be applied:

• Function node mutation: A non-terminal node, or function node, is randomly

selected and replaced with a node of the same arity, randomly selected from the

function set. Figure 10.4(b) illustrates that function node ‘+’ is replaced with

function node ‘−’.

• Terminal node mutation: A leaf node, or terminal node, is randomly selected

and replaced with a new terminal node, also randomly selected from the termi-

nal set. Figure 10.4(c) illustrates that terminal node a has been replaced with

terminal node z.

• Swap mutation: A function node is randomly selected and the arguments of

that node are swapped as illustrated in Figure 10.4(d).

• Grow mutation: With grow mutation a node is randomly selected and re-

placed by a randomly generated subtree. The new subtree is restricted by a

predetermined depth. Figure 10.4(e) illustrates that the node 3.4 is replaced

with a subtree.

• Gaussian mutation: A terminal node that represents a constant is randomly

selected and mutated by adding a Gaussian random value to that constant.

Figure 10.4(f) illustrates Gaussian mutation.

• Trunc mutation: A function node is randomly selected and replaced by a

random terminal node. This mutation operator performs a pruning of the tree.

Figure 10.4(g) illustrates that the + function node is replaced by the terminal

node a.

Individuals to be mutated are selected according to a mutation probability p

.Inad-

dition to a mutation probability, nodes within the selected tree are mutated according

to a probability p

. The larger the probability p

, the more the genetic build-up of

that individual is changed. On the other hand, the larger the mutation probability

, the more individuals will be mutated.

All of the mutation operators can be implemented, or just a subset thereof. If more

than one mutation operator is implemented, then either one operator is selected ran-

domly, or more than one operator is selected and applied in sequence.

In addition to the mutation operators above, Koza [479] proposed the following asexual

operators:

10.5 Mutation Operators 183

3.4 a

exp

(a) Original tree

3.4 a

exp

new node of

same arity

(b) Function node

3.4 z

exp

New terminal node

3.4 a

exp

Arguments swapped

(d) Swapping

exp

sin z

(e) Grow

3.51 a

exp

3.41+N(0,0.1)

(f) Gaussian

exp

(g) Trunc

Figure 10.4 Genetic Programming Mutation Operators

184 10. Genetic Programming

• Permutation operator: This operator is similar to the swap mutation. If a

function has n parameters, the permutation operator generates a random permu-

tation from the possible n! permutations of parameters. The arguments of the

function are then permutated according to this randomly generated permutation.

• Editing operator: This operator is used to restructure individuals according to

predeﬁned rules. For example, a subtree that represents the Boolean expression,

x AND x is replaced with the single node, x. Editing rules can also be used to

enforce semantic rules.

• Building block operator: The objective of the building block operator is to

automatically identify potentially useful building blocks. A new function node

is deﬁned for an identiﬁed building block and is used to replace the subtree

represented by the building block. The advantage of this operator is that good

building blocks will not be altered by reproduction operators.

10.6 Building Block Genetic Programming

The GP process discussed thus far generates an initial population of individuals where

each individual represents a tree consisting of several nodes and levels. An alternative

approach has been developed in [248, 742] – speciﬁcally for evolving decision trees

– referred to as a building-block approach to GP (BGP). In this approach, initial

individuals consist of only a root and the immediate children of that node. Evolution

starts on these “small” initial trees. When the simplicity of the population’s individ-

uals can no longer account for the complexity of the problem to be solved, and no

improvement in the ﬁtness of any of the individuals within the population is observed,

individuals are expanded. Expansion occurs by adding a randomly generated building

block (i.e. a new node) to individuals. In other words, grow mutation is applied.

This expansion occurs at a speciﬁed expansion probability, p

, and therefore not all of

the individuals are expanded. Described more formally, the building-block approach

starts with models with a few degrees of freedom – most likely too few to solve the

problem to the desired degree of accuracy. During the evolution process, more degrees

of freedom are added when no further improvements are observed. In between the

triggering of expansion, crossover and mutation occur as for normal GP.

This approach to GP helps to reduce the computational complexity of the evolution

process, and helps to produce smaller individuals.

10.7 Applications

GP was developed to evolve computer programs [478, 479]. Programs have been

evolved for a wide range of problem types as illustrated in [479]. These problem types

10.8 Assignments 185

Table 10.2 Genetic Programming Applications

Application References

Decision trees [248, 479, 685, 742]

Game-playing [479, 481]

Bioinformatics [484, 485]

Data mining [648, 741, 917]

Robotics [206, 486, 347]

include Boolean expressions, planning, symbolic function identiﬁcation, empirical dis-

covery, solving systems of equations, concept formation, automatic programming, pat-

tern recognition, game-playing strategies, and neural network design. Table 10.2 pro-

vides a summary of other applications of GP.

A very complete list of GP publications and applications can be found at

http://www.cs.bham.ac.uk/~ubl/biblio/gp-html/

10.8 Assignments

1. Explain how a GP can be used to evolve a program to control a robot, where the

objective of the robot is to move out of a room (through the door) ﬁlled with

obstacles.

2. First explain what a decision tree is, and then show how GP can be used to

evolve decision trees.

3. Is it possible to use GP for adaptive story telling?

4. Given a pre-condition and a post-condition of a function, is it possible to evolve

the function using GP?

5. Explain why BGP is computationally less expensive than GP.

6. Show how a GP can be used to evolve polynomial expressions.

7. Discuss how GP can be used to evolve the evaluation function used to evaluate

the desirability of leaf nodes in a game tree.

Chapter 11

Evolutionary Programming

Evolutionary programming (EP) originated from the research of L.J. Fogel in 1962

[275] on using simulated evolution to develop artiﬁcial intelligence. While EP shares

the objective of imitating natural evolutionary processes with GAs and GP, it diﬀers

substantially in that EP emphasizes the development of behavioral models and not

genetic models: EP is derived from the simulation of adaptive behavior in evolution.

That is, EP considers phenotypic evolution. EP iteratively applies two evolutionary

operators, namely variation through application of mutation operators, and selection.

Recombination operators are not used within EP.

This chapter provides an overview of EP, organized as follows: The basic EP is de-

scribed in Section 11.1. Diﬀerent mutation and selection operators are discussed in

Section 11.2. Self-adaptation and strategy parameters are discussed in Section 11.3.

Variations of EP that combine aspects from other optimization paradigms are reviewed

in Section 11.4. A compact treatment of a few advanced topics is given in Section 11.5,

including constraint handling, multi-objective optimization, niching, and dynamic en-

vironments.

11.1 Basic Evolutionary Programming

Evolutionary programming (EP) was conceived by Laurence Fogel in the early 1960s

[275, 276] as an alternative approach to artiﬁcial intelligence (AI), which, at that time,

concentrated on models of human intelligence. From his observation that intelligence

can be viewed as “that property which allows a system to adapt its behavior to meet

desired goals in a range of environments” [267], a model has been developed that

imitates evolution of behavioral traits. The evolutionary process, ﬁrst developed to

evolve ﬁnite state machines (FSM), consists of ﬁnding a set of optimal behaviors from a

space of observable behaviors. Therefore, in contrast to other EAs, the ﬁtness function

measures the “behavioral error” of an individual with respect to the environment of

that individual.

As an approach to evolve FSMs, individuals in an EP population use a representa-

tion of ordered sequences, which diﬀers signiﬁcantly from the bitstring representation

proposed by Holland for GAs (refer to Chapter 9). EP is, however, not limited to

an ordered sequence representation. David Fogel et al. [271, 272] extended EP for

Computational Intelligence: An Introduction, Second Edition A.P. Engelbrecht

2007 John Wiley & Sons, Ltd

187