Speedup of Evolutionary Behavior Learning with Crossover Depending on the Usage
Frequency of a Node

Daisuke KATAGAMI and Seiji YAMADA
CISS, IGSSE, Tokyo Institute of Technology
4259 Nagatsuta, Midori-ku Yokohama 226-8502, JAPANfkatagami,yamadag@ymd.dis.titech.ac.jp
ABSTRACT

1.0
1.0
IF_A

In this paper, for on-line robot behavior learning, we
propose heuristics using node usage for speedup of evo-

0.8

Prog

0.0

IF_B

0.3

lutionary learning, and verify the utility experimen-

node usage ratetally. Genetic Programming (GP) is an evolutionary

0.8

way to acquire a program through interaction with anenvironment. Since behaviors of a robot are described

0.3

IF_D

0.3

IF_C

IF_A

0.0

0.3

IF_B

IF_C

with a program, researches on applying GP to robot

0.8

behavior learning have been activated. Unfortunately,
in most of the studies, the behavior learning is doneo -line using simulation, not a real robot.

Becauseconvergence of GP is slow, and this makes operationof a real robot quite expensive. However, since situations out of simulation easily happens in a real world,

0.3
ACT_B

0.0

0.0

0.0

0.0

0.3

ACT_C

ACT_A
ACT_A
ACT_C
ACT_C

0.0

0.0

0.3

ACT_A

ACT_C

ACT_B

ACT_B

Figure 1: Distribution of node usage frequency.

the behavior learning with a real robot (called on-line
learning) remains very signi cant. Thus, in order tomake on-line behavior learning with GP practical, we
propose a novel crossover method for speedup of GP
using node usage of a program.

Hence we propose a novel crossover using the usage
frequency of nodes.
We develop three crossover methods: a crossover

1 Introduction

with crossover points in two nodes having high usage
frequency, a crossover with crossover points in a node

Recently, a robot learning using Genetic Programming(GP)[1] actively has been researched.

quency of the crossover points.

However, un-fortunately most of their researches use simulation, it
hasn't been still experiment using a real robot in realenvironment. As for on-line learning using a real robot,
it has been experimented to learn obstacle avoidance
behavior using GP[5].
For the ecient way to search by GP, methods using a subroutine such as ADF (Automatically De ned

having high usage frequency and a node having low
usage frequency, and a crossover with crossover points
in two nodes having low usage frequency.

We apply

three crossovers to on-line behavior learning of a real
mobile robot Khepera in two tasks: obstacle avoidanceand box-pushing, and make systematic experiments forinvestigating the eciency of learning. As a result, wefound out our approach is promising for speedup of
on-line behavior learning using GP.

However there isn't attempt to improve a destruc-

2 The method of crossover depending on theusage frequency of a node
2.1 The usage frequency of a node

tive crossover in itself, and crossover points are de-In this study, we de ned the number of the usage oftermined randomly.

In a case of using a conditional

nodes as the usage frequency of nodes. First of all, wesentence like a If-sentence in GP, we observe the dif-studied that the usage frequency of nodes varied each

Functions)[3] or MA (Module Acquisition)[2] have beendeveloped. These methods have the advantage that a
partial structure of a solution can be preserved from a
destructive crossover.

ference among nodes (functions) in frequency of usage.

a node by a preliminary experiment. We experiment

Only a part of nodes is used very often, and the otherthat a mobile learns box pushing behavior. Fig.1 showsis hardly executed. Also this tendency keeps without

the usage rate of nodes(18th individual, 21st genera-

the extreme change of an environment. It is signi canttion) learn by the experiment. A height(a column) ofthat if crossover points are determined in nodes of low

nodes show the usage rate of nodes. the usage rate ofusage frequency both in parents, the crossover does

nodes calculated A right tree is chosen by IF A which

not in uence to children's behavior. Thus we consider

is thethe e ectiveness of crossover depends on the usage fre-ure in the case of most, and a left tree is hardly used.

rst condition divergence sentence by thisg-Like this, it knows the thing that the big di erence
comes out to the usage rate by the node.

The node

used by using the condition divergence used for the
non-terminal sets of GP well in this environment, andthe node which isn't used are made. Therefore it canbe thought to be the results that it is accumulated.

