view release on metacpan or  search on metacpan

lib/Algorithm/Evolve.pm  view on Meta::CPAN

    
    my $p = Algorithm::Evolve->new(
        critter_class    => MyCritters,
        selection        => rank,
        size             => 400,
        callback         => \&callback,
    );
    
    $p->start;
    
    ## Print out final population statistics, cleanup, etc..

=cut

=head1 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 something as complex as 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 C<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.

=head2 Framework Overview

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

=over

=item 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.

=item Independent of representation:

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

=back

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 B<critter class> in this document). The module itself handles the
representation-independent parts of the algorithm using simple configuration
switches and methods.

=head1 USAGE

If you're of the ilk that prefers to learn things hands-on, you should
probably stop here and look at the contents of the F<examples/> directory
first. 

=head2 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:

=over

=item C<Class-E<gt>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.

=item C<Class-E<gt>crossover( $critter1, $critter2 )>

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

=item C<$critter-E<gt>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.

=item C<$critter-E<gt>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).

=item C<Class-E<gt>compare( $critter1, $critter2 )>

This method is used for L</Co_Evolution|co-evolution> with the gladitorial
selection method. It should return a number less than zero if $critter1 is
"better," 0 if the two are equal, or a number greater than zero if $critter2
is "better." 

=back

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

See the F<examples/> directory for example critter classes. Also, take a look
at L<Algorithm::Evolve::Util> which provides some useful utilities for 
implementing a critter class.




=head2 Algorithm::Evolve population interface

=over

=item C<$p = Algorithm::Evolve-E<gt>new( option =E<gt> value, ... )>

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

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

B<selection> and B<replacement>, the type of selection and replacement methods 
to use. Available methods for both currently include: 

=over

=item *

B<tournament>: Create tournament 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.

=item *

B<gladitorial>: See below under L</Co_Evolution|co-evolution>. Must be used
for both selection and replacement.

=item *

B<random>: Choose critters completely at random.

=item *

B<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/(fitness + 1).

=item *

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

=item *

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

=back

You may mix and match different kinds of selection and replacement methods. The

lib/Algorithm/Evolve.pm  view on Meta::CPAN

must always be a multiple of the former.

=back


=head2 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
B<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 C<compare> method
in your critter class and choose gladitorial selection and replacement. 
Gladitorial selection/replacement chooses random pairs of critters and
C<compare>s 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.

=head2 Adding Selection/Replacement Methods

To add your own selection and replacement methods, simply declare them in
the C<Algorithm::Evolve::selection> or C<Algorithm::Evolve::replacement> 
namespaces, respectively. The first argument will be the population object,
and the second will be the number of critters to choose for
selection/replacement. You should return a list of the I<indices> you chose.

    use Algorithm::Evolve;
    
    sub Algorithm::Evolve::selection::reverse_absolute {
        my ($p, $num) = @_;
        
        ## Select the indices of the $num lowest-fitness critters.
        ## Remember that they are sorted by increasing fitness.
        return (0 .. $num-1);
    }
    sub Algorithm::Evolve::replacement::reverse_absolute {
        my ($p, $num) = @_;
        
        ## Select indices of the $num highest-fitness critters.
        return ($p->size - $num .. $p->size - 1);
    }
    
    ## These are like absolute selection/replacement, but reversed, so that
    ## the evolutionary algorithm *minimizes* the fitness function.
    
    my $p = Algorithm::Evolve->new(
        selection => reverse_absolute,
        replacement => reverse_absolute,
        ...
    );

See the source of this module to see how the various selection/replacement
methods are implemented.
The mechanism for adding additional selection/replacement methods may change
in future versions.

=head1 SEE ALSO

L<Algorithm::Evolve::Util|Algorithm::Evolve::Util>, the F<examples/>
directory.

=head1 AUTHOR

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

=head1 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.