AI-Genetic
view release on metacpan or search on metacpan
}
# sub sortPopulation():
# This method sorts the population of individuals.
sub sortPopulation {
my $self = shift;
return if $self->{SORTED};
$self->{PEOPLE} = $self->sortIndividuals($self->{PEOPLE});
$self->{SORTED} = 1;
}
# sub getFittest():
# This method returns the fittest individuals.
sub getFittest {
my ($self, $N) = @_;
$N ||= 1;
$N = 1 if $N < 1;
$N = @{$self->{PEOPLE}} if $N > @{$self->{PEOPLE}};
$self->sortPopulation;
my @r = @{$self->{PEOPLE}}[0 .. $N-1];
return $r[0] if $N == 1 && not wantarray;
return @r;
}
# sub init():
# This method initializes the population to completely
# random individuals. It deletes all current individuals!!!
# It also examines the type of individuals we want, and
# require()s the proper class. Throws an error if it can't.
# Must pass to it an anon list that will be passed to the
# newRandom method of the individual.
# In case of bitvector, $newArgs is length of bitvector.
# In case of rangevector, $newArgs is anon list of anon lists.
# each sub-anon list has two elements, min number and max number.
# In case of listvector, $newArgs is anon list of anon lists.
# Each sub-anon list contains possible values of gene.
sub init {
my ($self, $newArgs) = @_;
$self->{INIT} = 0;
my $ind;
if (exists $_genome2class{$self->{TYPE}}) {
$ind = $_genome2class{$self->{TYPE}};
} else {
$ind = $self->{TYPE};
}
eval "use $ind"; # does this work if package is in same file?
if ($@) {
carp "ERROR: Init failed. Can't require '$ind': $@,";
return undef;
}
$self->{INDIVIDUAL} = $ind;
$self->{PEOPLE} = [];
$self->{SORTED} = 0;
$self->{GENERATION} = 0;
$self->{INITARGS} = $newArgs;
push @{$self->{PEOPLE}} =>
$ind->newRandom($newArgs) for 1 .. $self->{POPSIZE};
$_->fitness($self->{FITFUNC}) for @{$self->{PEOPLE}};
$self->{INIT} = 1;
}
# sub people():
# returns the current list of individuals in the population.
# note: this returns the actual array ref, so any changes
# made to it (ex, shift/pop/etc) will be reflected in the
# population.
sub people {
my $self = shift;
if (@_) {
$self->{PEOPLE} = shift;
$self->{SORTED} = 0;
}
$self->{PEOPLE};
}
# useful little methods to set/query parameters.
sub size { $_[0]{POPSIZE} = $_[1] if defined $_[1]; $_[0]{POPSIZE} }
sub crossProb { $_[0]{CROSSRATE} = $_[1] if defined $_[1]; $_[0]{CROSSRATE} }
sub mutProb { $_[0]{MUTPROB} = $_[1] if defined $_[1]; $_[0]{MUTPROB} }
sub indType { $_[0]{INDIVIDUAL} }
sub generation { $_[0]{GENERATION} }
# sub inject():
# This method is used to add individuals to the current population.
# The point of it is that sometimes the population gets stagnant,
# so it could be useful add "fresh blood".
# Takes a variable number of arguments. The first argument is the
# total number, N, of new individuals to add. The remaining arguments
# are genomes to inject. There must be at most N genomes to inject.
# If the number, n, of genomes to inject is less than N, N - n random
# genomes are added. Perhaps an example will help?
# returns 1 on success and undef on error.
sub inject {
my ($self, $count, @genomes) = @_;
unless ($self->{INIT}) {
carp "can't inject() before init()";
return undef;
$ga->evolve('rouletteTwoPoint', 100);
print "Best score = ", $ga->getFittest->score, ".\n";
sub fitnessFunc {
my $genes = shift;
my $fitness;
# assign a number to $fitness based on the @$genes
# ...
return $fitness;
}
sub terminateFunc {
my $ga = shift;
# terminate if reached some threshold.
return 1 if $ga->getFittest->score > $THRESHOLD;
return 0;
}
=head1 DESCRIPTION
This module implements a Genetic Algorithm (GA) in pure Perl.
Other Perl modules that achieve the same thing (perhaps better,
perhaps worse) do exist. Please check CPAN. I mainly wrote this
module to satisfy my own needs, and to learn something about GAs
along the way.
B<PLEASE NOTE:> As of v0.02, AI::Genetic has been re-written from
scratch to be more modular and expandable. To achieve this, I had
to modify the API, so it is not backward-compatible with v0.01.
As a result, I do not plan on supporting v0.01.
I will not go into the details of GAs here, but here are the
bare basics. Plenty of information can be found on the web.
In a GA, a population of individuals compete for survival. Each
individual is designated by a set of genes that define its
behaviour. Individuals that perform better (as defined by the
fitness function) have a higher chance of mating with other
individuals. When two individuals mate, they swap some of
their genes, resulting in an individual that has properties
from both of its "parents". Every now and then, a mutation
occurs where some gene randomly changes value, resulting in
a different individual. If all is well defined, after a few
generations, the population should converge on a "good-enough"
solution to the problem being tackled.
A GA implementation runs for a discrete number of time steps
called I<generations>. What happens during each generation can
vary greatly depending on the strategy being used (See
L</"STRATEGIES"> for more info).
Typically, a variation of the following happens at
each generation:
=over 4
=item B<1. Selection>
Here the performance of all the individuals is evaluated
based on the fitness function, and each is given a specific
fitness value. The higher the value, the bigger the chance
of an individual passing its genes on in future generations
through mating (crossover).
=item B<2. Crossover>
Here, individuals selected are randomly paired up for
crossover (aka I<sexual reproduction>). This is further
controlled by the crossover rate specified and may result in
a new offspring individual that contains genes common to
both parents. New individuals are injected into the current
population.
=item B<3. Mutation>
In this step, each individual is given the chance to mutate
based on the mutation probability specified. If an individual
is to mutate, each of its genes is given the chance to randomly
switch its value to some other state.
=back
=head1 CLASS METHODS
Here are the public methods.
=over 4
=item I<$ga>-E<gt>B<new>(I<options>)
This is the constructor. It accepts options in the form of
hash-value pairs. These are:
=over 8
=item B<-population>
This defines the size of the population, i.e. how many individuals
to simultaneously exist at each generation. Defaults to 100.
=item B<-crossover>
This defines the crossover rate. Defaults to 0.95.
=item B<-mutation>
This defines the mutation rate. Defaults to 0.05.
=item I<-fitness>
This defines a fitness function. It expects a reference to a subroutine.
More details are given in L</"FITNESS FUNCTION">.
=item I<-type>
This defines the type of the genome. Currently, AI::Genetic
supports only three types:
=over
=item tournamentSinglePoint
This strategy implements tournament selection and single-point crossover.
=item tournamentTwoPoint
This strategy implements tournament selection and two-point crossover.
=item tournamentUniform
This strategy implements tournament selection and uniform crossover.
=item randomSinglePoint
This strategy implements random selection and single-point crossover.
=item randomTwoPoint
This strategy implements random selection and two-point crossover.
=item randomUniform
This strategy implements random selection and uniform crossover.
=back
More detail on these strategies and how to call them in your own
custom strategies can be found in L<AI::Genetic::OpSelection>,
L<AI::Genetic::OpCrossover> and L<AI::Genetic::OpMutation>.
You can use the functions defined in the above modules in your
own custom-made strategy. Consult their manpages for more info.
A custom-made strategy can be defined using the I<strategy()>
method and is called at the beginning of each generation. The only
argument to it is the AI::Genetic object itself. Note that the
population at this point is sorted accoring to each individual's
fitness score. It is expected that the strategy sub will modify
the population stored in the AI::Genetic object. Here's the
pseudo-code of events:
for (1 .. num_generations) {
sort population;
call strategy_sub;
if (termination_sub exists) {
call termination_sub;
last if returned true value;
}
}
=head1 A NOTE ON SPEED/EFFICIENCY
Genetic algorithms are inherently slow.
Perl can be pretty fast, but will never reach the speed of optimized
C code (at least my Perl coding will not). I wrote AI::Genetic mainly
for my own learning experience, but still tried to optimize it as
much as I can while trying to keep it as flexible as possible.
To do that, I resorted to some well-known tricks like passing a
reference of a long list instead of the list itself (for example,
when calling the fitness function, a reference of the gene list
is passed), and caching fitness scores (if you try to evaluate
the fitness of the same individual more than once, then the fitness
function will not be called, and the cached result is returned).
To help speed up your run times, you should pay special attention
to the design of your fitness function since this will be called once
for each unique individual in each generation. If you can shave off a
few clock cycles here and there, then it will be greatly magnified in
the total run time.
=head1 BUGS
I have tested this module quite a bit, and even used it to solve a
work-related problem successfully. But, if you think you found a bug
then please let me know, and I promise to look at it.
Also, if you have any requests, comments or suggestions, then feel
free to email me.
=head1 INSTALLATION
Either the usual:
perl Makefile.PL
make
make install
or just stick it somewhere in @INC where perl can find it. It is in pure Perl.
=head1 AUTHOR & CREDITS
Written by Ala Qumsieh I<aqumsieh@cpan.org>.
Special thanks go to John D. Porter and Oliver Smith for stimulating
discussions and great suggestions. Daniel Martin and Ivan Tubert-Brohman
uncovered various bugs and for this I'm grateful.
=head1 COPYRIGHTS
(c) 2003-2005 Ala Qumsieh. All rights reserved.
This module is distributed under the same terms as Perl itself.
=cut
( run in 1.692 second using v1.01-cache-2.11-cpan-acf6aa7dc9e )