|
AI::Genetic - A pure Perl genetic algorithm implementation. |
AI::Genetic - A pure Perl genetic algorithm implementation.
use AI::Genetic;
my $ga = new AI::Genetic(
-fitness => \&fitnessFunc,
-type => 'bitvector',
-population => 500,
-crossover => 0.9,
-mutation => 0.01,
-terminate => \&terminateFunc,
);
$ga->init(10);
$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;
}
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.
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 generations. What happens during each generation can vary greatly depending on the strategy being used (See STRATEGIES for more info). Typically, a variation of the following happens at each generation:
Here are the public methods.
Defaults to bitvector.
$ga->init(10);
this initializes a population where each individual has 10 genes.
$ga->init([
[qw/red blue green/],
[qw/big medium small/],
[qw/very_fat fat fit thin very_thin/],
]);
this initializes a population where each individual has 3 genes, and each gene can assume one of the given values.
$ga->init([
[1, 5],
[0, 20],
[4, 9],
]);
this initializes a population where each individual has 3 genes, and each gene can assume an integer within the corresponding range.
$ga->inject(5,
[qw/red big thin/],
[qw/blue small fat/],
);
this adds 5 new individuals, 2 with the specified genetic coding, and 3 randomly generated.
Each generation consists of the following steps:
genes() and score() methods to get the genes and the
scores of the individuals. Please check the AI::Genetic::Individual manpage for details.
Very quickly you will realize that properly defining the fitness function is the most important aspect of a GA. Most of the time that a genetic algorithm takes to run is spent in running the fitness function for each separate individual to get its fitness. AI::Genetic tries to minimize this time by caching the fitness result for each individual. But, you should spend a lot of time optimizing your fitness function to achieve decent run times.
The fitness function should expect only one argument, an anonymous list of genes, corresponding to the individual being analyzed. It is expected to return a number which defines the fitness score of the said individual. The higher the score, the more fit the individual, the more the chance it has to be chosen for crossover.
AI::Genetic comes with 9 predefined strategies. These are:
More detail on these strategies and how to call them in your own custom strategies can be found in the AI::Genetic::OpSelection manpage, the AI::Genetic::OpCrossover manpage and the AI::Genetic::OpMutation manpage.
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 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;
}
}
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.
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.
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.
Written by Ala Qumsieh 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.
(c) 2003-2005 Ala Qumsieh. All rights reserved. This module is distributed under the same terms as Perl itself.
|
AI::Genetic - A pure Perl genetic algorithm implementation. |