--------------070308070308020605020701
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Hi, I took an interest in genetic algorithm after reading this article:
http://www-106.ibm.com/developerworks/linux/library/l-genperl/
The code listing is here:
http://www-106.ibm.com/developerworks/linux/library/l-genperl/numbers.html
To gain a better understanding, I tried the convert the code to Ruby,
and on the way I should be able to understand how it works.
Unfortunately my lack of knowledge in genetic and Perl means I couldn't
quite get the code working. When it runs, each generation doesn't seem
to improve. It would be great if someone could take a look, compare it
to the original Perl version and see where I've gone wrong, and the fix
require to get it working. The code's attached to this post.
Robo
p.s. the link was part one of the series, part two and three are here:
http://www-106.ibm.com/developerworks/linux/library/l-genperl2/
http://www-106.ibm.com/developerworks/linux/library/l-genperl3.html
--------------070308070308020605020701
Content-Type: text/plain;
name umbers.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename umbers.rb"
popsize 56
mut_rate .01
min_fitness .1
generation_count 00000
generation
pop_ref ]
def init_population(population, pop_size)
(1..pop_size).each do |id|
#insert individual's data to the population array
#the DNA is equal to the individual's number minus 1 (0-255)
population << {'dna' id - 1, 'survived' true, 'parent' 0, 'fitness' 0}
end
end
def evaluate_fitness(population, fitness_function)
population.each do |individual|
#set the fitness to result of the fitness function
m elf.method(fitness_function)
individual['fitness'] .call(individual['dna'])
end
end
def survive(population, min_fitness)
population.each do |individual|
individual['survived'] ndividual['fitness'] > in_fitness
#set fitness to 0 for unfit individuals (so they won't procreate)
individual['fitness'] if individual['fitness'] < min_fitness
end
end
def select_parents(population)
pop_size opulation.length
#create the weights array: select only survivors from the population,
#then use map to have only the fitness come through
weights opulation.select { |individual| individual['survived'] }.map { |individual| individual['fitness'] }
raise 'Population size pop_size is too small' if pop_size < 2
#fill pop_size parenting slots, to preserve the population size
(1..pop_size).each do |slot|
index ample(weights)
population[index]['parent'] +
end
end
def recombine(population)
pop_size opulation.length
parent_population ]
new_population ]
total_parent_slots
while total_parent_slots !
#find out how many parent slots are left
total_parent_slots
total_parent_slots opulation.inject(0) { |sum, individual| sum + individual['parent'] }
break unless total_parent_slots > 0
#we're sure at least one individual with parent > 0
individual il
while individual nil do
individual opulation[rand(pop_size)]
#individual is acceptable only if he can be a parent
individual il unless individual['parent'] > 0
end
#insert individual to parent population
parent_population << individual
individual['parent'] -
end
parent_population.each do |parent|
#select parent #2
parent2 arent_population[rand(pop_size)]
child 'survived' true, 'parent' 0, 'fitness' 0}
#this is breeding!
bitmask and(256)
#swap random bits between parents, according to the bitmask
child['dna'] parent2['dna'] & bitmask) | (parent['dna'] & ~bitmask)
new_population << child
end
new_population
end
def mutate(population, mut_rate)
population.each do |individual|
#only mutate if rand() more than mut_rate
next if rand > mut_rate
#mutate DNA by and-ing then or-ing two integers between 0-255
old_dna ndividual['dna']
individual['dna'] & and(256)
individual['dna'] | and(256)
puts "Mutated old_dna to #{individual['dna']}"
end
end
def fitness(dna)
dna / 256
end
#sample an array of weighted elements
def sample(weights)
count ample
weights.each_index do |i|
count + eights[i]
sample if rand(count[i]) !
end
#return an index into the weights array
sample
end
init_population(pop_ref, popsize)
while (generation + ) < generation_count do
evaluate_fitness(pop_ref, :fitness)
#print out a summary line
sorted_population op_ref.sort_by { |individual| individual['fitness'] }
printf("generation %d: size %d, least fit DNA [%d], most fit DNA [%d]\n",
generation,
sorted_population.length,
sorted_population[0]['dna'],
sorted_population[-1]['dna'])
#select survivors from population
survive(pop_ref, min_fitness)
select_parents(pop_ref)
pop_ref ecombine(pop_ref)
#working on new generation in pop_ref
#apply mutation to individual
mutate(pop_ref, mut_rate)
end
--------------070308070308020605020701
Content-Type: text/plain;
name umbers.pl"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename umbers.pl"
#!/usr/bin/perl -w
# GA demonstration with numeric DNA (between 0 and 255)
use strict;
use Data::Dumper;
# individuals in the population - no sense making more than DNA can provide for
my $popsize 56;
my $mut_rate .01; # the mutation rate
my $min_fitness .1; # the minimum fitness for survival
my $generation_count 00000; # run for this many generations
my $generation ; # generation counter
my $pop_ref ]; # a reference to a population array
init_population($pop_ref, $popsize);
do
{
evaluate_fitness($pop_ref, \&fitness);
# print out a generation summary line
my @sorted_population ort { $a->{fitness} $b->{fitness} } @$pop_ref;
printf "generation %d: size %d, least fit DNA [%d], most fit DNA [%d]\n",
$generation,
scalar @sorted_population,
$sorted_population[0]->{dna},
$sorted_population[-1]->{dna};
survive($pop_ref, $min_fitness); # select survivors from the population
select_parents($pop_ref);
$pop_ref ecombine($pop_ref); # recombine() returns a whole new population array reference
# from this point on, we are working with a new generation in $pop_ref
mutate($pop_ref, $mut_rate); # apply mutation to the individuals
} while ($generation++ < $generation_count); # run until we are out of generations
sub init_population
{
my $population hift @_;
my $pop_size hift @_;
# for each individual
foreach my $id (1 .. $pop_size)
{
# insert an anonymous hash reference in the population array with the individual's data
# the DNA is equal to the individual's number minus 1 (0-255)
push @$population, { dna $id-1, survived 1, parent 0, fitness 0 };
}
}
sub evaluate_fitness
{
my $population hift @_;
my $fitness_function hift @_;
foreach my $individual (@$population)
{
# set the fitness to the result of invoking the fitness function
# on the individual's DNA
$individual->{fitness} fitness_function->($individual->{dna});
}
}
sub survive
{
my $population hift @_;
my $min_fitness hift @_;
foreach my $individual (@$population)
{
# set the fitness to the result of invoking the fitness function
# on the individual's DNA
$individual->{survived} individual->{fitness} > min_fitness;
# set the fitness to 0 for unfit individuals (so they won't procreate)
$individual->{fitness} if $individual->{fitness} < $min_fitness;
}
}
sub select_parents
{
my $population hift @_;
my $pop_size calar @$population; # population size
# create the weights array: select only survivors from the population,
# then use map to have only the fitness come through
my @weights ap { $_->{fitness} } grep { $_->{survived} } @$population;
# if we have less than 2 survivors, we're in trouble
die "Population size $pop_size is too small" if $pop_size < 2;
# we need to fill $pop_size parenting slots, to preserve the population size
foreach my $slot (1..$pop_size)
{
my $index ample(\@weights); # we pass a reference to the weights array here
# do sanity checking on $index
die "Undefined index returned by sample()"
unless defined $index;
die "Invalid index $index returned by sample()"
unless $index > && $index < $pop_size;
# increase the parenting slots for this population member
$population->[$index]->{parent}++;
}
}
sub recombine
{
my $population hift @_;
my $pop_size calar @$population; # population size
my @parent_population;
my @new_population;
my $total_parent_slots ;
while ($total_parent_slots)
{
# find out how many parent slots are left
$total_parent_slots ;
$total_parent_slots + _->{parent} foreach @$population;
last unless $total_parent_slots;
# if we are here, we're sure we have at least one individual with parent > 0
my $individual ndef; # start with an undefined individual
do
{
# select a random individual
$individual population->[int(rand($pop_size))];
# individual is acceptable only if he can be a parent
undef($individual) unless $individual->{parent};
} while (not defined $individual);
push @parent_population, $individual; # insert the individual in the parent population
$individual->{parent}--; # decrease the parenting slots of the individual by 1
}
foreach my $parent (@parent_population)
{
# select a random individual from the parent population (parent #2)
my $parent2 parent_population[int(rand($pop_size))];
my $child survived 1, parent 0, fitness 0 };
# this is breeding!
my $bitmask nt(rand(256)); # a random byte between 0 and 255
# swap random bits between parents, according to the bitmask
$child->{dna} $parent2->{dna} & $bitmask) | ($parent->{dna} & ~$bitmask);
push @new_population, $child; # the child is now a part of the new generation
}
return \@new_population;
}
sub mutate
{
my $population hift @_;
my $mut_rate hift @_;
foreach my $individual (@$population)
{
# only mutate individuals if rand() returns more than mut_rate
next if rand > $mut_rate;
# mutate the DNA by and-ing and then or-ing it with two random
# integers between 0 and 255
my $old_dna individual->{dna};
$individual->{dna} & nt(rand(256));
$individual->{dna} | nt(rand(256));
# print "Mutated $old_dna to ", $individual->{dna}, "\n";
}
}
sub fitness
{
my $dna hift @_;
return $dna/256;
}
# Function to sample from an array of weighted elements
# originally written by Abigail <abigail / foad.org>
sub sample
{
# get the reference to the weights array
my $weights hift @_ or return undef;
# internal counting variables
my ($count, $sample);
for (my $i ; $i < scalar @$weights; $i ++)
{
$count + weights->[$i];
$sample i if rand $count [$i];
}
# return an index into the weights array
return $sample;
}
--------------070308070308020605020701--