# Re: Itinerary for a Traveling Salesman (#142)

**URL:** <https://www.ruby-forum.com/t/re-itinerary-for-a-traveling-salesman-142/116574>\
**Category:** Ruby\
**Created:** [October 7, 2007, 3:34pm UTC](https://www.ruby-forum.com/t/re-itinerary-for-a-traveling-salesman-142/116574 "2007-10-07T15:34:07Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![steve\_d](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/ce73a5/32.png) [@steve\_d](https://www.ruby-forum.com/u/steve_d)\
**Post date:** [October 7, 2007, 3:34pm UTC](https://www.ruby-forum.com/t/re-itinerary-for-a-traveling-salesman-142/116574/1 "2007-10-07T15:34:07Z")

</div>

Hi all,

You can find my solution here: [http://rn86.net/~stevedp/salesman.tar.gz](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

---

<div class="post-metadata">

**Author:** ![steve\_d](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/ce73a5/32.png) [@steve\_d](https://www.ruby-forum.com/u/steve_d)\
**Post date:** [October 7, 2007, 7:19pm UTC](https://www.ruby-forum.com/t/re-itinerary-for-a-traveling-salesman-142/116574/2 "2007-10-07T19:19:31Z")

</div>

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

> You can find my solution here: [http://rn86.net/~stevedp/](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