------ art_36096_23896875.1191792647502
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Hi all-
This is my first quiz. I am a java developer and I decided that I want to
learn ruby. I had previously written a genetic algorithm framework in java
and I decided it would be a cool exercise to port it to ruby. I am loving
ruby BTW! Anyways, the code may not be as terse as it could be, but it
works fairly well nonetheless. I tested primarily with a 5x5 grid because
it converges on the optimal solution between 2 and 12 seconds (typically),
but I did run it on a 7x7 grid and a 10x10 grid. The optimal solution for
the 7x7 grid was reached at about 8.5 minutes, however, I got tired of
waiting for the 10x10 to converge, so I killed the process. Anyways, here
is my code:
#!/usr/bin/ruby -w
#genetic.rb
module RubyGa
class Gene
attr_accessor :city, :lat, :lon
def initialize(city il, lat .0, lon .0)
@city ity
@lat at
@lon on
end
def copy
Gene.new(@city, @lat, @lon)
end
def eql?(gene)
self gene
end
def gene)
gene.class self.class &&
@city gene.city &&
@lat gene.lat &&
@lon gene.lon
end
def to_s
"(#{@lat}, #{@lon})"
end
end # Gene
class Chromosome < Array
def initialize(fitness .0, fitness_alg itness.new)
@fitness itness
@fitness_alg itness_alg
end
def genes(i , j ize)
ngenes ]
if (i > -1 && j < ize && j > )
i.upto(j-1) do |k|
ngenes << self[k].copy
end
end
ngenes
end
def chrom)
false unless chrom.class self.class && size chrom.size
0.upto(size-1) do |i|
return false unless self[i] chrom[i]
end
true
end
def eql?(chrom)
self chrom
end
def fitness
if @fitness 0.0
@fitness fitness_alg.rank(self)
end
@fitness
end
def copy
c hromosome.new(0.0, @fitness_alg)
genes.each do |gene|
c << gene
end
c
end
end # Chromosome
class Grid
attr_reader :n, :pts, :min
def initialize(n)
raise ArgumentError unless Integer n && n > 1
@n
@pts ]
n.times do |i|
x .to_f
n.times { |j| @pts << [x, j.to_f] }
end
# @min is length of any shortest tour traversing the grid.
@min * n
@min + ath::sqrt(2.0) - 1 if @n & 1 1
puts "Shortest possible tour {@min}"
end
end # Grid
class Genotype
attr_accessor :grid
def initialize(grid rid.new(5))
@grid rid
@genes rray.new
pts grid.pts
for i in 0...pts.length
pair ts.shift
x air.shift
y air.shift
@genes << Gene.new("Node #{i}", x, y)
end
end
def new_rand_chrom
@genes.replace @genes.sort_by { rand }
c hromosome.new
@genes.each do |gene|
c << gene.copy
end
c
end
end # Genotype
class Fitness
def rank(chrom)
fit istance(chrom.last, chrom.first)
i
while i < chrom.length - 1
g0 hrom[i]
g1 hrom[i+1]
fit + istance(g0, g1)
i +
end
fit
end
def distance(g0, g1)
Math::sqrt( ((g1.lat-g0.lat).abs**2) + ((g1.lon-g0.lon).abs**2) )
end
end # Fitness
class Crossover
attr_accessor :rate
def initialize
@rate .90
end
def crossover(p0, p1)
children ]
if rand < @rate
c0, c1 hromosome.new, Chromosome.new
min p0.length, p1.length].min
index and(min)
for i in index...min
c0 << p0[i].copy
c1 << p1[i].copy
end
children << fill(c0, p1)
children << fill(c1, p0)
end
children
end
private
def fill(c, p)
p.each do |gene|
c << gene unless c.include?(gene)
end
c
end
end # Crossover
class Mutator
attr_accessor :rate
def initialize
@rate .10
end
def mutate!(chrom)
if rand < @rate
s hrom.length - 1
r1 and(s)
r2 and(s)
while r1 r2
r2 and(s)
end
min r1, r2].min
max r1, r2].max
while max > min
chrom[min], chrom[max] hrom[max], chrom[min]
max -
min +
end
end
end
end # Mutator
class Population < Array
attr_accessor :genotype, :crossover, :mutator, :offspring
def initialize(genotype enotype.new, crossover rossover.new,
mutator utator.new)
@genotype enotype
@crossover rossover
@mutator utator
end
def prepare(size 00, initial_size 000, offspring 0)
@offspring ffspring
initial ]
initial_size.times do
g genotype.new_rand_chrom
initial << g unless initial.include?(g)
end
sort!(initial)
size.times do
self << initial.shift
end
end
def reproduce
(@offspring/2).times do
parents elect_parents
children crossover.crossover(parents[0], parents[1])
children.each do |child|
@mutator.mutate!(child)
self.pop
self.unshift(child)
end
end
sort!
end
def min
@genotype.grid.min
end
private
def sort!(list elf)
list.replace list.sort_by { |chrom| chrom.fitness }
end
def select_parents
parents ]
s ize
r1, r2 and(s), rand(s)
while r1 r2
r2 and(s)
end
parents << self[r1]
parents << self[r2]
parents
end
end # Population
end # RubyGa
if __FILE__ $0
include RubyGa
s ime.now
puts "Genetic algorithm started at #{s}"
p opulation.new
p.prepare(20, 100, 15)
best_so_far .first.fitness
gen
while best_so_far > p.min
p.reproduce
if p.first.fitness < best_so_far
puts "Best fitness found {p.first.fitness} at generation #{gen}"
puts "Path n#{p.first.join(" -> ")}"
puts "#{Time.now-s} seconds into execution"
puts
best_so_far .first.fitness
end
gen +
end
end
Since I am very new to ruby (been at it in my spare time now for about a
month), I would appreciate any comments/suggestions anyone may have.
Thanks,
-Dave Pederson
------ art_36096_23896875.1191792647502--