RAM chip would be necessary to
accommodate a much larger array
on a PIC. “pop” and “pop_new” are
two-dimensional arrays that hold the
DNA strands for each member of the
population. We need two of them
because we are going to copy, slice,
and mutate the old generation stored
in “pop” to generate the new
generation stored in “pop_new.”
“mutation_rate” is a variable
which determines what percentage of
bits will be randomly mutated during
the breeding cycle. I made this a variable rather than a constant definition
because it is often advantageous to
adjust the mutation rate during evolution.
For example, you can start out with a
high mutation rate at the beginning
and pare it down to a low mutation
rate for final tweaking at the end.
Finally, the metric array contains the
ASCII coded letters of our solution,
• Lines 19-47
There are three peripheral
functions in the program: delay(),
quit(), and evaluate(index). The delay
function creates a 1,000 cycle pause
which is used in conjunction with the
serial commands to avoid overflowing
the LCD serial data receiving buffer.
The quit command simply moves the
program execution into an infinite
loop, freezing the last message on the
LCD. The evaluate function takes an
index as an argument and evaluates
how closely that index in the “pop”
array matches against the “metric”
array; in other words, how many
letters in the DNA are correct.
b. Create a new population using
crossover and mutation.
c. Evaluate the new population.
The first step is initializing our
variables, configuring the USART, and
clearing the LCD screen.
• Lines 66-78
The second section is the first
step of the genetic algorithm, creating
a random initial population. Now, I
should be clear here in saying that the
microcontroller does not generate
truly random numbers; rather it starts
with a number as a seed and uses
that number as the basis of
mathematical calculations which
generate a pseudo-random sequence
of integers. If the seed is the same,
the random integers will be the same
and the genetic algorithm program
will unfold exactly as before. I wanted
to see a lot of different variations of
the algorithmic solution, so I chose to
seed the random number generator
with the current value of timer1 which
is just a quick way to get a bunch of
different starting numbers for testing.
To create the DNA for the initial
population, a random number
between 95 and 122 was chosen by
scaling and offsetting the output of
the 15-bit random number generator.
This represents ASCII characters “_,”
“`,” and the lower case alphabet.
• Lines 81-98
The next step is to evaluate our
initial population and check to see if
any of the DNA managed to be 100%
correct on the first try.
• Lines 100-136
Then we enter our breeding loop,
which will terminate only when the
solution is found. For a more difficult
problem, you could add additional
clauses here to end the breeding loop
after a certain number of iterations, or
when a different fitness criteria is met.
The breeding loop contains a lot of
code, but is actually quite simple. First,
we find the fittest member of the
population and then we find the total
fitness of the population. With this
information, we go back through and
normalize the fitness values of each
member to reflect what percentage
they contribute to the whole
population’s fitness. With normalized
fitness values, we can create a
weighted breeding pool which
allows us to pick more fit parents
more often for breeding.
• Lines 137-199
From here, we start picking
parents from the breeding pool to
mate. Two parents are randomly
chosen, and their DNA is broken into
three pieces and interchanged to
create two new children with the
recombined information of their
parents. The final step in breeding is
to randomly mutate a percentage of
bits in the DNA based on our
“mutation_rate” parameter above.
• Lines 200-209
To maintain a certain level of
FIGURE 4. Evolving the phrase.
• Lines 49-64
The main function implements
the genetic algorithm framework we
looked at last time:
1) Create an initial population of
2) Evaluate the initial population.
3) While no member of the
population meets the criteria for
success (Breeding loop):
a. Select individuals into a mating
SERVO 05.2008 71