Re: Itinerary for a Traveling Salesman (#142)

Ruby
#1

Hi all,

You can find my solution here: http://rn86.net/~stevedp/salesman.tar.gz

For this quiz I pretty much just implemented the GA described in the
problem: exchanging and reversing. I pick random indexes in the array
of points to decide where to split them before doing these operations.
Then I rank by distance and keep the shortest 15 and longest 5 and then
run another generation. I played around with ranking by number of
diagonals as well since, for a grid, the best solution will always have
either 0 or 1 diagonals but this didn’t seem to help at all. My
solution seems to get w/in 5% of the perfect solution for most grid
sizes w/in 100 generations.

One thing my solution does is create an SVG animation (scalable vector
graphic) of the evolution of the solution. I’ve included ruby-svg with
my solution so you don’t need to install anything. I’ve included with
my solution, an already made SVG (trips15.svg) of a 15x15 grid being
solved over 500 generations to w/in 3.2% of the optimal solution. You
might need to use Firefox for the SVGs to animate, I haven’t tried them
in IE.

To run my solution just unzip all the files and:
ruby travel_agency.rb <grid_size> <# of generations to run>
eg:
ruby travel_agency.rb 7 50

  • steve
#2

On Oct 7, 2007, at 8:33 AM, steve d wrote:

You can find my solution here: http://rn86.net/~stevedp/
salesman.tar.gz

Here’s the genetic algorithm I put together to solve it:

#!/usr/bin/env ruby -wKU

require “grid”

require “enumerator”

class GAPath
def self.random(points)
new(points.sort_by { rand })
end

def initialize(points)
@points = points
end

attr_reader :points

def fitness
@fitness ||=
(@points + [@points.first]).enum_cons(2).inject(0) do |sum,
(p1, p2)|
dx, dy = (p1.first - p2.first).abs, (p1.last - p2.last).abs
sum += Math.sqrt(dx * dx + dy * dy)
end
end

def breed(other)
crossover = rand(@points.size - 2) + 1
[ self.class.new( @points[0…crossover] +
(other.points - @points[0…crossover])),
self.class.new( other.points[0…crossover] +
(@points - other.points[0…crossover])) ]
end

def mutate
new_points = @points.dup
i1 = rand(new_points.size)
i2 = nil
loop do
i2 = rand(new_points.size)
break if i1 != i2
end
new_points[i1], new_points[i2] = new_points[i2], new_points[i1]
self.class.new(new_points)
end
end

class GAAlgorithmSolver
def initialize(population)
@population = population
@size = @population.size / 2
select
end

attr_reader :most_fit

def step
evolve
select
end

private

def select
@population = @population.sort_by { |c| c.fitness }
new_population = [@population.first]
@population = @population[1…-1]
chances = @population.enum_for(:each_index).
map { |i| @population.size - i }
total_chances = chances.inject(0) { |sum, c| sum + c }

 (@size - 1).times do
   selection = rand(total_chances) + 1
   chances.each_with_index do |chance, i|
     if selection <= chance
       new_population << @population.delete_at(i)
       chances.delete_at(i)
       total_chances -= chance
       break
     else
       selection -= chance
     end
   end
 end

 @population = new_population
 @most_fit   = @population.first

end

def evolve
@population +=
@population.enum_cons(2).map { |p1, p2| p1.breed(p2) }.flatten +
@population.map { |p| p.mutate }
end
end

if FILE == $PROGRAM_NAME
grid = Grid.new(ARGV.shift.to_i)
rescue abort(“Usage: #{File.basename($PROGRAM_NAME)} GRID_SIZE”)
solver =
GAAlgorithmSolver.new(Array.new(grid.n**2) { GAPath.random
(grid.pts) })

start = last = Time.now
off_by = 100
until off_by == 0 or Time.now - start > 60
off_by = 100 * (solver.most_fit.fitness / grid.min - 1)
solver.step
if Time.now - last >= 2
printf “Within %.2f%% with %d seconds left to search…\n”,
off_by, 60 - (Time.now - start)
last = Time.now
end
end

puts “Best path found has a length of #{solver.most_fit.fitness}.”
printf “This is %.2f%% off of the optimal solution.\n”, off_by
puts “The path is:”
solver.most_fit.points.enum_slice(5).inject(String.new) do |
output, row|
“#{output} #{row.inspect[1…-2]}\n”
end.sub(/\A /, “[”).sub(/\Z/, " ]").display

end

END

James Edward G. II