From: Ruby Quiz <james@...>
Date: 2007-10-11T21:12:07+09:00
Subject: [SUMMARY] Itinerary for a Traveling Salesman (#142)

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