A Simple Genetic Algorithm
(from Genetic Algorithms by David Goldberg)
A simple genetic algorithm that yields good results in many practical
problems is composed of three operators:
1. Reproduction
2. Crossover
3. Mutation
Reproduction is a process in which individual strings are copied
according to their objective function values, f (biologists call this
function the fitness function). Copying strings according to their
fitness values means that strings with a higher value have a higher
probability of contributing one or more offspring in the next generation.
This operator is an artificial version of natural selection, a Darwinian
survival of the fittest among string creatures.
One easy way to implement the reproduction operator is to create a
biased roulette wheel where each current string in the population has
a roulette wheel slot sized in proportion to its fitness.
Suppose the sample population of four strings has objective or fitness
values f as follows:
No. String Fitness % of total
-----------------------------------------
1 0 1 1 0 1 169 14.4
2 1 1 0 0 0 576 49.2
3 0 1 0 0 0 64 5.5
4 1 0 0 1 1 361 30.9
-----------------------------------------
Sum 1170 100.0
Summing the fitness over all four strings, we obtain a total of 1170.
The percentage of population total fitness is also shown in the table. The
corresponding weighted roulette wheel for this generation's reproduction
is shown below. To reproduce, spin the weighted roulette wheel four times.
For this example, string number 1 has a fitness value of 169, which
represents 14.4 percent of the total fitness. As a result, string 1 is
given 14.4 percent of the biased roulette wheel, and each spin turns up
string 1 with probability 0.144. Each time we require another offspring, a
spin of the weighted roulette wheel yields the reproduction candidate.
In this way, more highly fit strings have a higher number of offspring in
the succeeding generation. Once a string has been selected for
reproduction, an exact replica of the string is made. This string is then
entered into a mating pool, a tentative new population, for further
genetic operator action.
After reproduction, simple crossover may proceed in two steps. First,
members of the newly reproduced strings in the mating pool are mated at
random. Second, each pair of strings undergoes crossing over as follows:
an integer position k along the string is selected uniformly at random
between 1 and the string length less one [1, len(str)-1]. Two strings are
created by swapping all characters between positions k + 1 and len(str)
inclusively. For example, consider the two strings A1 and A2:
A1 = 0 1 1 0 | 1
A2 = 1 1 0 0 | 0
Suppose k = 4. The resulting crossover yields two new strings:
A1new = 0 1 1 0 0
A2new = 1 1 0 0 1