Implementing Genetic algorithm in Ruby

Discussion in 'Ruby' started by Robo, Dec 14, 2004.

  1. Robo

    Robo Guest

    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::Dumper;

    # 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 <>
    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;
    }
    Robo, Dec 14, 2004
    #1
    1. Advertising

  2. Robo

    Phil Tomson Guest

    In article <YsCvd.14841$>,
    Robo <> wrote:
    >-=-=-=-=-=-
    >
    >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
    Phil Tomson, Dec 14, 2004
    #2
    1. Advertising

  3. Robo

    ts Guest

    >>>>> "R" == Robo <> writes:

    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
    ts, Dec 14, 2004
    #3
  4. "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.


    On Wed, 15 Dec 2004 00:27:26 +0900, Phil Tomson <> wrote:
    > In article <YsCvd.14841$>,
    > Robo <> wrote:
    > >-=-=-=-=-=-
    > >
    > >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
    >
    >
    Michael DeHaan, Dec 14, 2004
    #4
  5. --------------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--
    Peter Hickman, Dec 15, 2004
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. SNAKE

    genetic algorithm

    SNAKE, Nov 4, 2003, in forum: C++
    Replies:
    2
    Views:
    329
    Allan Bruce
    Nov 4, 2003
  2. Sean Ross

    OT: Genetic Algorithm Recipe Bug Fix

    Sean Ross, Jul 3, 2003, in forum: Python
    Replies:
    6
    Views:
    341
    Andrew Dalke
    Jul 18, 2003
  3. Max

    Python Genetic Algorithm

    Max, Jan 27, 2008, in forum: Python
    Replies:
    14
    Views:
    1,070
    Wildemar Wildenburger
    Jan 28, 2008
  4. n/a
    Replies:
    2
    Views:
    103
  5. Peter Laurens

    Ruby Genetic Algorithm Library

    Peter Laurens, Nov 30, 2007, in forum: Ruby
    Replies:
    2
    Views:
    170
    Marcin Mielżyński
    Nov 30, 2007
Loading...

Share This Page