Genetic algorithm for Clever Algorithms project

I wrote a bunch of Ruby code for a book project I've just finished. One criticism is that it is fine code but not very "ruby like". I agree my style was simplified for communication reasons, and although it's procedural code, it still feels "ruby-like" to me.

For the representative example below, any ideas on making it more "Ruby like"?

```
# Genetic Algorithm in the Ruby Programming Language

# The Clever Algorithms Project: http://www.CleverAlgorithms.com
# (c) Copyright 2010 Jason Brownlee. Some Rights Reserved.
# This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 2.5 Australia License.

def onemax(bitstring)
sum = 0
bitstring.size.times {|i| sum+=1 if bitstring[i].chr=='1'}
return sum
end

def random_bitstring(num_bits)
return (0...num_bits).inject(""){|s,i| s pop[j][:fitness]) ? pop[i] : pop[j]
end

def point_mutation(bitstring, rate=1.0/bitstring.size)
child = ""
bitstring.size.times do |i|
bit = bitstring[i].chr
child =rate
point = 1 + rand(parent1.size-2)
return parent1[0...point]+parent2[point...(parent1.size)]
end

def reproduce(selected, pop_size, p_cross, p_mutation)
children = []
selected.each_with_index do |p1, i|
p2 = (i.modulo(2)==0) ? selected[i+1] : selected[i-1]
p2 = selected[0] if i == selected.size-1
child = {}
child[:bitstring] = crossover(p1[:bitstring], p2[:bitstring], p_cross)
child[:bitstring] = point_mutation(child[:bitstring], p_mutation)
children = pop_size
end
return children
end

def search(max_gens, num_bits, pop_size, p_crossover, p_mutation)
population = Array.new(pop_size) do |i|
{:bitstring=>random_bitstring(num_bits)}
end
population.each{|c| c[:fitness] = onemax(c[:bitstring])}
best = population.sort{|x,y| y[:fitness] x[:fitness]}.first
max_gens.times do |gen|
selected = Array.new(pop_size){|i| binary_tournament(population)}
children = reproduce(selected, pop_size, p_crossover, p_mutation)
children.e

First a note on your general design: You use hashmaps to represent members of the population. I'd rather recommend you create a little class to represent them:

class Individual
  include Comparable

  attr_reader :bitstring, :fitness

  def initialize(bitstring)
    @bit_string = bitstring
    @fitness = onemax(bitstring)
  end

  def (other)
    fitness  other.fitness
  end
end

You'll now use Individual.new(bitstring) to create a new individual (which will automatically calculate its own fittness) and individual.bitstring and individual.fitness to get an individual's bitstring or fitness respectively.

This has the benefit that now the logic of how to calculate an individuals fitness lives in the Individual class instead of in multiple place in the search method. This is a more natural place for it and makes it easier to find and change should you ever decide to use a different fitness function.

Also note that I included Comparable, implementing ` based on fitness. This means that you can now compare individuals to each other such that an individual is greater than another if and only if its fitness is greater. This allows you to use > on two individuals as well as methods like max to get the individual with the greatest fitness out of an array of individuals. It also allows you to call sort on array of individuals without passing a block. This will simplify your code in some places.

In a comment you mentioned that you don't want to use classes. However I still think that it would greatly improve your design to have the logic for creating new individuals and calculating their fitness in one single place, so you should at least factor it out into a method like this:

def create_individual(bitstring)
    {:bitstring => bitstring, :fitness => onemax(bitstring)}
end

Now some notes on particular pieces of code:

bitstring.size.times {|i| sum+=1 if bitstring[i].chr=='1'}

As has already been mentioned, this can easily be replaced with a call to count. However as a general note I want to point out that it's good practice to avoid index-based loops wherever possible, so if count did not exist, I'd write the above like this:

bitstring.each_char {|c| sum+=1 if c == '1'}

Or for 1.8.6 compability:

bitstring.each_byte {|b| sum+=1 if b.chr == '1'}

(0...num_bits).inject(""){|s,i| s<<((rand<0.5) ? "1" : "0")}

When dealing with inject, it's usually a good idea to keep the function simple, so it's more easily understandable. Often you can separate the logic of generating the elements from the logic of combining them, by using map before inject. This would make your code look like this:

(0...num_bits).map {|i| (rand<0.5) ? "1" : "0"}.inject("") {|s,i| s<<i}

Now there's two things to notice here:

• Whenever you call map on a range from 0 to some size, you might rather want to use Array.new(size) {block} which creates an array of the given size by calling the block size times.






• The smaller inject is now much easier to understand, but happens to be equivalent to calling join, so let's just do that.

So your code becomes:

Array.new(num_bits) { (rand<0.5) ? "1" : "0" }.join

This way you create a temporary array, which you didn't before, but on the other hand your code became much more understandable, so that little inefficiency should be worth it.

(pop[i][:fitness] > pop[j][:fitness]) ? pop[i] : pop[j]

Thanks to the Individual class this now looks like this:

(pop[i] > pop[j]) ? pop[i] : pop[j]

This isn't much different, but note that it now has the form (x > y) ? x : y, which incidentally means "the maximum of two objects". In other words we can simplify this code by using the max method:

[ pop[i], pop[j] ].max

bitstring.size.times do |i|
  bit = bitstring[i].chr

Again this should be bitstring.each_char do |bit| or bitstring.each_byte do |b| bit = b.chr.

""+parent1 if rand()>=rate

I'm not sure what the ""+ is supposed to do here. Remove it. Note that ""+x is not a way to turn x into a string in ruby (like it would be in e.g. Java). Calling ""+x when x is not a string (or "duck-string"), will cause a type error.

The fact that you're using ""+ to create a copy is less than obvious (thus the above paragraph). If you use the dup method, whose sole purpose it is to create a copy, instead, it will be much more understandable.

I'd also change the crossover` method to return an individual rather than a string, which makes the code a bit simpler.

StackExchange Code Review Q#354, answer score: 22