The Canonical Genetic Algorithm
The Simple Genetic Algorithm (more or less), as described by David Goldberg.In the early eighties, David Goldberg published a book, Genetic Algorithms in search, optimization, and machine learning. In this book he describes what makes genetic algorithms work, and introduces the simple genetic algorithm: an evolutionary algorithm based on binary strings, with crossover along with mutation as variation operator, and fitness-proportionate selection. This is the algorithm we implement in the next example ( canonical-ga.pl.
(1) use Algorithm::Evolutionary::Wheel; require "LittleEA.pm"; my $generations = shift || 500; #Which might be enough my $popSize = 100; # No need to keep it variable my $targetString = 'yetanother'; my $strLength = length( $targetString ); my @alphabet = ('a'..'z'); sub fitness ($;$) { my $string = shift; my $distance = 0; for ( 0..($strLength -1)) { $distance += abs( ord( substr( $string, $_, 1)) - ord( substr( $targetString, $_, 1))); } return $distance; } my @population = initPopulation( $popSize, $strLength, \@alphabet ); printPopulation( \@population); @population = sort { $a->{_fitness} <=> $b->{_fitness} } @population; for ( 1..$generations ) { (2) my @newPop; my @rates; for ( @population ) { push @rates, 1/$_->{_fitness}; (2) } (3) my $popWheel=new Algorithm::Evolutionary::Wheel @rates; for ( my $i = 0; $i < $popSize/2; $i ++ ) { my $chr1 = $population[$popWheel->spin()]; (3) my $chr2 = $population[$popWheel->spin()]; my $clone1 = { _str => $chr1->{_str}, _fitness => 0 }; my $clone2 = { _str => $chr2->{_str}, _fitness => 0 }; mutate( $clone1, \@alphabet ); mutate( $clone2, \@alphabet ); crossover( $clone1, $clone2 ); $clone1->{_fitness} = fitness( $clone1->{_str} ); $clone2->{_fitness} = fitness( $clone2->{_str} ); push @newPop, $clone1, $clone2; } @population = sort { $a->{_fitness} <=> $b->{_fitness} } @newPop; print "Best so far: $population[0]->{_str}\n"; printPopulation( \@population ); last if $population[0]->{_fitness} == 0; } |
- (1)
- Declaration of a class that belongs to the Algorithm::Evolutionary module. This module will be used extensively in the second chapter; so far, if you feel the need, download it from the SF web site. This module is for creating roulette wheels that are biased with respect to probability: the probability that the "ball" stops at one of its slots is proportional to its probability.
- (2)
- The probabilities for the wheel are created, taking into account fitness. Since, in this case, lower fitness is better, fitness has to be inverted to create the roulette wheel; that way, individuals with lower fitness (closest to the target string) will have a higher chance of being selected
- (3)
- A Wheel object is created, and used later on to select the individuals that are going to be cloned and reproduced.
The canonical genetic algorithm is the benchmark against any new algorithm will be measured; it performs surprisingly well along a wide range of problems, but, in this case, it is worse than our previous example, as is shown in the next plot:
Evolution of the fitness of the best individual for the canonical GA. It needs 160 generations (in this case) to reach the optimum, which is worse than the best cases before. Actually, in simple problems, strategies that favor exploitation over exploration sometimes are more successful than the canonical GA, however, this is always useful as a first approximation. It should be noted also that, unlike previous examples, since the best of the population are not kept from one generation to the next, fitness can actually decrease from one generation to the next.
The canonical genetic algorithm manages to keep a good balance balanced between exploration and exploitation, which is one of its strong points; this makes it efficient throughout a wide range of problems. However, its efficiency can be improved a bit by just keeping a few good members of the population; that way, at least we make sure that the best fitness obtained does not decrease. That members will be called the elite, and the mechanism that uses them, elitism. We will introduce that mechanism in the next instance of the example, canonical-ga-elitism.pl, which is substantially similar to the previous one, except that the first two chromosomes of each generation are preserved for the next. Results obtained are shown in the following plot:
A comparison of the evolution of the canonical GA, with and without elitism. Elitism performs better, obtaining the same result in a third as many generation.
Surprisingly enough, this improvement comes at little cost; there is no significant diminution in diversity during the run, maintaining a good pool of different strings all the time (you can use the freqs.pl program to check that, if you feel like it).
 | Keeping track of the best-fit chromosomes, and reintroducing them at the next generation, improves performance if done wisely; without the cost of a loss of diversity that can degrade performance in more complex problems. |
Even if now, the exact data structure that is being evolved is not that important, original genetic algorithms used, mainly for theoretical reasons (respect the sieve of schemas), binary strings. And one of the most widely used benchmarks for binary-string evolutionary algorithms (or simply GAs), is the "count ones" problem, also called "ONEMAX": in this problem, the target string consists of all ones. This problem is solved in the next program (canonical-classical-ga.pl)
(1) use Algorithm::Evolutionary::Wheel; require "LittleEA.pm"; my $numberOfBits = shift || 32; my $popSize = 200; # No need to keep it variable (1) my @population; sub fitness ($;$) { my $indi=shift; my $total = grep( $_ == 1, split(//,$indi )); return $total; } sub mutateBinary { my $chromosome = shift; my $mutationPoint = rand( length( $chromosome->{_str})); my $bit = substr( $chromosome->{_str}, $mutationPoint, 1 );(2) substr( $chromosome->{_str}, $mutationPoint, 1, $bit?1:0 ); } for ( 1..$popSize ) { my $chromosome = { _str => '', _fitness => 0 }; (2) for ( 1..$numberOfBits ) { $chromosome->{_str} .= rand() > 0.5?1:0; } $chromosome->{_fitness} = fitness( $chromosome->{_str} ); push @population, $chromosome; } printPopulation( \@population ); @population = sort { $b->{_fitness} <=> $a->{_fitness} } @population; do { my @newPop; my @rates; for ( @population ) { push @rates, $_->{_fitness}; } my $popWheel=new Algorithm::Evolutionary::Wheel @rates; for ( my $i = 0; $i < $popSize/2; $i ++ ) { my $chr1 = $population[$popWheel->spin()]; my $chr2 = $population[$popWheel->spin()]; #Generate offspring that is better my $clone1 = { _str => $chr1->{_str}, _fitness => 0 }; my $clone2 = { _str => $chr2->{_str}, _fitness => 0 }; mutateBinary( $clone1 ); mutateBinary( $clone2 ); crossover( $clone1, $clone2 ); $clone1->{_fitness} = fitness( $clone1->{_str} ); $clone2->{_fitness} = fitness( $clone2->{_str} ); push @newPop, $clone1, $clone2; } @population = sort { $b->{_fitness} <=> $a->{_fitness} } @newPop; #Print best print "Best so far: $population[0]->{_str}\n"; } until ( $population[0]->{_fitness} == $numberOfBits ); print "We're done\n"; printPopulation( \@population ); |
- (1)
- The first lines of the program differ a bit: it takes as an argument the number of bits, and the population is bigger. Fitness is also different: the fitness subroutine splits the binary strings to count the number of ones, which is returned.
- (2)
- The mutateBinary subroutine is also different: after selecting a position to mutate, it flips the bit in that position. A mutation operator that flips several bits could be thought of, but the same effect is achieved with several applications of the same operator. More complicated mutation operators use "hot spots" to mutate, or evolve the mutation rate, or change the probability of mutation for each locus in the chromosome. Sometimes, these strategies improve performance, some others are not worth the hassle.
As expected, this program finds the solution eventually; it is only shown here for historical reasons. Just by changing the fitness function, many problems that admit a binary codification could also be solved, from the MAXSAT optimization problem, to the well-known traveling salesperson problem.