Canonical GA with Algorithm::Evolutionary

After having dabbled with other languages for programming evolutionary computation, like C++ (for EO), or JavaScript (for GAJS), and taking a look at the EA Perl landscape, the author decided it was about time to program an evolutionary computation library in Perl. It was called initially OPEAL (for Original Perl Evolutionary Algorithm Library), but after some consultations, and previous to uploading it to CPAN (which, er, has not happened yet), it was renamed Algorithm::Evolutionary. It was intended as a complete and extensible evolutionary algorithm implementation, integrated with XML, and easy to learn, use and extend. It has been out there for about a year, and, right now, is available from SourceForge as a GPL module. Last released version is 0.5, which was released in summer 2002.

Enough hype, and let's see what the boy is able to do. Download it, do the three-phrase spell perl Makefile.PL; make; make install (and, for the wary, make test), and you'll have it installed in your preferred modules directory. You can then run this program (ea-ex1.pl):

use Algorithm::Evolutionary::Experiment;
use Algorithm::Evolutionary::Op::Easy;
my $fitness = sub {
  my $indi = shift;
  my $total = grep( $_ == 1, split(//,$indi->Chrom() ));
  return $total; 
};
my $ez = new Algorithm::Evolutionary::Op::Easy $fitness;
my $popSize = 100;
my $indiType = 'BitString';
my $indiSize = 32;
my $e = new Algorithm::Evolutionary::Experiment $popSize, $indiType, $indiSize, $ez;
print $e->asXML();
my $populationRef;
do { 
  $populationRef = $e->go();
  print "Best so far: ", $populationRef->[0]->asString(), "\n";
} until ($populationRef->[0]->Fitness() == $indiSize);
print "Final\n", $e->asXML();

<ea xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:noNamespaceSchemaLocation='ea-alpha.xsd'
    version='0.3'>
<!-- Serialization of an Experiment object. Generated automatically by
     Experiment $Revision: 1.2 $ -->
    <initial>
<op name='Easy'  ><op name='Bitflip'  rate='1' >
	<param name='howMany' value='1' />
</op>
<op name='Crossover'  rate='1' >
	<param name='numPoints' value='2' />
</op>

	<param name='selrate' value='0.4' /><code type='eval' language='perl'>
<src><![CDATA[{
    my $indi = shift @_;
    my $total = grep(($_ == 1), split(//, $indi->Chrom, 0));
    return $total;
}]]&gt;
 </src>
</code>
</op>
	</initial>
<!-- Population --><pop>
<indi type='BitString'  > <atom>0</atom> <atom>1</atom> <atom>1</atom> <atom>1</atom> <atom>1</atom> <atom>1</atom> <atom>0</atom> <atom>0</atom> <atom>0</atom> <atom>0</atom> <atom>0</atom> <atom>1</atom> <atom>1</atom> <atom>0</atom> <atom>0</atom> <atom>1</atom> <atom>0</atom> <atom>1</atom> <atom>0</atom> <atom>0</atom> <atom>1</atom> <atom>0</atom> <atom>1</atom> <atom>1</atom> <atom>0</atom> <atom>1</atom> <atom>1</atom> <atom>1</atom> <atom>0</atom> <atom>1</atom> <atom>1</atom> <atom>0</atom> 
	
</indi>
<!-- more indis like this one -->
	</pop>
</ea>

After the initial section, comes the pop section, that includes the components of the initially generated population. Each individual is enclosed by the tag indi, with a type attribute that indicates the class the individual belongs to, and them, one atom for every "atomic" component of the data structure.

That XML document can be retrieved back into a program by loading the file into a variable $xml and using this:my $experiment= Algorithm::Evolutionary::Experiment->fromXML( $xml ); .

However, as we said, this is not the canonical genetic algorithm. The program that implements it would be use the CanonicalGA class, like the example in ea-ex2.pl, which is exactly the same, except that, instead of declaring an Easy object, we declare a CanonicalGA. This object, besides implementing a canonical GA without elitism, uses QuadXOver, the crossover used before that takes two arguments by reference and returns offspring in the same arguments. The Crossover object takes arguments by value, not modifying them, and returns a single offspring.

A different problem might require a different fitness function, and probably different type of individuals. The default Algorithm::Evolutionary distribution includes four classes: Vector, for anything vectorial, from strings represented as vectors, through vector of floating point numbers, up to vectors of frobnicated foobars; String, with the BinaryString subclass, and Tree, for doing Genetic Programming or anything else that requires a tree data structure for representation. Using any of these data structures for solving a problem is left as an exercise to the student.

Algorithm::Evolutionary problems can be specified using Perl, but you can use an "universal reader" (ea-ex3.pl) to read the description of the algorithm in XML.

#!perl
use strict;
use warnings;
use Algorithm::Evolutionary::Experiment;
my $xmlDoc = join("",<>);
my $e = Algorithm::Evolutionary::Experiment->fromXML($xmlDoc);
my $populationRef = $e->go();
print "Final\n", $e->asXML();