Biology Reference
In-Depth Information
p
1
=[
01
0
1
01
01
0
1
]
p
2
=[11
1
0
11
00
1
0]
p
new
=[0111110111]
FIGURE 5.4
Uniform crossover to “breed” a new solution.
[0
1
1111011
1
]
[0011110110]
FIGURE 5.5
Bold values are subjected to mutation.
Another method is to repeat the process until no better solution has been found for,
say, ten consecutive generations. When the algorithm terminates, we choose the best
current solution as our candidate for an optimal solution (note that there is no guarantee
that the best solution found by the algorithm is actually the optimal solution; recall
that we use
optimal solution
to mean the best solution we are able to find).
As with other heuristic algorithms, there are many variations and the one presented
here is provided as a standard procedure. We may modify the algorithm, for example,
so that the initial chromosomes are selected in a certain way: perhaps we wish to
choose them at random, or perhaps we wish to choose chromosomes that are very
different from one another (i.e., solutions that come from different regions of the solu-
tion space). We may modify the crossover process so that one parent is favored over
another, or we may forego the mutation step altogether. The likelihood of mutation
is another area where user input is important: a high level of mutation will result in
more variation of child chromosomes, and thus will not incorporate the relative fitness
of the parent chromosomes as much. On the other hand, if the mutation step is not
included then we run a greater risk of our solution converging to some solution that is
only locally minimal; that is, it may be better than all of the solutions that are similar
to it, but not necessarily better than solutions that are radically different (we may
think of these solutions as being farther away in the solution space). The advantage
of using a genetic algorithm is that there is inherently some level of stochasticity;
that is, there is always the possibility of mutating to a better solution (as long as the
mutation rate is nonzero).
For the following exercises, use Netlogo to open the file entitled
Rabbits-
Grass-GA.nlogo
, available at
http://admg.vbi.vt.edu/software/rabbitsgrass-
netlogo-files/
. This file runs a genetic algorithm to attempt to determine the best
poison schedule based on the cost function given in the model (the schedule which
minimizes the number of rabbits and the days on which poison is used). Read the
“Info” tab for information on each of the options. In addition, you may need to exam-
ine the code in this model in order to complete all exercises.
Search WWH ::
Custom Search