Page 139 - Innovations in Intelligent Machines

130 A. Pongpunwattana and R. Rysdyk
G G

Mutate

Fig. 9. Go-to-goal segments are added at the end of each mutated path to force the
path to end at the goal location

to Mutate 1-Point), and then connects back to the start of another seg-
ment of the path further along. The beginning segment and the segment
joined to are both chosen at random.
– Crossover: takes the starting segments of one path and the ending seg-
ments of another and joins the two sets of segments together.
– Mutate Expand: adds one or more randomly created segments onto the
end of the path. All the original parts of the path are left untouched.
– Mutate Shrink: removes one or more segments from the end of the path.
The number of segments to be removed are selected at random.
Some of these mutation mechanisms require a method to construct of join-
ing segments which connect the ending point of a segment of a path being
mutated to the starting point of another segment while maintaining the con-
tinuity of the whole path. The methods used to compute joining segments
are presented in [19]. For a particular joining, all three methods are used, but
the resulting path with the shortest total length is selected. Once a new path
is created through the mutation process, a set of segments called go-to-goal
segments are added to the mutated path. This modification makes all paths
in the population end at the goal location. This procedure is illustrated in
Figure 9.

Selection Scheme

Given a population of the size µ + λ, the selection scheme is a mechanism
for selecting µ individuals to be parents of the n th generation. These µ par-
ents will be used to create λ offspring in the next mutation process. Many
types of selection schemes can be used in the evolution process. In this
research, a q-fold binary tournament selection scheme is chosen. Figure 10
illustrates the procedures of the selection scheme which can be described as
follows.