Reproduction, crossover, and mutation
David E. Goldberg. Genetic Algorithms in search, optimization and machine learning. Addison Wesley Longman, Inc., 2002.// Chapter3. Computer Implemenattion of a Genetic Algorithm, p. 62-65. The three operator of the simple tripartite algorithm can each be implemented in straightforward code segments. This comes as no surprise, since we have been touting the simple mechanics of these operators. Before we look at each routine, we must remember the common thread running through the three operators: each depends on random choice. In the code segments that follow, we assume the existence of three random choice riutines:
In the simple genetic algorithm, reproduction is implemented in the function select as a linear search through a roulette wheel with slots weighted in proportion to string fitness values. In the code shown in Fig. 3.5, we see that select returns the population index value corresponding to the selected individual. To do this, the partial sum of the fitness values is accumulated in the real variable partsum. The real variable rand contains the location where the wheel has landed after a random spin according to the computation:
rand:= random * sumfitness
Here the sum of the population fitnesses (calculated in the procedure statistics) is multiplied by the normalized pseudorandom number generated by random. Finally the repead-until construct searches through the weighted roulette wheel until the partial sum is greater than or equal to the stopping point rand. The function returns with the current population index value j assigned to select.
function select(popsize:integer; sumfitness: real; var pop:population):integer;
{select a single individual via roulette wheel selection}
var
rand, partsum:real; {random point on wheel, partial sum}
j:integer; {Population index}
begin
partsum:=0.0; j:=0; {Zero out counter and accumulator}
rand:=random*sumfitness; {Wheel point calc. Uses random number [0,1]}
repeat {Find wheel slot}
j:=j+1;
partsum:=partsum+pop[j].fitness;
until (partsum>=rand) or (j=popsize);
{Return individual number}
select:=j;
end;
Figure 3.5 Function select implements roulette wheel selection.
This is perhaps the simplest way to implement selection. There are more efficient codes to implement this operator (a binary search will certainly speed things up), and there are many other ways to choose offspring with appropriate now we stay with this basic mechanism.
The code segment select gives us a straightforward way of choosing offspring for the next generation. From our previous descriptions. We know our next step is crossover. In SGA the crossover operator is a procedure that we, cleverly enough, have called crossover (Fig. 3.6). The routine crossover takes two parent strings called parent1 and parent2 and generates two offspring strings called child1 and child2. The probabilities of crossover and mutation, pcross and pmutation, are passed to crossover, along with the string length lchrom, a crossover count accumulator ncross, and a mutation count accumulator nmutation.
procedure crossover (var parent1, parent2, child1, child2: chromosome; var lchrom, ncross, nmutation, jcross:integer; var pross, pmutation:real);
{cross 2 parent strings, place in 2 child strings}
var j:integer;
begin
if flip(pcross) then begin {Do crossover with p(cross)}
jcross:=rnd(l,lchrom-1); {Cross between 1 and 1-1}
ncross:=ncross+1; {Increment crossover counter}
end else {Otherwise set cross site to force mutation}
jcross:=lcross;
{1st exchange, 1 to 1 and 2 to 2}
for j:=1 to jcross do begin
child1[j]:=mutation(parent1[j], pmutation, nmutation);
child2[j]:=mutation(parent2[j], pmutation, nmutation);
end;
{2nd exchange, 1 to 2 and 2 to 1}
if jcross<>lchrom then {Skip if cross site is lchrom-no crossover}
for j:=jcross+1 to lchrom do begin
child1[j]:=mutation(parent2[j], pmutation, nmutation);
child1[j]:=mutation(parent1[j], pmutation, nmutation);
end;
end;
Figure 3.6 Procedure crossover implements simple (single-point) crossover.
Within crossover the operations mirror our description in Chapter 1. At the top of the routine, we determine whether we are going to perform crossover on the current pair of parent chromosomes. Specifically, we toss a biased coin that comes up head (true) with probability pcross. The coin toss is simulated in the boolean function flip, where flip in turn calls on the pseudorandom number routine random. If a cross is called for, a crossing site is selected between 1 and the last cross site. The crossing site is selected in the function rnd, which returns a pseudorandom integer between specified lower and upper limits (between 1 and lchrom - 1). If no cross is to be performed, the cross site is selected as lchrom (the full string length l) so a bit-by-bit mutation will take place despite the absence of a cross. Finally, the partial exchange of crossover is carried out in the for-do constructs at the end of the code. The first for-do handles the partial transfer of bits between parent1 and child1 and between parent2 and child2. The second for-do construct handles the transfer and partial exchange of material between parent1 and child2 and between parent1 and child1. In all cases, a bit-by-bit mutation is carried out by the boolean (or allelean) function mutation.
Mutation at a point is carried out by mutation as shown in Fig. 3.7. this function uses the function flip (the baised coin toss) to determine whether or not to change a true to a false (a 1 to a 0) or vice versa. Of coure the function flip will only come up heads (true) pmutation percent of the time as a result of the call to the pseudorandom number generator random within flip itself. The function also keeps tabs on the number of mutations by incrementing the variable nmutation. As with reproduction, there are ways to improve our simple mutation operator. For example, it would be possible to avoid much random number generation if we decided when the next mutation should occur rather than calling flip each time. Again, in this chapter, we avoid sophisticated niceties and ctick with the basics.
The three main pieces of our genetic algorithm puzzle have proven to be none too puzzling. We have seen in this section how the may be easily coded and easily understood. The next section continues piecing together the bigger GA picture as we coordinate reproduction, crossover, and mutation in a single generation.
function mutation(alleleval:allele; pmutation:real; var nmutation:integer):allele;
{Mutate an allele w/ pmutation, count number of mutations}
var mutate:boolean;
begin
mutate:=flip(pmutation); {Flip the biased coin}
if mutate then begin
nmutation:=nmutation+1;
mutation:=not alleleval; {Change bit value}
end else
mutation:=alleleval; {No change}
end;
Figure 3.7 Function mutation implements a single-bit, point mutation.