Evolutionary Methods and Evolutionary Computation 33
one of which is the mutation of nodes. Here, o nly the selec ted node is replaced
with another node.
The crossover ope rator in GAs and GP s ignificantly differ from other prob-
abilistic optimization mechanisms. The mutation operator searches nearby
structures by slightly changing good solutions. On the other hand, the
crossover operator aims to obtain better s olutions by combining good so-
lutions. For instance, in a function identification pr oblem to identify x
4
, the
partial str ucture x
2
has higher fitness compared to x. In fact, x
2
can be a
partial structure of x
4
. T he concept behind GP is that better solutions can be
obtained by repeatedly using crossover to co mbine good small partial struc-
tures called building blocks that formed, fo r example, through mutation.
Crossover in GAs is an exchange of partial sequences, and crossover in
GP is an extension where partial trees are exchanged. Here, partial trees are
chosen in two individuals selected through selection, and these se lec ted partial
trees are exchanged. Figure 2 .13(right) is an example of crossover in GP. 1 + x
and sin z are chosen as partial trees in this example. The crossover points
are selected at random; however, randomly selecting nodes without distin-
guishing ter minal and non-termina l nodes results in many exchanges of labe ls
between terminal nodes. Terminal nodes cannot be building blocks by them-
selves; therefore non-terminal nodes are preferentially chosen for cro ssover in
standard GP.
An important condition in ge netic operations in GP is that only individuals
with correct syntax are always generated when the above crossover or mutation
(except mutation of entire nodes) is used. GP uses tree structures to represent
genes so that the meaning is not destroyed by genetic operators.
2.3.6 Simulating wall following robots
Let us attempt to evolve a progr am for controlling a robot using GP. The
task here is to obtain a program that causes the robot to follow a wall (this
could be useful for controlling a cleaning robot, since dust tends to gather
against walls). The robot is capable of four motions: to move forward, move
back, turn right, and turn left. It has a group of se nsors that provide a 360-
degree view . It is placed in an irre gular room (i.e., a n asymmetric room) and
commanded to move about the periphery of the roo m, following the wall as
accurately as possible.
This kind of progra m is easy to write in Lisp [76]. Let us begin with the
adaptive learning necessary to s olve this problem with the GP.
The robo t is as sumed to have 12 sonar sensors (s00–s11) (see Fig. 2.14).
The four motions permitted to the robot are straight ahead, straight back,
turn left (+30 degrees ), and turn right (−30 degrees). Since this GP carries
out learning, the terminal nodes T are
T = {S00, S01, ··· , S11, ℜ}
where S00, S01, ··· , S1 1 are the values output by the 12 distance sensors. ℜ is
34 Agent-Based Modeling and Simulation with Swarm
S06=12.5
S03=11.5
S04=7.5
S02=11.5
S01=10.5
S07=12.5
S08=11.5
S09=7.5
S00=12.0
S11=11.5
S10=8.0
S05=5.5
FIGURE 2.14: Robot sensors.
a random number variable (it is generated randomly when initially evaluated,
i.e., it is g e nerated once per terminal node). The non-terminal nodes F are
F = {TR, TL, MF, MB, IFLTE, PROGN2},
where TR and TL are functions for turning the robot 30 degrees right and
left, respectively, whereas MF and MB are functions for moving the robo t 1
fo ot forward or back, respectively. These functions do not accept arguments.
It is assumed that execution of these functions takes 1 time unit, and that the
sensor outputs are changed dynamically after execution. Two more functions
are incorporated in order for the model to learn the appropriate co ntrol rela-
tionships. IFLTE (if-less-than-equal) takes four arguments and is interpreted
as follows:
(IFLTE a b x y) ⇒ if a ≤ b, then execute x and return the result.
if a > b, then execute y and the r e sult.
PROGN2 takes 2 arguments, executes them in order and returns the value
of the se c ond.
Figure 2.15 presents the wall following simulator by means of GP. The
robot moves about the displayed field. Use this simulator to create a program
for the desired robot. The robot program will be executed according to a
program displaying the GTYPE for a period of 400 time units. The fitness
will be determined by how many of the round green circles (tiles) are crossed.
Readers s hould refer to Appendix A.4 for instructions about this simulator.
The generated program always has to cope with even small changes in the
environment (such as shifts of the position of the chair in the r oom). T his
is what is meant by “robustness” of the program. It is not easy for a human
to write this kind of program for a robot; in contrast, GP can perfo rm the
necessary searches quite efficiently in order to write such a program.
Evolutionary Methods and Evolutionary Computation 35
FIGURE 2.15: Wall following by GP.
2.4 What is interactive evolutionary computation?
Let us consider the application of evolutionary co mputation (EC) to prob-
lems such as designing tables tha t match the atmosphere o f a room or com-
posing unobtrusive ringtones for mobile phones.
EC might se e m applicable to these problems if they are considered in
terms of optimizing the size and color of the bo ards in the case of the tables,
or the frequencies, filters, and other parameters in the c ase of the synthe-
sizers. However, the problem in this situa tion is how to evaluate each unit.
An evolutionary system based on the survival of the fittest must include a
method for evaluating whether individua l units are suitable for their environ-
ment; in other words, how close they are to the optimal solution. For example,
when using GA to evolve to a solution to the shortest path for the traveling
salesman problem (TSP), the solution represented by each unit is assigned a
degree of fitness in terms of path length (see Section 2 .2.7). Is it possible to
use a computer in the same manner to determine whether a table matches
the atmosphere of a room? Unfortunately, modeling a subjective evaluation
process based on human preferences and feelings, and then implementing such
a model on a computer, is an extremely difficult task.
For instance, consider the fitness function in the case of a computer drawing
a portrait. Conceivably, the firs t step is to compute the Euclidean distance
between the structural information of a face extracted from a photograph and
36 Agent-Based Modeling and Simulation with Swarm
1
FIGURE 2.16:
IEC algorithm.
the portrait drawn by the computer. However, drawing a portra it is not the
same as creating a photorealistic representation of a face—rather, drawing a
portrait involves the more interesting process of capturing the unique features
of the face and then drawing them in a stylized manner. However, can a
computer determine whether a person is identical in a facial photograph and
a portrait in which specific fa c ial features are captured and stylized? This
fitness problem is considered to be extremely difficult to implement using the
existing level of technology.
Nevertheless, there is s omething close to all o f us that is capable of per-
forming such evaluations instantaneously: the brain. Humans have evolved a
method for direct evaluation of individual units, and in this regard, the hu-
man evaluation system can be incorporated into a n optimization system a s
an evaluation function. Thus, when EC is employed for optimization bas e d
on human subjective evaluation, this process is then referred to as interactive
evolutionary computation (IEC) [10, 116].
Put simply, IEC is EC in which a human is subs tituted for the fitness
function. In IEC, the person using the system (the user) directly evaluates each
unit, and the viability (fitness) of subsequent generations is derived depending
on user preference s (Fig. 2.16). When implementing this system, personal
preferences and sensations are not modeled, and evaluation bas e d on user
subjectivity is incorporated into the system as a black b ox. In contrast to
conventional EC, where evolution is modeled as the result of a struggle for
survival, IEC is inspired by the pr ocess underta ken by humans of intentionally
breeding agricultural products and domestic animals.
Modern keywor ds such as “ e motional (kansei) engineering” and “humanized
technology” reveal the increasing tendency for technology to make use of hu-
man subjectivity. As part of this trend, IEC is b e ginning to attract attention
as a method able to incor porate the user’s subjective eva luation system.
Evolutionary Methods and Evolutionary Computation 37
FIGURE 2.17: CG synthesis of plants based on L-systems.
Various type s of human evaluation scales are used in IEC. For example,
psychological experiments often use a scale with at most 7 grades, although
a scale with 10 or 100 grades would cer tainly increase c larity in e veryday
situations. In contrast, for two-step evaluation, members of the population can
be either selected (or not) as a parent for the next generation. This process
is referred to as “simulated breeding” [121], since it is ana logous to artificial
breeding, in which des irable features are se lec ted and then bred.
In his 1986 book The Blind Watchmaker [24], Richard Dawkins, the well-
known author of The Selfish Gene, describes how images created according
to s imple rules can evolve into extr e mely complex and intriguing images as a
result of rule mutation and user s e lec tion. These image seque nce s were called
biomorphs, since they appear to resemble animals (e.g., insects) at first sight.
Biomorphs can be regarded as the first example of IEC, specific ally, evolu-
tion artificially created with a computer through selection based on human
subjective preferences.
Hence, IEC offers a new creative technique based on user selections. Since
many artists and res e archers were attracted to this method after being cap-
tivated by biomorphs, the initial focus of IEC research was in artistic fields,
particularly the application of IEC in computer graphics (CG) [106]. Such
applications cover a number of areas , including CG synthesis of plants based
on L-sys tems (Fig. 2.17, see also Appendix A.5), portr ait synthesis, graphic
art, three-dimensional (3D) CG synthesis for virtua l reality, avatar motio n
design [122], and animation [10]. Below, we focus on graphic art and design
as a representative IEC application.
Simulated Breeding for ART (SBART) [121] use s genetic programming
(GP) to create 2D images and is an exa mple of an IEC-based graphic art
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.