[QUIZ] Itinerary for a Traveling Salesman (#142)

[James_Edward_Gray_II]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

···

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Morton Goldberg

A salesman wants to call on his customers, each of which is located in a
different city. He asks you to prepare an itinerary for him that will minimize
his driving miles. The itinerary must take him to each city exactly once and
return him to his starting point. Can you write a Ruby program to generate such
an itinerary?

This problem is famous and known to be NP-complete. So how can you be expected
to solve it as a weekend Ruby Quiz project? It's unreasonable isn't it? Yes,
it is, unless the conditions are relaxed somewhat.

First, let's restrict the problem to a space for which the solution is known: a
grid of points as defined by the following Ruby code:

  # Square grid (order n**2, where n is an integer > 1). Grid points are
  # spaced on the unit lattice with (0, 0) at the lower left corner and
  # (n-1, n-1) at the upper right.
  
  class Grid
     attr_reader :n, :pts, :min
     def initialize(n)
        raise ArgumentError unless Integer === n && n > 1
        @n = n
        @pts = []
        n.times do |i|
           x = i.to_f
           n.times { |j| @pts << [x, j.to_f] }
        end
        # @min is length of any shortest tour traversing the grid.
        @min = n * n
        @min += Math::sqrt(2.0) - 1 if @n & 1 == 1
     end
  end

Second, let's relax the requirement that the itinerary be truly minimal. Let's
only require that it be nearly minimal, say, within 5%. Now you can tackle the
problem with one of several heuristic optimization algorithms which run in
polynomial time. In particular, you could use a genetic algorithm (GA).

  Genetic Algorithm (GA)

From one point of view a GA is a stochastic technique for solving an
optimization problem--for finding the extremum of a function. From another
point of view it is applied Darwinian evolution.

To see how a GA works, let's look at some pseudocode.

  Step 1. Generate a random initial population of itineraries.
  Step 2. Replicate each itinerary with some variation.
  Step 3. Rank the population according to a fitness function.
  Step 4. Reduce the population to a prescribed size,
           keeping only the best ranking itineraries.
  Step 5. Go to step 2 unless best itinerary meets an exit criterion.

Simple, isn't it? But perhaps some discussion will be useful.

Step 1. You can get the points you need to generate a new random itinerary by
calling *pts* on an instance *grid* of the Grid class shown above.

Step 2. GAs apply what are called *genetic operators* to replicas of the
population to produce variation. Genetic operators are usually referred to by
biological sounding names such *mutation*, *recombination*, or *crossover*.
Recombination means some kind of permutation. In my GA solution of the problem
proposed here, I used two recombination operators, *exchange* and *reverse*.
Exchange means cutting an itinerary at three points (yielding four fragments)
and swapping the middle two fragments. Reverse means cutting an itinerary at
two points (yielding three fragments) and reversing the order of the middle
fragment.

Step 3. The fitness function for the traveling salesman problem can be the
total distance traversed when following an itinerary (including the return to
the starting point), or it can be a related function that reaches its minimum
for exactly the same itineraries as does the total distance function.

A GA can be rather slow, but has the advantage of being easy to implement. My
experience with problem I have proposed is that a GA can produce a solution
meeting the 5% criterion reasonably quickly and that it can find an exact
solution if given enough time.

  An Exact Solution

To give you an idea of how a solution looks when plotted, here is a picture of a
minimal tour on a 7 X 7 grid.

  *--*--*--* *--*--*
  > > > >
  * *--* *--* *--*
  > > > >
  * * *--*--*--* *
  > > / |
  * *--*--*--*--* *
  > >
  *--* *--*--*--* *
     > > > >
  *--* * *--*--* *
  > > > >
  *--*--* *--*--*--*

This exact solution was found by my Ruby GA solver in about two minutes.

  Wikipedia Links

Two Wikipedia pages have a great deal of relevant information on the topic of
this quiz.

  http://en.wikipedia.org/wiki/Traveling_salesman_problem

  http://en.wikipedia.org/wiki/Genetic_algorithm

[Simon_Kroger (Simon Kröger)]

A salesman wants to call on his customers, each of which is located in a
different city. He asks you to prepare an itinerary for him that will minimize
his driving miles. The itinerary must take him to each city exactly once and
return him to his starting point. Can you write a Ruby program to generate such
an itinerary?
[...]

Sorry if i'm just stating the obvious - this quiz isn't about finding a
solution (fast and correct) but to implement the genetic algorithm, right?

I'm just asking myself if i missed a (or maybe the) point...

cheers

Simon

[Eric_Mahurin]

As far as I know, a genetic algorithm isn't going to guarantee any
approximation factor (within 1.05 of optimal as suggested above),
right? To get that kind of guaranteed accuracy level, I think you'd
need to go with Arora's quite complex polynomial-time approximation
scheme, which I have yet to see an implementation of. Personally, I'd
like to see it implemented for the (rectilinear) steiner tree problem
(his techniques work on a whole slew of geometric graph problems).

···

On 10/5/07, Ruby Quiz <james@grayproductions.net> wrote:

Second, let's relax the requirement that the itinerary be truly minimal. Let's
only require that it be nearly minimal, say, within 5%. Now you can tackle the
problem with one of several heuristic optimization algorithms which run in
polynomial time. In particular, you could use a genetic algorithm (GA).

[Eugene_Kalenkovich2 (Eugene Kalenkovich)]

One more variation of GA theme. For mutationsd I use reversals only, with
variable lengths up to 1/2 of trip (+2). Apparently random shift also helps
a lot.
Additional twist to the algorithm, that works only for a limited problem
space (but works well) - population and productivity increase in time
exponentially. I've tried different rates of increase, **1 gives a realy
good speed in lucky cases, but miserable on bad ones. **2 is good, but
decreases speed of lucky ones too much. **1.5 seems to be a good compromise
(I am starting to think that "good enough", being a pragmatic one, should be
a Ruby slogan). I have no mathematical explanation/proof, but can expect
that magic number is either 1.5 or 1.(3)

I believe that result has a good balance between code simplicity and
performance (any volunteers to test performance of different solutions on
cases >7 ?)

require 'enumerator'
require 'grid'

def distance(p1,p2,sqrt=true)
  dist=((p1[0]-p2[0])**2 +(p1[1]-p2[1])**2)
  sqrt ? Math::sqrt(dist) : dist
end

def length(path, sqrt=true)
  len=distance(path[0],path[-1],sqrt)
  path.each_cons(2) {|p1,p2| len+=distance(p1,p2,sqrt)}
  len
end

def mutation(path,i)
  len=path.length
  rev=i%(len/2)+2
  shift=rand(len-1)
  pos=rand(len-rev)
  newpts=path[shift..-1]+path[0...shift]
  newpts[pos,rev]=newpts[pos,rev].reverse
  newpts
end

num,pct=ARGV
num>>=5
pct>>=0
num=num.to_i
pct=pct.to_i

grid=Grid.new(num)
pass=grid.min+grid.min*pct/100.0+0.1
pathset=[grid.pts]
count=0
while (length(pathset[0])>pass) do
  count+=1
  newpaths=[]
  sample=(count**1.5).round
  pathset.each { |path| sample.times {|i| newpaths << mutation(path,i)} }
  pathset=(pathset+newpaths).sort_by { |path|
length(path,false) }.first(sample)
  puts "#{count}. #{length(pathset[0])}"
end
p pathset[0]

[Joseph_Seaton]

I'm afraid my solution is rather late since I spent so much time trying to tweak it.

Nothing special (and very inelegant), but it manages to get a 7*7 grid to within 5% in about 40s (give or take quite a bit):

#!/usr/bin/env ruby
require 'rubygems'
require 'rvg/rvg'
require 'grid'
include Magick

class GeneticGridGuess
  def initialize grid
    @grid, @min = grid.pts, grid.min*1.05
    puts "Minumum time (within 5%): #{@min}"
    @len, @seg = @grid.length, (@grid.length*0.3).ceil
    @psize = Math.sqrt(@len).ceil*60
    @mby = (@psize/20).ceil
    @pop = []
    @psize.times do
      i = @grid.sort_by { rand }
      @pop << [dist(i),i]
    end
    popsort
  end
  def solve
    while iter[0] > @min
      puts @pop[0][0]
    end
    @pop[0]
  end
  def iter
    @pop = (@pop[0..20]*@mby).collect do |e|
      n = e[1].dup
      case rand(10)
      when 0..6 #Guesses concerning these values
        seg = rand(@seg)
        r = rand(@grid.length-seg+1)
        n[r,seg] = n[r,seg].reverse
      when 7
        n = n.slice!(rand(@grid.length)..-1) + n
      when 8..9
        r = []
        3.times { r << rand(@grid.length)}
        r.sort!
        n = n[0...r[0]] + n[r[1]...r[2]] + n[r[0]...r[1]] + n[r[2]..-1]
      end
      [dist(n),n]
    end
    popsort
    @pop[0]
  end
  def dist i
    #Uninteresting but fast as I can make it:
    t = 0
    g = i+[i[0]]
    @len.times do |e|
       t += Math.sqrt((g[e][0]-g[e+1][0])**2+(g[e][1]-g[e+1][1])**2)
    end
    t
  end
  def popsort
    @pop = @pop.sort_by { |e| e[0] }
  end
end

gridsize = ARGV[0] ? ARGV[0].to_i : (print "Grid size: "; STDIN.gets.to_i)
grid = GeneticGridGuess.new(Grid.new(gridsize)).solve

puts "In time #{grid[0]}:"
grid[1].each do |e|
  print "#{e[0].to_i},#{e[1].to_i} "
end
puts

if !ARGV[1]
  RVG.new(gridsize*100,gridsize*100) do |canvas|
    canvas.background_fill = 'white'
    cgrid = grid[1].collect do |e|
      [e[0]*100+10,e[1]*100+10]
    end
    cgrid.each do |point|
      canvas.circle(5,point[0],point[1]).styles(:fill=>'black')
    end
    canvas.polygon(*cgrid.flatten).styles(:stroke=>'black', :stroke_width=>2, :fill=>'none')
  end.draw.display
end

Suggestions very welcome, particularly concerning speed

Joe

[Eric_I2 (Eric I.)]

My solution is split across a few files, so rather than pasting it all
into this posting, I'll offer a link instead:

    http://learnruby.com/examples/ruby-quiz-142.tgz

To run it for a grid of 7x7, say, you'd issue the command:

    ruby find_route.rb 7

Like James Edward Gray's solution, I created a generic GA class that
didn't have any specific coding for routes and grids. And the Route
class has some methods to create routes from other routes that
correspond to various GA operators. But there's also an interface
class that allows the GA class to deal with routes.

I implemented both of the suggested operations -- exchange and
reverse. And I wanted an operation that combined two routes, and so I
used the one that I saw in James Koppel's solution -- partner guided
reorder. I also allow one to specify the relative frequency with
which the various operators are randomly chosen.

And I do keep track of each route's ancestory, to look for possible
patterns as to which operations tended to be the most useful, for use
in tuning the operator frequencies.

Finally, if RMagick is available, it generates a GIF image of the best
route found.

It was interesting to see how easy a GA was to implement given Ruby's
nice set of Array/Enumerable methods. It was a very nice Ruby Quiz as
it sucked me into spending more time on it than I would have liked.

Eric

···

----

Are you interested in on-site Ruby training that uses well-designed,
real-world, hands-on exercises? http://LearnRuby.com

[Morton_Goldberg]

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

[Morton_Goldberg]

I am posting this because I think there may be some interest in seeing a deterministic solution to the quiz problem. This time I include grid.rb because it's a little different from the version given in the quiz description. My change reorders the @pts array. I wanted an ordering that was easier for me to visualize. Actually, this solution would work with the original grid.rb, but some of the method names (bottm, right_side, left_side, top) in path.rb would be rendered misleading.

<code>
#! /usr/bin/env ruby -w
# d_tsp.rb
# DTSP -- Deterministic solution to Traveling Salesman Problem

···

#
# Created by Morton Goldberg on September 23, 2007.

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

require "grid"
require "path"

DEFAULT_N = 5
grid_n = ARGV.shift.to_i
grid_n = DEFAULT_N if grid_n < 2
grid = Grid.new(grid_n)
puts "#{grid_n} x #{grid_n} grid"
puts Path.new(grid)
</code>

<code>
# lib/path.rb
# DTSP -- Deterministic solution to Traveling Salesman Problem
#
# Created by Morton Goldberg on September 23, 2007
#
# Minimal path traversing a grid of points starting from and returning to
# the origin.

require "enumerator"

class Path
    attr_reader :pts, :grid
    def initialize(grid)
       @grid = grid
       @order = grid.n**2
       @pts = []
       bottom
       right_side
       top
       left_side
    end
    def length
       len = 0.0
       @pts.each_cons(2) { |p1, p2| len += dist(p1, p2) }
       len
    end
    def inspect
       "#<#{self.class} #{grid.n} points -- length=#{length}, " \
       "pts=#{@pts.inspect}>"
    end
    def to_s
       iter = @pts.enum_for(:each_slice, 5)
       "length: %.2f excess: %.2f\%\n" % [length, excess] +
       iter.collect do |row|
          row.collect { |pt| pt.inspect }.join(' ')
       end.join("\n")
    end
private
    def bottom
       @pts.concat(grid.pts.first(grid.n))
    end
    def right_side
       1.step(grid.n - 3, 2) { |i| right_u_turn(i) }
    end
    def right_u_turn(i)
       k = 1 + i * grid.n
       @pts.concat(grid.pts[k, grid.n - 1].reverse)
       k += grid.n
       @pts.concat(grid.pts[k, grid.n - 1])
    end
    def top
       if grid.n & 1 == 0
          # For even n, the top is just a run back to the left side.
          @pts.concat(grid.pts.last(grid.n).reverse)
       else
          # For odd n, the run from the right side back to the left side
          # must be corrugated.
          top_2 = grid.pts.last(2 * grid.n - 1)
          upr_top = top_2.last(grid.n).reverse
          low_top = top_2.first(grid.n - 1).reverse
          @pts << low_top.shift << upr_top.shift << low_top.shift
          @pts << upr_top.shift << upr_top.shift
          ((grid.n - 3) / 2).times do
             @pts << low_top.shift << low_top.shift
             @pts << upr_top.shift << upr_top.shift
          end
       end
    end
    def left_side
       (grid.n - 2).downto(1) { |i| @pts << grid.pts[i * grid.n] }
       @pts << grid.pts.first
    end
    # Relative difference between length and minimum length expressed as
    # percentage.
    def excess
       100.0 * (length / grid.min - 1.0)
    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>

<code>
# lib/grid.rb
# DTSP -- Deterministic solution to Traveling Salesman Problem
#
# Created by Morton Goldberg on September 23, 2007

# Square grid (order n**2, where n is an integer > 1). Grid points are
# spaced on the unit lattice with (0, 0) at the lower left corner and
# (n-1, n-1) at the upper right.

class Grid
    attr_reader :n, :pts, :min
    def initialize(n)
       raise ArgumentError unless Integer === n && n > 1
       @n = n
       @pts = []
       n.times do |i|
          y = i.to_f
          n.times { |j| @pts << [j.to_f, y] }
       end
       # @min is length of shortest tour traversing the grid.
       @min = n * n
       @min += Math::sqrt(2.0) - 1 if @n & 1 == 1
    end
end
</code>

Regards, Morton

[James_Edward_Gray_II]

The goal of this quiz was to come up with a good problem to experiment with genetic algorithms on, yes. Morton and I discussed that quite a bit.

However, as you all know by now, I'm not a big restrictions kind of guy. So I suggested Morton lay out the problem and describe the way we think would be fun to solve it.

That leaves the choice of strategy to the solver and we won't take away your keyboard if you don't use a genetic algorithm.

James Edward Gray II

P.S. Of course, if you've been waiting to play with genetic algorithms, this is your chance! I was itching for a good excuse to try one, so that's how I built my solution. This is a good problem for the experiment, I think.

···

On Oct 6, 2007, at 10:55 AM, Simon Kröger wrote:

A salesman wants to call on his customers, each of which is located in a
different city. He asks you to prepare an itinerary for him that will minimize
his driving miles. The itinerary must take him to each city exactly once and
return him to his starting point. Can you write a Ruby program to generate such
an itinerary?
[...]

Sorry if i'm just stating the obvious - this quiz isn't about finding a
solution (fast and correct) but to implement the genetic algorithm, right?

I'm just asking myself if i missed a (or maybe the) point...

[Morton_Goldberg]

It's true that this quiz resulted from James asking for a quiz featuring genetic algorithms, and it's also true that I wish to encourage participants to implement a genetic algorithm. On the other hand, any solution to the problem is certainly welcome. Also, given the restriction to an n x n grid, it _is_ possible to write a fast, exact solution.

Regards, Morton

···

On Oct 6, 2007, at 11:55 AM, Simon Kröger wrote:

A salesman wants to call on his customers, each of which is located in a
different city. He asks you to prepare an itinerary for him that will minimize
his driving miles. The itinerary must take him to each city exactly once and
return him to his starting point. Can you write a Ruby program to generate such
an itinerary?
[...]

Sorry if i'm just stating the obvious - this quiz isn't about finding a
solution (fast and correct) but to implement the genetic algorithm, right?

I'm just asking myself if i missed a (or maybe the) point...

[James_Edward_Gray_II]

Genetic algorithms don't guarantee the solution, that's correct. But it's pretty easy to get one working reasonably well for this.

James Edward Gray II

···

On Oct 6, 2007, at 3:05 PM, Eric Mahurin wrote:

On 10/5/07, Ruby Quiz <james@grayproductions.net> wrote:

Second, let's relax the requirement that the itinerary be truly minimal. Let's
only require that it be nearly minimal, say, within 5%. Now you can tackle the
problem with one of several heuristic optimization algorithms which run in
polynomial time. In particular, you could use a genetic algorithm (GA).

As far as I know, a genetic algorithm isn't going to guarantee any
approximation factor (within 1.05 of optimal as suggested above),
right?

[Morton_Goldberg]

You are correct. For the general shortest tour problem, a genetic algorithm can't guarantee a solution within a specific error bound. I should have been clearer about that.

However, for the grid version of the problem with the grid not too big (say, n x n <= 10 x 10), it is not at all hard to come up with a genetic algorithm that meets the 5% goal. And how many salesmen make trips with more than 100 cities on their itinerary?

I really don't want this quiz to be too hard. I don't expect anyone participating in this quiz to work with really large grids. A solution that can get to within 5% on a 10 x 10 grid is a good one as far as I'm concerned.

Regards, Morton

···

On Oct 6, 2007, at 4:05 PM, Eric Mahurin wrote:

On 10/5/07, Ruby Quiz <james@grayproductions.net> wrote:

Second, let's relax the requirement that the itinerary be truly minimal. Let's
only require that it be nearly minimal, say, within 5%. Now you can tackle the
problem with one of several heuristic optimization algorithms which run in
polynomial time. In particular, you could use a genetic algorithm (GA).

As far as I know, a genetic algorithm isn't going to guarantee any
approximation factor (within 1.05 of optimal as suggested above),
right? To get that kind of guaranteed accuracy level, I think you'd
need to go with Arora's quite complex polynomial-time approximation
scheme, which I have yet to see an implementation of. Personally, I'd
like to see it implemented for the (rectilinear) steiner tree problem
(his techniques work on a whole slew of geometric graph problems).

[Dave_Pederson]

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 = nil, lat = 0.0, lon = 0.0)
      @city = city
      @lat = lat
      @lon = lon
    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.0, fitness_alg = Fitness.new)
      @fitness = fitness
      @fitness_alg = fitness_alg
    end

    def genes(i = 0, j = size)
      ngenes = []
      if (i > -1 && j <= size && j >= i)
        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 = Chromosome.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 = n
      @pts = []
      n.times do |i|
        x = i.to_f
        n.times { |j| @pts << [x, j.to_f] }
      end
      # @min is length of any shortest tour traversing the grid.
      @min = n * n
      @min += Math::sqrt(2.0) - 1 if @n & 1 == 1
      puts "Shortest possible tour = #{@min}"
    end

  end # Grid

  class Genotype

    attr_accessor :grid

    def initialize(grid = Grid.new(5))
      @grid = grid
      @genes = Array.new
      pts = @grid.pts
      for i in 0...pts.length
        pair = pts.shift
        x = pair.shift
        y = pair.shift
        @genes << Gene.new("Node #{i}", x, y)
      end
    end

    def new_rand_chrom
      @genes.replace @genes.sort_by { rand }
      c = Chromosome.new
      @genes.each do |gene|
        c << gene.copy
      end
      c
    end

  end # Genotype

  class Fitness

    def rank(chrom)
      fit = distance(chrom.last, chrom.first)
      i = 0
      while i < chrom.length - 1
        g0 = chrom[i]
        g1 = chrom[i+1]
        fit += distance(g0, g1)
        i += 1
      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 = 0.90
    end

    def crossover(p0, p1)
      children = []
      if rand < @rate
        c0, c1 = Chromosome.new, Chromosome.new
        min = [p0.length, p1.length].min
        index = rand(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 = 0.10
    end

    def mutate!(chrom)
      if rand < @rate
        s = chrom.length - 1
        r1 = rand(s)
        r2 = rand(s)
        while r1 == r2
          r2 = rand(s)
        end
        min = [r1, r2].min
        max = [r1, r2].max
        while max > min
          chrom[min], chrom[max] = chrom[max], chrom[min]
          max -= 1
          min += 1
        end
      end
    end

  end # Mutator

  class Population < Array

    attr_accessor :genotype, :crossover, :mutator, :offspring

    def initialize(genotype = Genotype.new, crossover = Crossover.new,
mutator = Mutator.new)
      @genotype = genotype
      @crossover = crossover
      @mutator = mutator
    end

    def prepare(size = 100, initial_size = 1000, offspring = 80)
      @offspring = offspring
      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 = select_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 = self)
      list.replace list.sort_by { |chrom| chrom.fitness }
    end

    def select_parents
      parents = []
      s = size
      r1, r2 = rand(s), rand(s)
      while r1 == r2
        r2 = rand(s)
      end
      parents << self[r1]
      parents << self[r2]
      parents
    end

  end # Population

