Doing Evolutionary Algorithms with Algorithm::Evolutionary

And other Perl modules

And other Perl modules

This chapter revisits the evolutionary algorithms we have seen so far, and then some, by using an evolutionary algorithm module (which might be in CPAN by the time you read this) called (what else?) Algorithm::Evolutionary. This module has been designed by the author to be flexible, integrated with XML, Perlish and easy to extend. We will also show how this library works with other Perl modules.

Introduction to evolutionary algorithms in Perl

So far, there have been many attempts to create evolutionary algorithm modules and programs in Perl; most have concentrated in implementing Genetic Programming, and some have been geared to a particular application, like the GlotBot. The closest thing one can get in CPAN is the AI::Gene modules, which were intended for creating the basic infrastructure for an evolutionary algorithm devoted to fighting spam. The canonical genetic algorithm, implemented using AI::Gene, would be as follows: ( cga-ai-gene.pl):

use AI::Gene::AI::Gene::Simple;                            (1)
package MyGene;
our @ISA = qw (AI::Gene::Simple);
sub render_gene {
  my $self = shift;
  return (join '', @{$self->[0]});
}
sub mutate_minor {
  my $self = shift;
  my $num = +$_[0] || 1;
  my $rt = 0;
  for (1..$num) {
    my $glen = scalar @{$self->[0]};
    my $pos = defined $_[1] ? $_[1] : int rand $glen;
    next if $pos >= $glen;  # pos lies outside of gene
    my $token = $self->generate_token();
    $self->[0][$pos] = $token;
    $rt++;
  }
  return $rt;
}                                                         (1)
package main;
use Algorithm::Evolutionary::Wheel;
my $generations = shift || 500; #Which might be enough
my $popSize = 100; # No need to keep it variable
my $targetString = 'yetanother';
my $strLength = length( $targetString );                  (2)
sub fitness ($;$) {
  my $ary = shift;
  my $distance = 0;
  for ( 0..($strLength -1)) {
    $distance += abs( ord(  $ary->[$_]) -  ord( substr( $targetString, $_, 1)));
  }
  return $distance;                                       (2)
}
sub printPopulation {
  my $pop = shift;
  for (@$pop) {
    print $_->render_gene(), " -> $_->[1] \n";
  }
}                                                         (3)
sub crossover {
  my ($chr1, $chr2) = @_;
  my $length =  scalar( @{$chr1->[0]});
  my $crossoverPoint = int (rand( $length));
  my $range = int( rand( $length - $crossoverPoint ));
  my @tmpAry = @{$chr1->[0]};
  @{$chr1->[0]}[ $crossoverPoint..($crossoverPoint+ $range)] = 
      @{$chr2->[0]}[$crossoverPoint..($crossoverPoint+ $range)];
  @{$chr2->[0]}[ $crossoverPoint..($crossoverPoint+ $range)] =
    @tmpAry[ $crossoverPoint..($crossoverPoint+ $range)]; (3)
}
my @population;
for ( 1..$popSize ) {                                     (4)
  my $chromosome = MyGene->new();
  $chromosome->mutate_insert( $strLength );
  $chromosome->[1] = fitness( $chromosome->[0] );         (4)
  push @population, $chromosome;
}
printPopulation( \@population);
@population = sort { $a->[1] <=> $b->[1] } @population;
for ( 1..$generations ) {
  my @newPop;
  my @rates;
  for ( @population ) {
    push @rates, 1/$_->[1];
  }
  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()];
    my $clone1 = $chr1->clone();
    my $clone2 = $chr2->clone();                          (5)
    $clone1->mutate_minor(1);
    $clone2->mutate_minor(1);
    crossover( $clone1, $clone2 );
    $clone1->[1] = fitness( $clone1->[0] );
    $clone2->[1] = fitness( $clone2->[0] );
    push @newPop, $clone1, $clone2;
  }
  @population = sort { $a->[1] <=> $b->[1] } @newPop;
  print "Best so far: ", $population[0]->render_gene(), "\n";
  printPopulation( \@population );
  last if $population[0]->[1] == 0;
}
(1)
After a somewhat peculiar declaration of the class (needs to be done this way because it is where it is installed by default, maybe it is a bug), we have to subclass the basic AI::Gene class, first to create a rendering of the chromosome so that it looks the same as our previous examples, and then to change the basic definition of mutation, which originally used "character classes"; something we don't need here. It needs to change no further, since it uses as basic alphabet the English lowercase alphabet, as we did in our original programs.
(2)
The data structure used to represent the chromosome is an array-of-arrays, instead of a hash; the first component of the array contains the chromosome; this fitness function takes that chromosome array, and returns fitness. The second component of the array will be used for the fitness, as will be seen later on.
(3)
Crossover is also modified according to the new data structure; arrays are used instead of strings. The rest of the program is not highlighted, but has also been modified according to the new data structure.
(4)
Initializing the chromosome means now creating a new object of the new class MyGene, and then initializing it via the provided AI::Gene::mutate_insert method, that inserts new characters up to the required number.
(5)
Mutation is performed via the provided AI::Gene::mutate_minor, that changes a single character (given as parameter). The rest of the program is the same as before, except for the specific methods used to print the chromosome.
All in all, some useful code is provided by AI::Gene, but, still, you have to write a substantial part of the program. Besides, in our opinion, functionally, mutation operators are functions applied to chromosomes, not part of the chromosome interface, and, as such, should be considered independent classes. In the way AI::Gene is designed, any new mutation-like operator can be added by sub-classing the base class, but it will not be a part of the class, unless you overload one of the existing functions (like mutate_minor). And, finally, it lacks any classes for doing algorithm-level stuff: selection, reproduction, which have to be done by the class client.

Note

AI::Gene can be a good CPAN starting point for evolutionary computation, but it has some way to go to become a complete evolutionary algorithm solution.

There are several other published tools you can use to perform genetic algorithms with Perl. Two of them,AI::GA and Algorithm::Genetic are simple and straightforward implementations of a genetic algorithm. An article by Todor Zlatanov, Cultured Perl: Genetic algorithms applied with Perl Create your own Darwinian breeding grounds, describes a system for doing Genetic Programming with Perl, and includes sample code; this article gets the most mentions in the Perl community. A library, MyBeasties, stands out among the rest. It is a very complex and general implementation of an evolutionary algorithm for any kind of genotype, which, besides, has its own language for describing them and its transformations and evaluations. It features many classes for mutation and recombination, but it lacks classes for higher-level operations, and for implementing different kind of algorithms. Its learning curve is somewhat steep, anyhow.