Algorithm-Evolve

 view release on metacpan or  search on metacpan

README  view on Meta::CPAN

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

INSTALLATION

To install this module type the following:

   perl Makefile.PL
   make
   make test

examples/breeding_perls.pl  view on Meta::CPAN

##############################################################################

use Algorithm::Evolve;
Algorithm::Evolve->new(
    critter_class   => 'main',
    selection       => 'roulette',
    replacement     => 'rank',
    parents_per_gen => 2,
    size            => 200,
    callback        => \&callback,
)->start;

sub callback {
    my $p = shift;

    if ($p->best_fit->fitness == $TARGET) {
        $p->suspend;
        printf "Solution found after %d generations:\n%s\n",
                    $p->generations, $p->best_fit->as_perl_code;
    }
    

examples/rock_paper_scissors.pl  view on Meta::CPAN

my $p = Algorithm::Evolve->new(
    critter_class    => 'main',
    selection        => 'gladitorial',
    parents_per_gen  => 10,
    size             => 80,
    callback         => \&callback,
    random_seed      => shift
);

$p->start;

__END__

=head1 NAME

rock_paper_scissors.pl - Rock Paper Scissors co-evolution example for
Algorithm::Evolve

=head1 DESCRIPTION

examples/rock_paper_scissors.pl  view on Meta::CPAN

random initialization, and mutation. Unlike F<examples/string_evolver.pl>,
this is a co-evolving system where fitness is not absolute, but based
on a critter's ability to play Rock, Paper, Scissors against the other
members of the population.

In co-evolution, population members are chosen for selection and replacement
using the C<compare> method. In our critter class, we override the default
C<compare> method. Our new C<compare> method
uses each string gene as a sequence of Rock, Paper, and Scissors moves. The
gene who wins the most turns is the winner. Notice how we pick a random spot
in the string genes to start at, and wrap back to the beginning, taking each
move exactly once.

At each generation, the total number of Rock, Paper, and Scissors
encodings in the population are tallied and printed. If you graph the
output in something like gnuplot, you will probably notice that the
population cycles between Rock, Paper, and Scissors being the most
prevalent move. This is the command in gnuplot I used to view the output
from this script:

   gnuplot> plot 'output' using :1 title 'Rock' with lines, \

examples/string_evolver.pl  view on Meta::CPAN

my $pop = Algorithm::Evolve->new(
    critter_class    => 'StringEvolver',
    selection        => 'rank',
    parents_per_gen  => 8,
    size             => 200,
    callback         => \&callback,
    random_seed      => shift
);

$pop->start;

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

    croak "parents_per_gen and children_per_gen must be no larger than size"
        if $p->children_per_gen > $p->size
        or $p->parents_per_gen  > $p->size;
        
    $p->{children_per_parent} = $p->children_per_gen / $p->parents_per_gen;

}

############################

sub start {
    my $p = shift;
    $p->_initialize;
        
    until ($p->is_suspended) {
        no strict 'refs';
        
        my @parent_indices
            = ("Algorithm::Evolve::selection::" . $p->selection)
                ->($p, $p->parents_per_gen);

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

###################

sub suspend {
    my $p = shift;
    $p->{is_suspended} = 1;
}

sub resume {
    my $p = shift;
    $p->{is_suspended} = 0;
    $p->start;
}

sub best_fit {
    my $p = shift;
    carp "It's hard to pick the most fit when fitness is relative!"
        unless ($p->use_fitness);
    $p->critters->[-1];
}

sub avg_fitness {

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

        $p->suspend if $p->generations >= 2000;
    }
    
    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

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

B<size>, the number of critters to have in the population.

B<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).

B<random_seed>, an optional number that will be fed to C<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.


=item C<$p-E<gt>size()>

Returns the size of the population, as given above. As of now, you cannot
change the population's size during the runtime of the evolutionary algorithm.

=item C<$p-E<gt>run()>

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

=item C<str_mutate( $string1 [, $num [, \@alphabet ]] )>

=item C<arr_mutate( \@array1 [, $num [, \@alphabet ]] )>

Returns a random mutation of the gene according to the given alphabet
(defaulting to {0,1}). If C<$num> is less than 1, it performs I<probabilistic
mutation>, with each position having a C<$num> probability of being mutated. If
C<$num> is greater than or equal to 1, it performs I<N-point mutation>: exactly
C<$num> positions are chosen at random and mutated. C<$num> defaults to 1. A
convenient rule of thumb is start with a mutation rate of 1/gene_length.

A mutation will always change the character in question: an 'a' will never be
chosen to replace an existing 'a' in a mutation. The following identity holds
for N-point mutations:

  str_agreement( str_mutate($some_string, $n, \@alph), $some_string )
    == length($some_string) - $n;

The alphabet for a string gene should consist of only single characters unless
you know what you're doing. Conceivably, you can implement an 'add' and 'remove'