n 2(Rm
i −Rj )

Hijmn

0

n 2
m
n
0.5(1−Rmi −Rj ) +0.5(Ri ×Rj )

Hijmn

1
0.8
0.6
0.4
0.2
0

1
0.8
0.6
0.4
0.2
0
0.2

0.4
Rm
i

So far as there is no big change of the environment,

0.6

0.8

1 0

0.2

0.4

0.8
0.6 n
Rj

1
0

0.2

0.4
Rm
i

0.6

0.8

1 0

0.2

0.4

0.8
0.6 n
Rj

1

the node which isn't used by that condition divergencemeans that it isn't used after that as well as for thisthing. It pays attention to the correlation with the usage frequency and the experiment environment of that

Figure 2: Crossover func-

Figure 3: Crossover func-tion 1(H1).

tion 2(H2).

node, and aims at improving learning eciency by including it into heuristic of the crossover operation by

n 2
m
n
(1−Rm
i −Rj ) −0.5(Ri ×Rj )Hijmn

this research.

1
0.8
0.6
0.4
0.2
0

2.2 The crossover depending on the usage frequency of a node

0

0.2

0.4
Rm
i

0.6

0.8

The usage rate of nodes is calculated with the following

Cimm=i Nmax

formula.

R

The usage frequency of the node m in the individual i,

max are the maximum number of the node with Rim
Cim in the population here. In most research of GP,

Nwith the usage rate of the node m in the individual i,the case that an crossover point is decided at random

like one-point crossover in Genetic Algorithm is mostabout the crossover operator. We call general crossover
methods like that as random crossover. We prepared
for the following three setups that crossover probability
was changed by the usage rate of the node.
1. The setup of increasing the crossover probability
with high node of the usage frequency and low
node(The crossover function 1 : H1)
2. The setup of increasing the crossover probability
with high nodes of the usage frequency(The crossover
function 2 : H2)
3. The setup of increasing the crossover probability
with low nodes of the usage frequency(The crossover
function 3 : H3)

Crossover function 1 The following formula is made

1 0

0.2

0.4

0.8
0.6 n
Rj

1

Figure 4: Crossover function 3(H3).

Crossover function 2 The following formula is madean evaluation function to increase the crossover probability with high nodes of the usage frequency.

Thelandscape is shown in Fig.3.

ij = 0:5(1 0 Rmi 0 Rjn )2 + 0:5(Rim 2 Rjn )
mn
H ij
H 2ij
mn = P Hmnij
mn
i;j

H

Crossover function 3 The following formula is madean evaluation function to increase the crossover probability with low nodes of the usage frequency.

Thelandscape is shown in Fig.4.

ij = 1:0(1 0 Rmi 0 Rjn )2 0 0:5(Rim 2 Rjn )
mn
ij
Hmn
H 3ij
=
P
mn
ij
Hmn
i;j

H

The experiment which two tasks were di erent froman evaluation function to increase the crossover prob-

was done to examine the e ect of each evaluation func-

ability at a low node and a high node of the usage

tion by using these evaluation functions. Each is madefrequency.

the Exp.A, the Exp.B, and it explains in the following.

ij = (Rim 0 Rjn )2
mn
H ij
H 1ij
mn = P Hmnij
mn
i;j

H

ijmn are the crossover probability that node
m of the individual i, j , n become the points of theijcrossover with Hmn here. The landscape is shown in
Where H 1

Fig.2.

3 Setup of the Exp.A and Exp.B
3.1 An environment and task
We made experiments with a standard autonomous
miniature robot Khepera.

It is equipped with eight

infrared proximity sensors.

The mobile robot has acircular shape with diameter of 6 cm and a height of 5
cm. It possesses two motors and on-board power supply. The motors can be independently controlled byTable 1: Parameters of GP(Obstacle Avoidance).
Obstacle

Avoid-Box Moving

ance
Terminal

Forward,Right,Left Forward,Right,Leftinitial positions, and learning was done and evaluatedabout those two places with the box push of the Exp.B
by the test. We built the system of GP based on theevolution algorithm [4][5]which Nordins were using as
the system of this research.
That procedure is shown in the following.

