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