From: Peter Hickman <peter@...>
Date: 2004-12-15T18:22:05+09:00
Subject: Re: Implementing Genetic algorithm in Ruby

--------------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--