Implementing Genetic algorithm in Ruby

[Robo]

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

popsize = 256
mut_rate = 0.01
min_fitness = 0.1
generation_count = 100000
generation = 0
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 = self.method(fitness_function)
individual['fitness'] = m.call(individual['dna'])
end
end

def survive(population, min_fitness)
population.each do |individual|
individual['survived'] = individual['fitness'] >= min_fitness
#set fitness to 0 for unfit individuals (so they won't procreate)
individual['fitness'] = 0 if individual['fitness'] < min_fitness
end
end

def select_parents(population)
pop_size = population.length

#create the weights array: select only survivors from the population,
#then use map to have only the fitness come through
weights = population.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 = sample(weights)
population[index]['parent'] += 1
end
end

def recombine(population)
pop_size = population.length
parent_population = []
new_population = []

total_parent_slots = 1

while total_parent_slots != 0
#find out how many parent slots are left
total_parent_slots = 0
total_parent_slots = population.inject(0) { |sum, individual| sum + individual['parent'] }

break unless total_parent_slots > 0

#we're sure at least one individual with parent > 0
individual = nil
while individual == nil do
individual = population[rand(pop_size)]
#individual is acceptable only if he can be a parent
individual = nil unless individual['parent'] > 0
end

#insert individual to parent population
parent_population << individual
individual['parent'] -= 1
end

parent_population.each do |parent|
#select parent #2
parent2 = parent_population[rand(pop_size)]

child = {'survived' => true, 'parent' => 0, 'fitness' => 0}

#this is breeding!
bitmask = rand(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 = individual['dna']
individual['dna'] &= rand(256)
individual['dna'] |= rand(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 = sample = 0

weights.each_index do |i|
count += weights
sample = i if rand(count) != 0
end

#return an index into the weights array
sample
end

init_population(pop_ref, popsize)
while (generation += 1) < generation_count do
evaluate_fitness(pop_ref, :fitness)

#print out a summary line
sorted_population = pop_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 = recombine(pop_ref)

#working on new generation in pop_ref
#apply mutation to individual
mutate(pop_ref, mut_rate)
end

#!/usr/bin/perl -w

# GA demonstration with numeric DNA (between 0 and 255)

use strict;
use Data:umper;

# individuals in the population - no sense making more than DNA can provide for
my $popsize = 256;
my $mut_rate = 0.01; # the mutation rate
my $min_fitness = 0.1; # the minimum fitness for survival
my $generation_count = 100000; # run for this many generations
my $generation = 0; # 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 = sort { $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 = recombine($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 = shift @_;
my $pop_size = shift @_;

# 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 = shift @_;
my $fitness_function = shift @_;

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 = shift @_;
my $min_fitness = shift @_;

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} = 0 if $individual->{fitness} < $min_fitness;
}
}

sub select_parents
{
my $population = shift @_;
my $pop_size = scalar @$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 = map { $_->{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 = sample(\@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 >= 0 && $index < $pop_size;

# increase the parenting slots for this population member
$population->[$index]->{parent}++;

}

}

sub recombine
{
my $population = shift @_;
my $pop_size = scalar @$population; # population size
my @parent_population;
my @new_population;

my $total_parent_slots = 1;

while ($total_parent_slots)
{
# find out how many parent slots are left
$total_parent_slots = 0;
$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 = undef; # 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 = int(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 = shift @_;
my $mut_rate = shift @_;

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} &= int(rand(256));
$individual->{dna} |= int(rand(256));
# print "Mutated $old_dna to ", $individual->{dna}, "\n";
}
}

sub fitness
{
my $dna = shift @_;
return $dna/256;
}

# Function to sample from an array of weighted elements
# originally written by Abigail <[email protected]>
sub sample
{
# get the reference to the weights array
my $weights = shift @_ or return undef;
# internal counting variables
my ($count, $sample);

for (my $i = 0; $i < scalar @$weights; $i ++)
{
$count += $weights->[$i];
$sample = $i if rand $count [$i];
}

# return an index into the weights array
return $sample;
}

 

[Phil Tomson]

-=-=-=-=-=-

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.

That's a lot of code.

If you're interested I've got some Ruby code I wrote for a GA class I took
a couple of years ago. At least I know it works (as in there is
improvement from generation to generation). email me if you're interested
and I'll try to dig it up.

Phil

 

[ts]

R> Unfortunately my lack of knowledge in genetic and Perl means I couldn't
R> quite get the code working. When it runs, each generation doesn't seem
R> to improve. It would be great if someone could take a look, compare it
R> to the original Perl version and see where I've gone wrong, and the fix
R> require to get it working. The code's attached to this post.

First the P version seems wrong. Perhaps best if you find a better
algorithm.

At least there are some basic errors

R> my @sorted_population = sort { $a->{fitness} $b->{fitness} } @$pop_ref;

<=>

missing


R> my $pop_size = scalar @$population; # population size
R>
R> # create the weights array: select only survivors from the population,
R> # then use map to have only the fitness come through
R> my @weights = map { $_->{fitness} } grep { $_->{survived} } @$population;
R>
R> # if we have less than 2 survivors, we're in trouble
R> die "Population size $pop_size is too small" if $pop_size < 2;

this algorithm seems wrong : be carefull with it

R> $count += $weights->[$i];
R> $sample = $i if rand $count [$i];

rand($count) < $weights->[$i];

R> }

