Agent-Based Models and Optimal Control in Biology: A Discrete Approach - Mathematical Concepts and Methods in Modern Biology - page 161

are often satisfied with a solution that is better than any previously known. As such,
the heuristic approach to optimal control is a valuable option.
Of course, every heuristic algorithm has associated risks and advantages, and the
particular algorithm that is best suited for a given model or problem will depend on
these. As an introduction to the heuristic approach, we describe a so-called genetic
algorithm in some detail, in the context of the “Rabbits andGrass”model.We conclude
this section with a list of other heuristic algorithms.

5.7.1 Genetic Algorithms
Genetic algorithms (sometimes referred to as evolutionary algorithms) were origi-
nally developed as a means of studying the natural evolution process, and have been
adapted for use in optimization since the 1960s [ 12 - 14 ]. Each solution is viewed
as a chromosome. The chromosome is a string of values, or genes, each of which
represents the value of one of the parameters. Each chromosome, then, represents
an individual solution that can be implemented and whose associated cost can then
be evaluated. A typical genetic algorithm functions in the following way: several
chromosomes are selected to form a population. The cost of each is then evaluated.
The chromosomes are ordered, beginning with the chromosome that produces the
minimum cost. The best half (i.e., those with lower associated cost) of the chromo-
somes are then selected to carry on to the next generation; that is, they will be kept
in the list to be evaluated later. Then the process of breeding comes into play: two
random chromosomes from those that have been carried over are selected to serve as
parents. A “child” chromosome (i.e., a new solution) is then bred from these parents
by some method of crossover ( uniform crossover is a typical method in which there
is an equally likely chance that the child will take each particular gene from either
parent). The next step is mutation : each gene has the possibility of being mutated at
random, changing from its current value to any admissible value of that gene. The
child chromosome produced from such breeding is added to the next generation of
solutions. This process is repeated until the remaining half of the new population has
been re-populated with new child chromosomes. The entire process is then repeated:
the chromosomes are evaluated and the best are set aside, new chromosomes are bred
from them, and so on.
The control objective with the “Rabbits and Grass” model was to determine a
control schedule that minimized the number of rabbits while also minimizing the
number of days on which poison was used. Suppose we wish to achieve this goal
over the course of 10 days. Then a solution is a vector of length 10, each entry
of which is either 0 or 1. Suppose we begin with two randomly chosen solutions,
p 1

. We create a “child” solution by going
through each gene (i.e., each entry in the parent solutions) and randomly selecting
one of the values. See Figure 5.4 for an example of such a “child” solution. The child
solution is then subjected to mutation; see Figure 5.5 for an example.
The algorithm continues for a pre-determined number of steps, or until a certain
condition is met. For example, we may choose to run the algorithm for 50 generations.

=[ 0101010101 ] , p 2 =[ 1110110010 ]