164 Agent-Based Modeling and Simulation with Swarm
6.6.1 Evolution of predatory behaviors using genetic search
This section introduces the fundamental idea of BUGS. We can exper-
imentally verify the evolution of bugs w hich possess “predatory b e haviors,”
i.e., the evolution of bugs that lear n to hunt bacteria. The o riginal motivation
for these experiments was derived from [29]. Bugs lear n to move to those re-
gions in the search space where the bacterial concentration is highest. Since
the bug concentration is set up to be proportional to the local value of the
function to be maximized in the search space, the “stabilized” bug concen-
trations are proportional to these sea rch space values. Hence the bugs learn
(GA style) to be hill climbers. A Swarm-based BUGS simulator is available
for readers’ self-study. The details are given in Section 6.7.
6.6.1.1 Bugs hunt bacteria
Figure 6.24 (a) illustrates the world in which bugs (large dots) live (a 512 ×
512 cellular grid). They feed on bacteria (small dots) which are continually
being deposited. The normal bacterial deposition rate is roughly 0.5 bacter ium
per (GA) generation over the whole grid. Each bug has its internal energy
source. The maximum energy supply of a bug is set at 1500 units. When a bug’s
energy supply is exhausted, the bug dies and disappears. Each bacterium eaten
provides a bug with 40 units of energy, which is enough to make 40 moves,
where a move is defined to be one of six possible directional displacements of
the bug, as shown in Fig. 6.25.
A bug’s motion is determined by coded instructions on its gene code.
The six directions a bug can move are labeled F, R, HR, RV, HL, and L for
Forward, Right, Hard Right, Reverse, Hard Left, and Left, respe c tively. The
GA chromosome for mat for these bugs is an intege r vector of size six where
the elements of the vector correspond to the directions in the following order:
(F,R,HR,RV,HL,L), e.g., (2,1,1,1,3 ,2) (as shown in the window in Fig. 6.24(a)).
When a bug is to make a move , it will move in the direction d
i
(e.g., d
3
= HR)
with a probability p(d
i
), which is determined by the following formula:
p(d
i
) =
e
a
i
P
6
j=1
e
a
j
(6.20)
where a
i
is the ith component value of the chromosome vecto r (e.g., a
5
= 3
above). O nce a move is made, a new directional orientation s hould be deter-
mined. Figure 6.25 shows the new F
next
directions, e.g., if the move is R, the
new forward direction will be to the right (i.e., east). For instance, a bug with
a gene code of (1,9,1,1,1,1) tur ns frequently in direction R so that it is highly
likely to move in a circle.
After 800 moves (i.e., when it attains an “age” of 800), the bug is said
to be “ma ture” and is ready to reproduce if it is “strong” (i.e., its energy is
greater than a threshold value of 1000 energy units). There are two types of
reproduction, asexual and sexual (see Fig. 6.26). With asexual re production,
a strong mature bug disappears and is replaced by two new bugs (in the same
Particle S warm Simulation 165
(a)
(b)
FIGURE 6.24: Bug world: (a)166th generation, (b) 39, 618th genera tion.
166 Agent-Based Modeling and Simulation with Swarm
FIGURE 6.25: Bug’s gene code.
cell on the grid). Each daughter bug has half the energy of its parent. The
genes of each daughter bug are mutated as follows. One of the comp onents of
the directional 6-vector is chosen with uniform probability. The value of the
direction is r e placed by a new value chosen with uniform probability (over
the integer range of, e.g., [0,10]). Sexual reproduction occurs when two strong
mature bugs “meet” (i.e., they move within a threshold distance from each
other called the “reproductive radius” ). The distance between two pa rents is
defined as the Euclidean dista nce between the two parents. The reproductive
radius is set at 10.0 . T he two parents continue to live and are joined by
the two daughter bugs. Each parent loses half of its energy in the sexual
reproductive process. As a result, two children are born whose energies are
half the average of the parents’ energies. The children’s genes are obtained
by applying mutation and uniform crossover operators to the parents’ genes.
Thus, these reproductions are constrained by pr obabilities.
Figure 6.24(b) shows the results o f the first simple evolutionary e xpe ri-
ment. The simulation began with ten bugs with random genetic structures.
Most of the bugs jittered from side to side unpredictably and are called “jitter-
bugs.” They are likely to starve to death because they eat up most of the food
in their immediate vicinity and are unable to explore widely. In time “cruiser”
bugs evolve, which move forward most of the time and turn left or right oc-
casionally. Note that if a bug hits an edge of the grid, it stays there until an
appropria te move displaces it away from that grid edge. These “cruiser” bugs
succeed in finding food and thus dominate the entire population. A typical
chromosome for a “cr uis e r” bug is shown in the sub-window of Fig. 6.24(b),
Particle S warm Simulation 167
(a) Bugs hunt for bacteria
(b) Asexual reproduction (c) Sexual reproduction
FIGURE 6.26: A schematic illustration of bugs.
i.e., (9,6 ,0,2,4,1). T he remar kable features of this chromosome vector ar e as
follows:
(1) The forward gene (F) is large (9).
(2) The reverse gene (RV) is small (2).
(3) One of the Right (R), Left (L), Hard Right (HR), and Hard Left (HL)
is of moderate s ize (6).
The second feature is impo rtant because bugs with large “reverse” (RV)
gene values c reate “twirlers,” which make to o many turns in one direction.
Such unfortunate creatures usually die. The third feature is also esse ntial,
because intelligent bugs have to avoid loitering around wall edges.
168 Agent-Based Modeling and Simulation with Swarm
FIGURE 6.27: Types of bugs.
6.6.1.2 Effectivenes s of sexual reproduction
Dewdney’s original paper used only mutation operators, i.e., asexual re-
production. Sexual reproduction is introduced in bugs to increase the effective
evolution of bugs [54]. It can be experimentally shown that the speed of evo-
lution is higher with sexual reproduction. In the first experiment, we c an
statistically compare the performance rates, where the performance of bugs
at generation t is defined a s follows:
P erf ormance(t) =
9
X
i=0
P erf (t − i), (6.21)
where
P erf (k) =
#Eaten(k)
#Bac (k) × #Bug(k)
(6.22)
#Bug(k) = (no. of bugs at the kth generation) (6.23)
#Bac (k) = (no. of bacteria at the kth generation) (6.24)
#Eaten(k) = (no. of bac teria eaten by bugs at the kth generation) (6.25)
This indicates how many ba c teria a re eaten by bugs as a whole in the last
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.