unless (defined $sample) {
$sample = $weights->[0];
}

R> return $sample;
R> }

For the ruby version : you have at least a problem with fitness


R> def fitness(dna)
R> dna / 256

dna / 256.0 # otherwise ruby can use integer /

R> end

R> #sample an array of weighted elements
R> def sample(weights)
R> count = sample = 0

R> weights.each_index do |i|
R> count += weights
R> sample = i if rand(count) != 0

rand(count) < weights

R> end



Guy Decoux

 

[Michael DeHaan]

"Unfortunately my lack of knowledge in genetic"

Unfortunately I misread this as "my lack of knowledge is genetic", but
I am running on a caffeine shortage

I don't have time to work with your code right now, but generally
speaking throwing some classes and object methods in there would
improve the readability quite a bit -- I do understand you were trying
a more-or-less direct port.

I've frequently looked at Perl code on developerworks and thought it
could be improved significantly with better modularity. Developer
works does not do a good job of technical editing, IMHO, so they turn
into a bit of a "submit article, get $$$" farm. You might want to
search perlmonks.org for better Perl examples, or you could look at
some of the genetic algorithm stuff already on CPAN.

 

[Peter Hickman]

--------------070701030701040408070501
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Here's a little bit of code that I hacked up overnight for a string
based GA.

It lacks quite a lot, like a crossover method for example, but it go
quite some way to getting the basic structure up and running.

I will continue to hack away at it over the week.



--------------070701030701040408070501
Content-Type: text/plain;
name="ga.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="ga.rb"

class Pool
def initialize(pool_size, string_size)
pm = Struct.new( "PoolMember", :fitness, :ranking, :data )

@pool = Array.new

pool_size.times do
@pool << pm.new(0.0, 1, random_string(string_size))
end

@best = pm.new(0.0, 1, '')
end

def display_pool
puts "Fitnes Rank Data"
puts "------ ----- " + ('-' * @pool[0][:data].size)
@pool.each do |entry|
puts "%6.2f %5d %s" % [entry[:fitness], entry[:ranking], entry[:data]]
end
end

def apply_fitness
@pool.each do |entry|
entry[:fitness] = calculate_fitness( entry[:data] )
end

sort_pool

set_rank

if @pool.first[:fitness] > @best[:fitness] then
@best[:fitness] = @pool.first[:fitness]
@best[:data] = @pool.first[:data]
end
end

def apply_mutation( probability )
@pool.each do |entry|
(0...entry[:data].size).each do |index|
if rand < probability then
if entry[:data][index].chr == '1' then
entry[:data][index] = '0'
else
entry[:data][index] = '1'
end
end
end
end
end

def best
return @best[:fitness], @best[:data]
end

def create_new_pool
newpool = Array.new

##
## A simple fitness based selection
##

total_fitness = 0.0
last_fitness = 0.0

@pool.each do |entry|
total_fitness += entry[:fitness]
entry[:fitness] += last_fitness
last_fitness = entry[:fitness]
end

while newpool.size != @pool.size do
value_to_match = random_value( total_fitness )
@pool.each do |entry|
if entry[:fitness] >= value_to_match then
newpool << entry[:data]
break
end
end
end

##
## Put the new strings back into the pool
##

@pool.each_index do |index|
@pool[index][:data] = newpool[index]
@pool[index][:fitness] = 0.0
end

set_rank
end

private

def set_rank
rank = 1
@pool.each do |entry|
entry[:ranking] = rank
rank += 1
end
end

def random_value( value )
return rand * value
end

def random_string( length )
x = ''

length.times do
x += (rand < 0.5) ? '0' : '1'
end

return x
end

def sort_pool
@pool.sort! { |a, b| b[:fitness] <=> a[:fitness] }
end

def calculate_fitness( data )
raise "You need to subclass to implment this function"
end
end

class NewPool < Pool
def calculate_fitness( data )
total = data.size

data.split(//).each_index do |index|
if index % 2 == 0 then
if data[index].chr == '0' then
total = total + 1
else
total = total - 1
end
else
if data[index].chr == '1' then
total = total + 1
else
total = total - 1
end
end
end

return total.to_f
end
end

x = NewPool.new(30,40)
x.apply_fitness
x.display_pool
puts x.best
25.times do
x.create_new_pool
x.apply_mutation( 0.3 )
# apply crossover
x.apply_fitness
puts x.best
end
x.display_pool

--------------070701030701040408070501--