,Right Round,Left RoundFunction

IF Front,IF Right

IF Front,IF Right,IF Left,IF Back

,IF Left,IF Back

1. Select four arbitrary programs from the population.
(a) Run each programs, and read proximity andlight sensors.

,Prog3
population

5040(b) For each of calculate a

size
step

50

2. Make two o spring of the two individuals with high-60

selection

est

tournamenttness and let the copies be subject to crossoverand mutation. The following heuristic is carried out

methodtournamenttness value F .

in the case of crossover.

4

size

(a) For the combination of all nodes of two individuals calculate evaluation value H(b) Calculate the H 1

a PID controller. The eight infrared sensors are dis-

ij .
mn

ijmn (orH 2ijmn ; H 3ijmn ) crossovertributed around the robot in a circular pattern. They

probability on the combination of all nodes

emit infrared light, receive the re ected light and mea-

from evaluated value.

sure distances in a short range: 2-5 cm. The robot is(c) Decide crossover points using the roulette strat-

also equipped with a Motorola 68331 micro-controlleregy.

which can be connected to a computer via serial cable.

(d) Carry out crossover in the decided point, andFirst, the experiment of the obstacle avoidance wasmake two new o spring.

done in the Exp.A to examine the e ect of each evaluation function. Obstacle avoidance is a comparatively
easy task because an answer can be expressed by map-

3. Replace the two individuals with worst

ping of the behavior toward the condition. Therefore,
it is suitable for comparing the e ect of the above-

4. Repeat step 1 to 4.

mentioned 3 setup. We prepared for 2 obstacles of the
cube on the table of theat rectangle of 110cm

2 90cm,and installed the wall made of the white plastic board
surrounded by them.

We did an experiment about the random crossoverand this technique which the crossover function 1,2,3
by using this procedure respectively.

5 Acquisition of Obstacle Avoidance
Behavior:Exp.A

Next, the task of the acquisition of the box pushing
behavior was done by using the evaluation function
2 that good results came out from the results of the
Exp.A. This is an Exp.B. An light source and the boxof the cube made of the transparent plastic board on
the table of theat rectangle of 110cm

2 90cm wereput, and the experiment of the acquisition of the box

First, the experiment of the obstacle avoidance wasdone as the Exp.A to examine the e ect of each evaluation function.

where it varied in this environment in the light source

5.1 Fitness function

direction.

Anpushing behavior was done from two initial positions

A function like Table.1 was designed in the terminal
sign of GP and the non-terminal sign.

4 Measures of the Exp.A and Exp.B
We divided an experiment into test phase with training
phase.

A robot learning in training phase, and thebest individual which it could get in that process wasevaluated again in test phase. As for the experiment A,
a robot does learning through the a series of behavior.
It begins in the initial position from the place where itis di erent every time for that reason.
It was arranged with the training at random in two

tness withthe two new o spring.

F

tness function was de ned as follows.

std = smax + (j10 0 m1 j + j10 0 m2 j + jm1 0 m2 j)
1
Fadj
Fadj =
F itness : F = p
XF
1 + Fstdadj
i=0
smax returns the biggest value (0 0 1023) in eightproximity sensor value here.

Moreover, m1 and m2

shows the speed of the left wheel and the right wheel
respectively, and takes binary here

010 0 10. Big value

is taken, and this function lowers evaluation as muchas to be close to the obstacle. Big value is taken, and

0.6

0.3

Std Fitness(ex1)
Std Fitness(random)

0.55

0.26

0.5

0.24
Fitness

Fitness

0.45
0.4
0.35

0.22
0.2
0.18
0.16

0.3

0.14

0.25

0.12

0.2

0.1
0

5

10

15
Generation

0.6

20

25

30

0

tness: H 1.

Figure 5: Ave. of

5

10

15
Generation

Figure 7: Max. of

0.3

Std Fitness(ex2)
Std Fitness(random)

0.55

20

25

30

tness: H 1.

Best-of-gen Fitness(ex2)Best-of-gen Fitness(random)

0.28
0.26

0.5

0.24
Fitness

0.45
Fitness

