# Itinerary for a Traveling Salesman (#142)

**URL:** <https://www.ruby-forum.com/t/itinerary-for-a-traveling-salesman-142/229146>\
**Category:** Ruby\
**Created:** [October 11, 2007, 2:12pm UTC](https://www.ruby-forum.com/t/itinerary-for-a-traveling-salesman-142/229146 "2007-10-11T14:12:55Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [October 11, 2007, 2:12pm UTC](https://www.ruby-forum.com/t/itinerary-for-a-traveling-salesman-142/229146/1 "2007-10-11T14:12:55Z")

</div>

This time, we tried to put the focus on how you solved the quiz, instead  
of the  
solution itself. A great aspect of genetic algorithms is that you  
really don’t  
need to know much about the problem domain in order to find a workable  
solution  
for it. That comes with tradeoffs though, naturally. It takes longer  
to find a  
solution this way and there are no guarantees it will be great when you  
do  
settle on something. Still, I think it’s very valuable to examine just  
how  
these solutions work.

I’m going to show Joseph Seaton’s code here. It’s smaller than many of  
the  
solutions submitted, but still quite approachable. It finds good  
answers pretty  
quickly on my box.

Here’s how the code begins:

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

# …

When I first read the requires for this script, I didn’t know what rvg  
was. I  
went searching for the library I needed to install and couldn’t easily  
find one.  
For those that don’t know, rvg is a feature of RMagick that provides you  
with  
vector-based drawing tools. If you have an up-to-date RMagick install,  
you have  
rvg as well.

The constructor in this code should be pretty easy to digest. It pulls  
the  
point list and minimum path for a passed Grid, careful to increase the  
minimum  
to our looser goal. It also pulls the Grid.length() and uses that to  
build a  
size for mutated segments. The @psize holds the population size our  
selections  
will be made from and @mby (for “multiply by,” I assume) is a multiplier  
used in  
the reproduction process. The rest of the code here just builds the  
initial  
population from random sorts of the points.

Next, let’s have a peek at the two helper methods used above:

# …

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

# …

The dist() method provides a standard Euclidean Distance measure and  
popsort()  
just sorts the current population by this measure. The thing to note  
here is  
that the population is always stored as a dist(), followed by the path.  
This  
prevents needing to recalculate the dist() multiple times.

The final two methods of this class do the real work in the solution:

# …

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  
end

# …

The solve() method drives the process, continuing the search until a  
solution  
drops below our minimum accepted fitness measure. Many solutions also  
used time  
as a cut-off factor and I would recommend that approach. Genetic  
algorithms  
don’t guarantee a solution and even when they do find one it could take  
quite  
some time.

The iter() method moves the population forward one generation. The  
process is  
simple: select the best 20 members of the current population, multiply  
that set  
by some factor, mutate each member of the expanded set in some way, and  
save the  
result as our new population. The population is then resorted and the  
best  
returned.

I believe there’s a small error in that code. Since the whole  
population is  
mutated, it is possible that a better solution could be discarded and  
replaced  
by inferior solutions. The code should probably also save the best  
solution  
seen thus far, just in case.

The mutations are largely from the quiz description. 70% of the time a  
reverse  
mutation is performed and 20% of the time an exchange mutation. 10% of  
the  
time, a variation of the exchange is used where just two random segments  
are  
traded.

These are all asexual mutations, but some did try crossovers. An  
ordered  
crossover works pretty well in this case. With that approach you select  
two  
parents, pick a crossover point in the path, and build two offspring  
from  
transforms around that point. The first child has the points of the  
first  
parent up to the crossover point, but the later points are reordered to  
match  
the second parent. This is reversed in the second child.

With the framework in place, we’re ready to see the application code:

# …

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

# …

The first line of this code pulls the grid size from a command-line  
argument or  
STDIN. The second line builds the Grid, creates the solver, and puts it  
to  
work. The rest of the code just prints the points of the best solution.

Though that’s enough to give us some boring numerical output, Joseph  
also had  
code to draw pretty pictures:

# …

if !ARGV[1]  
image = 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]).styles(:fill=\>‘black’)  
end  
canvas.polygon(\*cgrid.flatten).  
styles(:stroke=\>‘black’, :stroke\_width=\>2, :fill=\>‘none’)  
end.draw  
image.display rescue image.write("#{gridsize}x#{gridsize}tour.jpg")  
end

I made a small change in this code so it would draw the picture to disk  
when the  
X Window library needed for display is not available.

This code is run if a second command-line argument is not given to  
disable it.  
It works by creating a canvas, plotting each point in the path on that  
canvas,  
and finally adding a polygon to represent the path found by the solver.  
As you  
can see, RMagick’s RVG class simplifies the shape drawing quite a bit.

My thanks to all the geneticists brave enough to share your Frankenstein  
creations with the rest of us.

Tomorrow we will try generating search results instead of travel  
plans…