end # RubyGa

if __FILE__ == $0

  include RubyGa

  s = Time.now
  puts "Genetic algorithm started at #{s}"
  p = Population.new
  p.prepare(20, 100, 15)
  best_so_far = p.first.fitness
  gen = 1
  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 = p.first.fitness
    end
    gen += 1
  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

[steve]

just wanted to link to a few of the animations from my solution

http://rn86.net/~stevedp/trips7.svg <http://rn86.net/~stevedp/trips7.svg>
http://rn86.net/~stevedp/trips8.svg <http://rn86.net/~stevedp/trips8.svg>
http://rn86.net/~stevedp/trips15.svg<http://rn86.net/~stevedp/trips15.svg>

the 15x15 one is kinda fun

- steve

[Arthur_Chan]

I think it is a super useful post for me, as I am finding TSP solution
in Ruby!

Anyway, I've looked at the codes, it's related to the grid mentioned.
Sorry for my lack of knowledge in Math. My problem is finding the
shortest path among cities in my website, is it possible to apply the
grid algorithm?

Thanks much!

···

--
Posted via http://www.ruby-forum.com/.

[James_Edward_Gray_II]

Hi all-

Hi Dave.

This is my first quiz.

I did forward your first message to the list, but I'm glad to see you decided to join us.

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.

Some thoughts:

     def copy
       Gene.new(@city, @lat, @lon)
     end

All objects include a dup() method that would be equivalent to this.

For:

     def eql?(gene)
       self == gene
     end

Or just:

   alias_method :eql?, :==

With:

     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

This is a light suggestion, but we tend to do as few type checks as possible in Ruby. You may have a reason for doing it here, but most of the time we find that leaving them out gives us more options.

Those are just some general points I saw. Overall, it's a nice solution. Thanks for sharing.

James Edward Gray II

···

On Oct 7, 2007, at 4:30 PM, Dave Pederson wrote:

[Martin_DeMello]

The 'pretty' way to do this: [gene.class, gene.city, gene.lat,
gene.long] == [self.class, @city, @lat, @long]

Introduces a bit of overhead due to the temp array creation, so you
probably want to benchmark when doing this in an inner loop.

martin

···

On 10/7/07, Dave Pederson <dave.pederson.ruby@gmail.com> wrote:

    def ==(gene)
      gene.class == self.class &&
      @city == gene.city &&
      @lat == gene.lat &&
      @lon == gene.lon
    end

[James_Edward_Gray_II]

That's quite interesting.

I noticed the iteration count keeps climbing a little after it settles on a solution. Is it still looking for something better?

James Edward Gray II

···

On Oct 10, 2007, at 1:35 AM, steve wrote:

just wanted to link to a few of the animations from my solution

http://rn86.net/~stevedp/trips7.svg <http://rn86.net/~stevedp/trips7.svg&gt;
http://rn86.net/~stevedp/trips8.svg <http://rn86.net/~stevedp/trips8.svg&gt;
http://rn86.net/~stevedp/trips15.svg&lt;http://rn86.net/~stevedp/trips15.svg&gt;

[Steve_Ross]

I'd like to be optimistic, but this is not a problem that has satisfactorily solved. Excerpt:

···

--------
This lack of improvement in TSP guarantees may be something we cannot avoid; with current models of computing it may well be that there simply is no solution method for the TSP that comes with an attractive performance guarantee, say one of the form n**c for some fixed number c, that is, n x n x n ... x n, where n appears c times in the product. A technical discussion of this issue can be found in Stephen Cook's paper and the Clay Mathematics Institute offers a $1,000,000 prize for anyone who can settle it.[1]

--------

So it's unlikely you will type it into Google and get pithy Ruby solution to a problem that's been around since I was taking CS and that was forever ago. The problem is not that you can't solve it for a small number of cities using reduction ad absurdum; it's that the solution does not scale to larger numbers of cities.

[1]http://www.tsp.gatech.edu/methods/progress/progress.htm

On Apr 27, 2009, at 6:03 AM, Arthur Chan wrote:

I think it is a super useful post for me, as I am finding TSP solution
in Ruby!

Anyway, I've looked at the codes, it's related to the grid mentioned.
Sorry for my lack of knowledge in Math. My problem is finding the
shortest path among cities in my website, is it possible to apply the
grid algorithm?

Thanks much!
--
Posted via http://www.ruby-forum.com/\.

[Rick_DeNatale1 (Rick DeNatale)]

More abstractly, it is well known to be in the class of NP-complete problems:

NP-completeness

···

On Mon, Apr 27, 2009 at 9:45 PM, s.ross <cwdinfo@gmail.com> wrote:

I'd like to be optimistic, but this is not a problem that has satisfactorily
solved.

--
Rick DeNatale

Blog: http://talklikeaduck.denhaven2.com/
Twitter: http://twitter.com/RickDeNatale
WWR: http://www.workingwithrails.com/person/9021-rick-denatale
LinkedIn: http://www.linkedin.com/in/rickdenatale