Best-of-gen Fitness(ex1)Best-of-gen Fitness(random)

0.28

0.4
0.35

0.22
0.2
0.18
0.16

0.3

0.14

0.25

0.12

0.2

0.1
0

5

10

15
Generation

20

25

30

tness: H 2.

Figure 6: Ave. of

evaluation is lowered when a robot turn at

0

5

10

15
Generation

Figure 8: Max. of

20

25

30

tness: H 2.

xed point

It was not the di erence about the mean of adapta-

obtained this exper-tion of population using random crossover very much.

iment at population size p times. We use the results

This technique shows that the whole search of thewhich normalized Fgroup lacks an in uence very much in this.

std

without advancing. Fitness F

tness F .

,std and made the best value 0.0 as

were coecients, and it used

= 1:0,= 10:0 this time.

6 The results of Exp.A
6.1 Comparison with Random Crossover:Averageof tness
The experiment is made ten times by changing seedusing crossover function 1,2 and 3, and we obtained
the average of the mean value of the
training.

delity in theAnd, compared with the experiment using

random crossover. Furthermore, the standard deviation of the experiment is shown every 4 generation in
the graph. Fig.5 shows the change of average of themean oftness every generation in the experiment us-

ing crossover function 1 and random crossover. Fig.6
shows the change of average of the mean oftness every

generation in the experiment using crossover function
2 and using random crossover.

6.2 Comparison with Random Crossover:The
best of tness
We obtained the change of every average generation of
the best value oftness in the experiment.

It com-pared with the experiment using random crossover.
Furthermore, the standard deviation of the experimentis shown every 4 generation in the graph. Fig.7 shows
the change of average of the mean of best

tness every

generation in the experiment using crossover function
1 and using random crossover. The best value gets thehigh value of the evaluation in the generation whose itis early. It is found clearly that the crossover of thelearning eciency which it is all right as for is done bygiving it evaluation gradually. Fig.8 shows the changeof average of the mean of best

tness every generationin the experiment using crossover function 2 and using

random crossover. The best value got a little higher
value than the method of random crossover with the

1Best-of-gen Fitness(ex2)Best-of-gen Fitness(random)

Fitness

0.8
0.6
0.4
0.2
0
0

5

10
Generation

Figure 9: The moving locus(Ex.2, Gen.20).

15

Figure 10: Average of best-of-gen
generation whose it was early. However, it caught up
in around the generation 10, and got the value thatthe method of using random crossover was better after that. The experiment which the crossover function
3 was used for showed worse value than before.

As

for the crossover with nodes which aren't used, it isfound that it makes eciency worse as for the searchof the best value. Test value didn't almost change with
before.

We experimented about acquisition of box pushing behavior by using crossover function 2 with a good evaluation from the results of the Exp.A.

7.1 Fitness function
We de ned aactually moves by using the evaluation function 1. ThisF

gures are the moving locus of the robot by the pro-tness function as follows.

Xn u

std

=

i=1

gram which it gets with the generation 20 of the done
Exp.A by using the evaluation function 2. When theit converting the direction without colliding and theevaluation has been given at generation 20. We did anexperiment about three setups which made crossoverprobability change by the usage probability of a nodeby the task of the obstacle avoidance. It was evaluatedabout the mean of a degree of adaptation, the bestvalue, the test value respectively toward three evaluation functions. As for the evaluation function 3, badvalue was shown if it was the same in comparison withthe method of using random crossover. Crossover with
low node of the usage frequency didn't appear in theexpression type easily. Therefore, this showed low evaluation as results as for the easy task when it was compared with the method of using random crossover. The
graph showed a high evaluation respectively comparedwith random crossover about the evaluation function 1
and 2. This thing shows that this technique is e ective.
Moreover, when we observed the behavior of the robot
which is an expression type, it was observed that the
behavior which an evaluation function 2 was a little excellent about when it is compared with an evaluation
function 1 was shown. The results of our experimentclearly shows that this technique was e ective.

tness(Ex2).

7 Exp.B:Acquisition of box pushing behavior

Fig.9 shows the example of a locus which a robot

robot seems to knock against the obstacle and the wall,20

1

adj = 1 + Fstd

