Growing up: a whole evolutionary algorithm with Algorithm::Evolutionary
How to program and serialize all parts of an evolutionary algorithmIt is about time we go into more complex stuff, and, since many sub-algorithms are already programmed into Algorithm::Evolutionary, we will use it. The not so-simple genetic algorithm is composed of a main loop that does, in sequence,
selection of the group of individuals that will be the parents of the next generation
application of genetic operators to those elements
insertion of those parents in the population
elimination of a part of the population, and
checking for termination conditions
#!perl
use strict;
use warnings;
use Algorithm::Evolutionary::Experiment;
use Algorithm::Evolutionary::Op::Creator;
use Algorithm::Evolutionary::Op::Bitflip;
use Algorithm::Evolutionary::Op::Crossover;
use Algorithm::Evolutionary::Op::RouletteWheel;
use Algorithm::Evolutionary::Op::GeneralGeneration;
use Algorithm::Evolutionary::Op::DeltaTerm;
use Algorithm::Evolutionary::Op::FullAlgorithm;
my $numberOfBits = shift || 32;
my $popSize = 100;
my $fitness = sub {
my $indi = shift;
my $total = grep( $_ == 1, split(//,$indi->Chrom() ));
return $total;
}; (1)
my $creator = (2)
new Algorithm::Evolutionary::Op::Creator( $popSize, 'BitString',
{ length => $numberOfBits });
my $selector = new Algorithm::Evolutionary::Op::RouletteWheel $popSize;
my $mutation = new Algorithm::Evolutionary::Op::Bitflip;
my $crossover = new Algorithm::Evolutionary::Op::Crossover;
my $replacementRate = 0.4; #Replacement rate
my $generation =
new Algorithm::Evolutionary::Op::GeneralGeneration( $fitness, $selector, (2)
[$mutation, $crossover], $replacementRate ); (3)
my $terminator = new Algorithm::Evolutionary::Op::DeltaTerm $numberOfBits, 0;
my $algorithm = new Algorithm::Evolutionary::Op::FullAlgorithm $generation, $terminator;(3)
my $experiment = new Algorithm::Evolutionary::Experiment $creator, $algorithm;(4)
print<<EOC;
<?xml version="1.0" standalone="no"?>
<experiment>
EOC
print $experiment->asXML(); (4)
$experiment->go();
print $experiment->asXML(), "</experiment>";
|
- (1)
- Declaration of a Creator, which is factory class for algorithm individuals, Bitstrings in this case. This class takes as arguments the number of elements it will produce, the name of the class, and a hash that contains a list of named arguments, that will be passed to the class constructor. In this case, just the length of the chromosome is needed
- (2)
- A Generation includes a selector, which decides what elements of the population will be used for reproduction. In this case, RouletteWheel is chosen, the same reproductive method we have seen before: the elements of the population are selected with a probability proportional to its fitness. Another option would have been TournamentSelect, which takes a set of several individuals, and select only the best of them. It is a greedier way of selection, and its greediness depends on the number of elements in the tournament: the higher the number, the greedier. Crossover and mutation operators are declared in the next line; in Algorithm::Evolutionary, operators are independent classes, so that you are free to declare and use as many as you want. The operators are passed in an array ref to the Generation, and are selected according to rate: by default, each operator gets a rate of 1, and thus have the same probability. Rate can be changed during runtime, since it is an instance variable. Finally, the $replacementRate rules how many elements of the population will be substituted each generation. Finally, the object is declared, passing all the previous stuff as arguments.
- (3)
- Finally, the full algorithm itself, in all its majesty, is declared. It needs the previously-declared $generation object, plus a termination condition. And then, the two operators that are going to be applied sequentially to the population, the creator and then the algorithm, are used to create an Experiment object. This object takes as an argument operators that will be applied sequentially to the population; any operator whose apply method takes an array as an argument could be passed here. It could be possible, for instance, to use a creator, then an evolutionary algorithm, then a bridge, and then another kind of algorithm, population-based incremental learning, for instance, or simulated annealing, to improve the final result. This, of course, could be done in a single operator.
- (4)
- The algorithm is run, and its initial and final state is included in a well-formed XML document that is sent to standard output.
The good thing about having this XML output is that you can process it very easily, for instance, to pretty-print final population, using this XSLT stylesheet to obtain this web page. The XML document can be used for post-algorithmic analysis, for interchange with other evolutionary algorithms, possibly written in other languages, or even for external data representation for parallel and distributed algorithms. For instance, the output of the algorithm can be converted to a combined HTML/SVG (Scalable Vector Graphics) document, which can be used for presentation straight away. It could also be imagined a "literate evolutionary computation" application that would mix the output of an evolutionary algorithm, with the description of the classes obtained via pod2xml, to create an XSLT stylesheet that would process output and create a document with output along explanation. This is left as an exercise to the reader.
 | XML is cool. 'Nuff said. |