# Itinerary for a Traveling Salesman (#142)

The three rules of Ruby Q.:

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 Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
message,
if you can.

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

by Morton G.

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 Q. 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:

# (n-1, n-1) at the upper right.

class Grid
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
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.

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

Travelling salesman problem - Wikipedia

Genetic algorithm - Wikipedia

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

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

[…]

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…

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 G. 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 11:55 AM, Simon Kröger wrote:

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…

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 3:05 PM, Eric M. wrote:

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 G. II

On 10/5/07, Ruby Q. [email protected] 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).

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

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

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

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

Since I am very new to ruby (been at it in my spare time now for
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 G. II

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

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]

On 10/7/07, Dave P. [email protected] wrote:

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

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.min1.05
puts “Minumum time (within 5%): #{@min}”
@len, @seg = @grid.length, (@grid.length
0.3).ceil
@psize = Math.sqrt(@len).ceil60
@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(gridsize100,gridsize100) 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

My solution is split across a few files, so rather than pasting it all

``````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 G.'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 K.'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 Q. 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

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.

``` #! /usr/bin/env ruby -w # ga_path.rb # GA_Path # # Created by Morton G. 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 lib/ga_solver.rb>

# solver – it knows nothing about the problem it is solving.

class GASolver
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 lib/path.rb>

origin.

# the grid using a GA solver.

require “enumerator”

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

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

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

the 15x15 one is kinda fun

• steve

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

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

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 G. II

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

``` #! /usr/bin/env ruby -w # d_tsp.rb # DTSP -- Deterministic solution to Traveling Salesman Problem # # Created by Morton G. 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) ``` ``` # lib/path.rb # DTSP -- Deterministic solution to Traveling Salesman Problem # # Created by Morton G. 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 ``` ``` # lib/grid.rb # DTSP -- Deterministic solution to Traveling Salesman Problem # # Created by Morton G. 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 ```

Regards, Morton

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.

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!

On Mon, Apr 27, 2009 at 9:45 PM, s.ross [email protected] wrote:

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:

Rick DeNatale