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
on Ruby T. follow the discussion. Please reply to the original quiz
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:

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

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

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? :slight_smile:

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
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 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) :slight_smile:

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

lib/ga_solver.rb

GA_Path

Created by Morton G. 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 lib/path.rb>

lib/path.rb

GA_Path

Created by Morton G. 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

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

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.svghttp://rn86.net/~stevedp/trips15.svg

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

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 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
rendered misleading.

#! /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.

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

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:

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

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs