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

[Ruby Quiz]

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, ts, :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 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

 

[James Edward Gray II]

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

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

right?

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

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

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

That leaves the choice of strategy to the solver and we won't take =20
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 =20
algorithms, this is your chance! I was itching for a good excuse to =20
try one, so that's how I built my solution. This is a good problem =20
for the experiment, I think.

 

[Morton Goldberg]

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

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

right?

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

It's true that this quiz resulted from James asking for a quiz =20
featuring genetic algorithms, and it's also true that I wish to =20
encourage participants to implement a genetic algorithm. On the other =20=

hand, any solution to the problem is certainly welcome. Also, given =20
the restriction to an n x n grid, it _is_ possible to write a fast, =20
exact solution.

Regards, Morton=

 

[Eric Mahurin]

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

 

[James Edward Gray II]

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?

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

 

[Morton Goldberg]

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

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

 

[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 == chrom
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

 

[Martin DeMello]

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

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

 

[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]).stylesfill=>'black')
end
canvas.polygon(*cgrid.flatten).stylesstroke=>'black',
:stroke_width=>2, :fill=>'none')
end.draw.display
end

Suggestions very welcome, particularly concerning speed

Joe

 

[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

 

[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.enqfeedback)
when ?r
@cmd_queue.enqreport)
when ?q
@cmd_queue.enqquit)
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, ts, :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_foreach_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 }
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

 

[James Edward Gray II]

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>

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

 

[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 ts, :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_foreach_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, ts, :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

 

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

 

[s.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

 

[Rick DeNatale]

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

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

http://en.wikipedia.org/wiki/NP-complete

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