NAME

Algorithm::Evolve - An extensible and generic framework for executing evolutionary algorithms

SYNOPSIS

#!/usr/bin/perl -w
use Algorithm::Evolve;
use MyCritters;  ## class providing appropriate methods

sub callback {
    my $pop = shift;

    ## some stats every 10 generations   
    print $pop->avg_fitness, $/ unless $pop->generations % 10;
    
    $pop->suspend if $pop->generations >= 2000;
}

my $pop = Algorithm::Evolve->new(
    critter_class    => MyCritters,
    selection        => rank,
    replacement      => random,
    parents_per_gen  => 2,
    children_per_gen => 4,
    size             => 400,
    callback         => \&callback,
);

$pop->start;

## print out final population statistics

DESCRIPTION

This module contains a class-based framework for executing evolutionary algorithms. The goal is to allow evolution of any type of object conceivable with relative ease, be it a simple string, an array, a hash of arrays, a directed graph object using a CPAN module, or anything else.

The configurable aspects of an evolutionary algorithm can be split up into two categories: those aspects closely tied to the object representation (fitness function, crossover and mutation operators), and those that do not depend at all on the object representation (selection and replacement methods, population size, number of mating events). The former group of options is implemented by the user and abstracted to class of evolvable objects, while the latter is handled by Algorithm::Evolve using simple configuration switches.

USAGE

Designing a class of critter objects

Algorithm::Evolve maintains a population of critter objects to be evolved. You may evolve any type of objects you want, provided the class supplies the following methods:

Class->new()

This method will be called as a class method with no arguments. It must return a blessed critter object. It is recommended that the returned critter's genes be randomly initialized.

Class->crossover( $obj1, $obj2 )

This method will also be called as a class method, with two critter objects as arguments. It should return a list of two new objects based on the genes of the passed objects.

$critter->mutate()

This method will be called as an instance method, with no arguments. It should randomly modify the genes of the critter. Its return value is ignored.

$critter->fitness()

This method will also be called as an instance method, with no arguments. It should return the critter's fitness measure within the problem space. This should always be a nonnegative number. This method need not be memo-ized, as it is only called once per critter by Algorithm::Evolve.

You may also want to use the DESTROY method as a hook for when critters are removed from the population.

See the examples directory for an example of a unimodal string evolver that uses a very lightweight blessed string-ref implementation. Also, take a look at Algorithm::Evolve::Util which provides some useful utilities for implementing a critter class.

Algorithm::Evolve population interface

$pop = Algorithm::Evolve->new( option => value, ... )

Takes a hash of arguments and returns a population object. The relevant options are:

critter_class, the name of the critter class whose objects are to be evolved. This class should already be use'd or require'd by your code.

selection and replacement, the type of selection and replacement methods to use. Available methods for both currently include: tournament, random, rank, roulette, and absolute. You may mix and match selection and replacement methods, the only exception being tournament which can only be used as both selection and replacement method.

tournament_size, only required if you choose tournament selection/ replacement. Algorithm::Evolve only currently performs single-tournament selection/replacement.

parents_per_gen and children_per_gen control the number of breedings per generation. children_per_gen must be a multiple of parents_per_gen. parents_per_gen must also be an even number. Each pair of parents selected in a generation will produce the same number of children, calling the crossover method in the critter class as many times as necessary. Basically, each selected parent gets a gene copy count of children_per_gen/parents_per_gen. The exception is in tournament selection, where children_per_gen must be equal to parents_per_gen. The number of tournaments each generation is then equal to parents_per_gen/2.

size, the number of critters to have in the population.

callback, an optional (but highly recommended) reference to a function. It should expect one argument, the population object. It is called after each generation. You may find it useful for printing out current statistical information. You must also use it if you intend to stop the algorithm after a certain number of generations (or some other criteria).

random_seed, an optional number that will be fed to srand before the algorithm starts. Use this to reproduce previous results. If this is not given, Algorithm::Evolve will generate a random seed that you can retrieve.

$pop->run

Begins execution of the algorithm, and returns when the population has been suspend'ed.

$pop->suspend

Call this method from within the callback function to stop the algorithm's iterations and return from the run method.

$pop->resume

Start up the algorithm again after being suspend'ed.

$pop->generations, $pop->avg_fitness, $pop->best_fit

These return basic information about the current state of the population. You probably will use these methods from within the callback sub. The best_fit method returns the most-fit critter in the population.

$pop->critters

Returns a reference to an array containing all the critters in the population, sorted by fitness. You can use this to iterate over the entire population, but please don't modify the array.

$pop->random_seed

Returns the random seed that was used for this execution.

SEE ALSO

Algorithm::Evolve::Util

AUTHOR

Algorithm::Evolve is written by Mike Rosulek <mike@mikero.com>. Feel free to contact me with comments, questions, patches, or whatever.

COPYRIGHT

Copyright (c) 2003 Mike Rosulek. All rights reserved. This module is free software; you can redistribute it and/or modify it under the same terms as Perl itself.