/ 
Algorithm-Evolve-0.02
River stage zero No dependents
/ Algorithm::Evolve

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;

    ## Output some stats every 10 generations   
    print $pop->avg_fitness, $/ unless $pop->generations % 10;
    
    ## Stop after 2000 generations
    $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, cleanup, etc..

DESCRIPTION

This module is intended to be a useful tool for quick and easy implementation of evolutionary algorithms. It aims to be flexible, yet simple. For this reason, it is not a comprehensive implementation of all possible evolutionary algorithm configurations. The flexibility of Perl allows the evolution of any type of object conceivable: a simple string or array, a deeper structure like a hash of arrays, or even a complex object like graph object from another CPAN module, etc.

It's also worth mentioning that evolutionary algorithms are generally very CPU-intensive. There are a great deal of calls to rand() and a lot of associated floating-point math. If you want a lightning-fast framework, then searching CPAN at all is probably a bad place to start. However, this doesn't mean that I've ignored efficiency. The fitness function is often the biggest bottleneck.

Framework Overview

The configurable parts of an evolutionary algorithm can be split up into two categories:

Dependent on the internal representation of genes to evolve:

These include fitness function, crossover and mutation operators. For example, evolving string genes requires a different mutation operator than evolving array genes.

Independent of representation:

These include selection and replacement methods, population size, number of mating events, etc.

In Algorithm::Evolve, the first group of options is implemented by the user for maximum flexibility. These functions are abstracted to class of evolvable objects (a critter class in this document). The module itself handles the representation-independent parts of the algorithm using simple configuration switches and methods.

USAGE

Designing a class of critter objects (interface specification)

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, which should always be a nonnegative number. This method need not be memo-ized, as it is only called once per critter by Algorithm::Evolve.

This method may be omitted only if using gladitorial selection/replacement (see below).

Class->compare( $obj1, $obj2 )

This method is used for "co-evolution" with the gladitorial selection method. It should return a number less than zero if $obj1 is "better," 0 if the two are equal, or a number greater than zero if $obj2 is "better."

You may also want to use the DESTROY method as a hook for detecting 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: Create tournaments groups of the desired size (see below). The two highest-fitness group members get to breed, and the two lowest-fitness members get replaced (This is also called single-tournament selection). Must be specified for both selection and replacement.

  • gladitorial: See below under "co-evolution". Must be used for both selection and replacement.

  • random: Choose critters completely at random.

  • roulette: Choose critters with weighted probability based on their fitness. For selection, each critter's weight is its fitness. For replacement, each critter's weight is 1/(f+1).

  • rank: Choose critters with weighted probability based on their rank. For selection, the most-fit critter's weight is $pop->size, while the least-fit critter's weight is 1. For replacement, the weights are in reverse order.

  • absolute: Choose the N most-fit critters for selection, or the N least-fit for replacement.

You may mix and match different kinds of selection and replacement methods. The only exceptions are tournament and gladitorial, which must be used as both selection and replacement method.

tournament_size, only required if you choose tournament selection/replacement. Should be at least 4 unless you know what you're doing.

max_gladitorial_attempts: Because comparisons in gladitorial selection may result in a tie, this is the number of ties permitted before giving up and picking critters at random instead during that breeding event. The first time this occurs, the module will carp a message.

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.

In tournament and gladitorial selection, children_per_gen must be equal to parents_per_gen. The number of tournaments each generation is 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.

$pop->selection( [ $new_method ] )
$pop->replacement( [ $new_method ] )

Fetch or change the selection/replacement method while the algorithm is running.

$pop->parents_children_per_gen($parents, $children)

Changes the parents_per_gen and children_per_gen attributes of the population while the algorithm is running. Both are changed at once because the latter must always be a multiple of the former.

Co-Evolution

When there is no absolute measure of fitness for a problem, and a critter's fitness depends on the other memebers of the population, this is called co-evolution. A good example of such a problem is rock-paper-scissors. If we were to evolve strategies for this game, any strategy's success would be dependent on what the rest of the population is doing.

To perform such an evolutionary algorithm, implement the compare method in your critter class and choose gladitorial selection and replacement. Gladitorial selection/replacement chooses random pairs of critters and compares them. If the result is not a tie, the winner receives reproduction rights, and the loser is chosen for replacement. This happens until the desired number of parents have been selected, or until a timeout occurs.

SEE ALSO

Algorithm::Evolve::Util, the examples/ directory.

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.