Inspired by recent genetic algorithms floating around, I decided to try my hand at implementing one in perl. I’d thought for a long time that it would be quite difficult, but really it’s quite easy. My biggest hangup was dealing with data structures, but once I did that, it turns out that all you really need is a few functions:
- A fitness function, that determines which individuals are most fit to reproduce
- A mutate function, that will add random chance into each generation
- A breed function that allows the best individuals to reproduce.
I ended up implementing a very simple algorithm, but it’s fairly fast and very generic โ it can be easily adapted to just about any task. Sadly, I have no fascinating application just yet, but if I stumble across one, I’ll be sure to post about it.
After the jump, I’ll put up some of the code I used and a link to the script, all for your viewing pleasure.
The heart of the algorithm is the mutate and breed functions:
sub mutate{ # Mutates each allele of an individual by a random, weighted amount,
# controlled by certain parameters. It re-initializes if the allele
# is zero, and takes abs()
my $ind = shift;
for (@$ind) {
$_ = eval($init_string) unless ($_);
$_ += (rand(2) - 1)*($mut_weight*($_)+$mut_offset);
$_ = -$_ unless ($_>0);
}
return 0;
}
sub breed{ # Breeds each individual with the top 20 percent of the population randomly
# by averaging each allele of the individual with the corresponding allele
# of a random individual in the top quintile. Note that this means that
# each individual breeds with, at most (and ideally), as many individuals
# as it has alleles, which breaks down the parent / child model slightly.
my $indvs = shift;
my @list;
($minimize) || (@list = sort {fitness($b) fitness($a)} @$indvs); # Sort asc. vs. desc.
($minimize) && (@list = sort {fitness($a) fitness($b)} @$indvs);
@list = @list[1..(int(scalar(@list)/5)+1)];
for (@$indvs) { # Iterate through individuals
my $ind_ref = $_;
my $i = 0;
for (@$ind_ref) { # Iterate through alleles
$_ = ((@list[int(rand(length(@list)-1))])->[$i] + $_)/2; # Average given allele with
# a random, fit,
# corresponding allele
$_ = (rand(1)
Between the comments and the code, it should be pretty clear what's going on in here, although some of the data structures are kinda hard to get from this section. As I explain in the code:
A randomized population is created. An array holds references to the specified number of "individuals". Each individual is an array of alleles (scalar values) that are chosen by evaluating a specified string. These are currently positive real numbers.
These references (or references to the population array) are passed as arguments to the functions each iteration.
If you're interested, be sure to check out the code and please give me some feedback!
UPDATE: Ivan in the comments made the recommendation of using an anonymous function to intialize individuals. I made that change he recommended and updated the code.
Or… you can sudo cpan Algorithm::Evolutionary and download a nifty and venerable cpan module.
The code looks nice, anyways, and just goes out to prove that Perl is as good a language as any other for programming evolutionary algorithms. Better than many others, in fact.
Don’t use string eval – it slows you down significantly, and it’s rather inelegant.
what you are looking for is anonymous functions –
my $init = sub { rand(10) };
and then replace all eval($init_string) with $init->();
Thanks for the replies…
@JJ: I hadn’t seen that module. It looks interesting. However, the point here was to write one from scratch, which seems to have worked out fairly well. I wasn’t sure how Perl would do, and it seems to have come through admirably.
@Ivan: Good call on anonymous functions. I’ve made that change and I’ll post updated code in a little bit.
as an alternative to Algo::Evolutionary, http://search.cpan.org/search?query=genetic&mode=all shows also AI::Genetic and AI::Genetic::Pro. I know you did this for fun, but if I was to use Perl genetic algos for serious work, I’d probably go for the ::Pro module.
Another comment on your code – sort {fitness($b) fitness($a)} – will evaluate your fitness function ~ N log(N) times, which is usually not what you want. For education, you should probably read about Orcish maneuver and Schwartzian Transform… as for real work you should probably use Sort::Key.
I would definitely use a module as well, over home-grown code, both for performance and reliability. However, it’s a fun learning experience. And you’re right, there is some inefficiency in doing the straight sort(), so it’s good to learn a bit about better ways of doing the same thing.
WRT to performance, you can get strong gains by compiling your own perl, eliminating threads and some other features.
I hadn’t seen AI::Genetic::Pro; it looks nice, and it’s been XS-ed for performance. However, it doesn’t look too flexible. I did Algorithm::Evolutionary for my own research, and thus what I valued the most was the possibility to easily add new stuff.
I’ve been playing with AI::Genetic and it’s quite good… I especially value the ability to define your own strategies, as well as the flexibility in defining the genome.
As to performance, I wouldn’t be using Perl if I wanted it to be fast, only if I wanted it to be pretty, which this is. Perl makes for a nice interface to a genetic algorithm, and makes it very easy to modify to any problem. Even my homegrown code has that advantage, and it’s even more present in the modules that are available.
Actually, Perl is not so slow for the bread and butter of GA, string handling. And, of course, you (and mostly everybody else) is able to write faster and tighter code in a language they know well (which, in my case, is Perl), than in other that’s supposed to be faster but is unknown.
BTW, you can use anything as a genome in Algorithm::Evolutionary, as long as you match the operators you use with it. There are even several underlying representations for things like bitstrings (string vs. bit vector, guess which one is faster?)