F

i

+

Xn v
i=1

i

+

Xn w

i

i=0

F itness : F =

F

adj

Xp F

adj
i=0
where ui ，vi and wi takes binary here 0,1. ui evaluatedthe ith terminal sign and 1 is returned, when there

was a reaction in the infra-red proximity sensor of thefront this time.

iv returns 1 in the same way when

there was a response in the ambient light sensor in
front in addition.

iw returns 1 when a box is pushed

in addition.

8 The eesults of Exp.B
8.1 Comparison the crossover tness 2 with
Random Crossover:The best tness
Fig.10 shows the change of average of the mean oft-ness every generation in the experiment using crossover
function 2 and the method of using random crossover.
This graph shows generally high evaluation in comparison with the method of using random crossover. As
for this experiment, it is a dicult task to solve it bymapping of the behavior toward the condition. And,
it increases in the 8

28 condition from 8 condition in

the Exp.A even if sensor value is shown by adding thegeneral idea of the light source direction by 2 value
simply. It increases by 1 condition 1 behavior in the8

28 condition from 8 condition in the Exp.A even if aapplied. When the crossover function 1 and an evaluation function 2 in this study were used, the operation
whose learning eciency was very good could be donein comparison with random crossover as a result of theexperiment. The validity of this method and its good
performance are con rmed through the experiments.

REFERENCES[1] Wolfgang Banzhaf, Peter Nordin, Robert E. Keller,

Genetic Programming {An Introduction; On the Automatic Evolution ofComputer Programs and its Applications. Morgan
and Frank D. Francone.

Figure 11: The moving locus(Ex2,Gen19).

Kaufmann, dpunkt.verlag, January 1998.

thing to solve shows sensor value by adding a conceptof the light source direction in addition to the diculttask by 2 value simply. This thing made the search of
the answer of the task a dicult thing, and a di erence
became easy to appear by the crossover being used as
the operation for the master conversely as results. It
faces the problem of the acquisition of the best value,
and it can think with the results which e ect appearedin.

A mean and test value showed the value which[2] Kenneth E. Kinnear, Jr. Alternatives in automaticfunction de nition: A comparison of performance.
In Kenneth E. Kinnear, Jr., editor, Advances in

Genetic Programming, chapter 6, pages 119{141.
MIT Press, 1994.
[3] John R. Koza. Genetic Programming II: Automatic

Discovery of Reusable Programs. MIT Press, Cambridge Massachusetts, May 1994.
[4] Peter Nordin and Wolfgang Banzhaf. Genetic Pro-

didn't almost change with before.

gramming Controlling a Miniature Robot. In E. V.
Fig.11 shows the example of a locus which a robot

Siegel and J. R. Koza, editors, Working Notes for

actually moves by using the evaluation function 2 in

the AAAI Symposium on Genetic Programming,

the Exp.B. A box is pushed, and it loses sight of apages 61{67, MIT, Cambridge, MA, USA, 10{12box soon for theNovember 1995. AAAI.

rst time as for the behavior of therobot of the generation whose it is early, too.

Thisis so that it can't take suitable behavior when it ishere with the program adapted to the change in theenvironment having not been made yet and a robot
leaving a box. The robot of the generation 20 changes a
direction when it is understood that a light source is in
the left though it faces in the light source direction anda box is being pushed a little to right. It is understood
more than this thing that the program which adapt
with that change is being made with recognizing thedirection which the light source direction and a box
touch.
We did an experiment by using the crossover function 2 the behavior acquisition of the robot could bethought to be done better more than the results of the
Exp.A by the task of the box push behavior again, andcompared that results with the method of using ran-

dom crossover. It was compared with the method ofusing random crossover in the best value, and it could
get high evaluation with the generation whose it was
early, and the e ectiveness of this technique became
clear as that results.

9 Conclusion
This paper proposed the novel crossover technique depending on the usage frequency of a node.

We hadthe experiment on-line learning which an actual robot
was used for with the system which this technique was[5] P.Nordin and W.Banzhaf.

An on-line method to

evolve behavior and to control a mini ature robot
in real time with genetic programming. In Adaptive

Behavior, pages 107{140, 1996.