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