From: Morton Goldberg <m_goldberg@...>
Date: 2007-10-10T02:41:43+09:00
Subject: Re: [QUIZ] Itinerary for a Traveling Salesman (#142)

This is my GA solution to Quiz 142. It is comprised of four files: a  
command line interface and run controller, a GA solver, a path model,  
and -- of course -- a grid model. I am omitting the grid model from  
this posting because it was part of the quiz description.

<code ga_path.rb>
#! /usr/bin/env ruby -w
# ga_path.rb
# GA_Path
#
# Created by Morton Goldberg on September 18, 2007

# A CLI and runtime controller for a GA solver intended to find paths  
that
# are approximations to the shortest tour traversing a grid.
#
# This script requires a POSIX-compatible system because the runtime
# controller uses the stty command.
#
# The paths modeled here begin at the origin (0, 0) and traverse a n x n
# grid. That is, the paths pass through every point on the grid exactly
# once before returning to the origin.
#
# Any minimal path traversing such a grid has length = n**2 if n is even
# and length = n**2 - 1 + sqrt(2) if n is odd.

ROOT_DIR = File.dirname(__FILE__)
$LOAD_PATH << File.join(ROOT_DIR, "lib")

require "thread"
require "getoptlong"
require "grid"
require "path"
require "ga_solver"

class SolverControl
    def initialize(solver, t_run, t_print, feedback)
       @solver = solver
       @t_run = t_run
       @t_print = t_print
       @feedback = feedback
       @cmd_queue = Queue.new
       @settings = '"' + `stty -g` + '"'
       begin
          system("stty raw -echo")
          @keystoke_thread = Thread.new { keystoke_loop }
          solver_loop
       ensure
          @keystoke_thread.kill
          system("stty #{@settings}")
       end
    end
private
    def solver_loop
       t_delta = 0.0
       t_remain = @t_run
       catch :done do
          while t_remain > 0.0
             t_start = Time.now
             @solver.run
             t_delta += (Time.now - t_start).to_f
             if t_delta >= @t_print
                t_remain -= t_delta
                if @feedback && t_remain > 0.0
                   say sprintf("%6.0f seconds %6.0f remaining\t\t%s",
                               @t_run - t_remain, t_remain,
                               @solver.best.snapshot)
                end
                t_delta = 0.0
                send(@cmd_queue.deq) unless @cmd_queue.empty?
             end
          end
       end
    end
    def keystoke_loop
       loop do
          ch = STDIN.getc
          case ch
          when ?f
             @cmd_queue.enq(:feedback)
          when ?r
             @cmd_queue.enq(:report)
          when ?q
             @cmd_queue.enq(:quit)
          end
       end
    end
    # Can't use Kernel#puts because raw mode is set.
    def say(msg)
       print msg + "\r\n"
    end
    def feedback
       @feedback = !@feedback
    end
   def report
       say @solver.best.to_s.gsub!("\n", "\r\n")
    end
    def quit
       throw :done
    end
end

# Command line interface
#
# See the USAGE message for the command line parameters.
# While the script is running:
#    press 'f' to toggle reporting of elapsed and remaining time
#    press 'r' to see a progress report and continue
#    press 's' to see a progress snapshot and continue
#    press 'q' to quit
# Report shows length, excess, and point sequence of current best path
# Snapshot shows only length and excess of current best path.

grid_n = nil # no default -- arg must be given
pop_size = 20 # solver's path pool size
mult = 3 # solver's initial population = mult * pop_size
run_time = 60.0 # seconds
print_interval = 2.0 # seconds
feedback = true # time-remaining messages every PRINT_INTERVAL

USAGE = <<MSG
ga_path -g n [OPTIONS]
ga_path --grid n [OPTIONS]
   -g n, --grid n
      set grid size to n x n (n > 1)   (required argument)
      n > 1
   -s n, --size n
      set population size to n         (default=#{pop_size})
   -m n, --mult n
      set multiplier to n              (default=#{mult})
   -t n, --time n
      run for n seconds                (default=#{run_time})
   -p n, --print n
      set print interval to n seconds  (default=#{print_interval})
   -q, --quiet
      starts with feedback off         (optional)
   -h
      print this message and exit
MSG

GRID_N_BAD = <<MSG
#{__FILE__}: required argument missing or bad
\t-g n or --grid n, where n > 1, must be given
MSG

# Process cammand line arguments
args = GetoptLong.new(
    ['--grid',  '-g', GetoptLong::REQUIRED_ARGUMENT],
    ['--size',  '-s', GetoptLong::REQUIRED_ARGUMENT],
    ['--mult',  '-m', GetoptLong::REQUIRED_ARGUMENT],
    ['--time',  '-t', GetoptLong::REQUIRED_ARGUMENT],
    ['--print', '-p', GetoptLong::REQUIRED_ARGUMENT],
    ['--quiet', '-q', GetoptLong::NO_ARGUMENT],
    ['-h',            GetoptLong::NO_ARGUMENT]
)
begin
    args.each do |key, val|
       case key
       when '--grid'
          grid_n = Integer(val)
       when '--size'
          pop_size = Integer(val)
       when '--mult'
          mult = Integer(val)
       when '--time'
          run_time = Float(val)
       when '--print'
          print_interval = Float(val)
       when '--quiet'
          feedback = false
       when '-h'
          raise ArgumentError
       end
    end
rescue GetoptLong::MissingArgument
    exit(-1)
rescue ArgumentError, GetoptLong::Error
    puts USAGE
    exit(-1)
end
unless grid_n && grid_n > 1
    puts GRID_N_BAD
    exit(-1)
end

# Build an initial population and run the solver.

grid = Grid.new(grid_n)
initial_pop = Array.new(mult * pop_size) { Path.new(grid).randomize }
solver = GASolver.new(pop_size, initial_pop)
puts "#{grid_n} x #{grid_n} grid" if feedback
SolverControl.new(solver, run_time, print_interval, feedback)
puts solver.best
</code>

<code lib/ga_solver.rb>
# lib/ga_solver.rb
# GA_Path
#
# Created by Morton Goldberg on August 25, 2007
#
# Stochastic optimization by genetic algorithm. This is a generic GA
# solver -- it knows nothing about the problem it is solving.

class GASolver
    attr_reader :best
    def initialize(pop_size, init_pop)
       @pop_size = pop_size
       @population = init_pop
       select
    end
    def run(steps=1)
       steps.times do
          replicate
          select
       end
    end
private
    def replicate
       @pop_size.times { |n| @population << @population[n].replicate }
    end
    def select
       @population = @population.sort_by { |item| item.ranking }
       @population = @population.first(@pop_size)
       @best = @population.first
    end
end
</code>

<code lib/path.rb>
# lib/path.rb
# GA_Path
#
# Created by Morton Goldberg on September 18, 2007
#
# Models paths traversing a grid starting from and returning to the  
origin.
# Exposes an interface suitable for finding the shortest tour traversing
# the grid using a GA solver.

require "enumerator"

class Path
    attr_reader :ranking, :pts, :grid
    def initialize(grid)
       @grid = grid
       @order = grid.n**2
       @ranking = nil
       @pts = nil
    end
    def randomize
       pts = @grid.pts
       @pts = pts[1..-1].sort_by { rand }
       @pts.unshift(pts[0]).push(pts[0])
       rank
       self
    end
    def initialize_copy(original)
       @pts = original.pts.dup
    end
    def length
       len = 0.0
       @pts.each_cons(2) { |p1, p2| len += dist(p1, p2) }
       len
    end
    def inspect
       "#<#{self.class} length=#{length}, pts=#{@pts.inspect}>"
    end
    def to_s
       by_fives = @pts.enum_for(:each_slice, 5)
       "length: %.2f excess: %.2f\%\n" % [length, excess] +
       by_fives.collect do |row|
          row.collect { |pt| pt.inspect }.join('  ')
       end.join("\n")
    end
    def snapshot
       "length: %.2f excess: %.2f\%" % [length, excess]
    end
    # Relative difference between length and minimum length expressed as
    # percentage.
    def excess
       100.0 * (length / grid.min - 1.0)
    end
    def replicate
       replica = dup
       cuts = cut_at
       case cuts.size
       when 2
          replica.reverse(*cuts).rank if cuts[0] + 1 < cuts[1]
       when 3
          replica.exchange(*cuts).rank
       end
       replica
    end
protected
    # Recombination operator: reverse segment running from i to j - 1.
    def reverse(i, j)
       recombine do |len|
          (0...i).to_a + (i...j).to_a.reverse + (j...len).to_a
       end
    end
    # Recombination operator: exchange segment running from i to j - 1
    # with the one running from j to k - 1.
    def exchange(i, j, k)
       recombine do |len|
          (0...i).to_a + (j...k).to_a + (i...j).to_a + (k...len).to_a
       end
    end
    def rank
       @ranking = sum_dist_sq * dist_sq(*@pts.last(2))
       # Alternative fitness function
       # @ranking = sum_dist_sq
       # Alternative fitness function
       # @ranking = length
    end
private
    # Build new points array from list of permuted indexes.
    def recombine
       idxs = yield @pts.length
       @pts = idxs.inject([]) { |pts, i| pts << @pts[i] }
       self
    end
    # Sum of the squares of the distance between successive path points.
    def sum_dist_sq
       sum = 0.0
       @pts.each_cons(2) { |p1, p2| sum += dist_sq(p1, p2) }
       sum
    end
    # Find the points at which to apply the recombiation operators.
    # The argument allows for deterministic testing.
    def cut_at(seed=nil)
       srand(seed) if seed
       cuts = []
       3.times { cuts << 1 + rand(@order) }
       cuts.uniq.sort
    end
    # Square of the distance between points p1 and p2.
    def dist_sq(p1, p2)
       x1, y1 = p1
       x2, y2 = p2
       dx, dy = x2 - x1, y2 - y1
       dx * dx + dy * dy
    end
    # Distance between points p1 and p2.
    def dist(p1, p2)
       Math.sqrt(dist_sq(p1, p2))
    end
end
</code>

Discussion
----------

1. The command line interface implemented in ga_path.rb is fairly  
complex. My GA solver is fairly sensitive to a number of parameters,  
so I feel I need a lot control over its initialization. Also, for  
GAs, I prefer to control termination manually rather than building a  
termination criterion into the solver.

2. If you ignore all the user interface stuff in ga_path.rb, you can  
see that ga_path.rb and ga_solver.rb, taken together, follow the  
pseudocode given in the problem description very closely. Note how  
brutally simple and fully generic ga_solver.rb is -- it knows nothing  
about the problem it is solving. In fact, I originally developed it  
to solve another problem and simply plugged into this one.

3. The fitness function

def rank
    @ranking = sum_dist_sq * dist_sq(*@pts.last(2))
end

implemented in path.rb is perhaps not the obvious one. The extra  
factor of  dist_sq(*@pts.last(2)) adds some selection pressure to  
enhance the survival of paths having short final segments, something  
that is desirable in paths that must return to their starting point.  
I also tried the following, more obvious, fitness functions. These  
also work. My experience is that the one I settled on works somewhat  
better.

def rank
    @ranking = length
end

def rank
    @ranking = sum_dist_sq
end

Regards, Morton