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

First, before I get to my main solution, I would like to show that, as
Morton pointed out, yes, it is very possible to have a quick, exact
solution. Here’s one that does so for N >= 3 (N=2 and N=1 nevertheless
draw correctly; a call to uniq would make them work).

require ‘RMagick’
require ‘enumerator’

<definitions of Grid and draw_itin removed - see main solution below>

n = ARGV[0].to_i

itin = ([0]*n).zip((0…n).to_a)

1.step(n-3, 2) do |x|
itin += ([x](n-1)).zip((1…n).to_a.reverse)
itin += ([x+1]
(n-1)).zip((1…n).to_a)
end

if n%2==0
itin += ([n-1]*(n-1)).zip((0…n).to_a.reverse)
else
(n-1)…step(2, -2) do |y|
itin += [[n-2,y],[n-1,y],[n-1,y-1],[n-2,y-1]]
end
end

itin += (0…n).to_a.reverse.zip([0]*n)

\$grid = Grid.new(n) #Because draw_itin asks for it
draw_itin(itin, “#{n}x#{n}tour2.jpg”)

However, not being one to run from a fun problem, my main solution does
implement a genetic algorithm. While I did use the reverse_segment and
adjacent_segment_swap recombinators described in the quiz, I also used a
good variety of other asexual (i.e.: one parent) and sexual (i.e…: two
parents) recombinators.

Unfortunately, and as might be expected, my solution has a wide variety
in speed. I’ve seen the time to evolve a 6x6 tour range from under 500
generations to tens of thousands of generations. At first I wondered
whether the two sexual recombinators and element_swap were reducing
variability too much, but commenting them out of the RECOMBINATORS array
didn’t seem to help;

Anyway, here’s the code:

require ‘enumerator’
require ‘RMagick’

DESIRED_FITNESS = 1.05
GENERATION_SIZE = 30

# (n-1, n-1) at the upper right.

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

class Array
def conses(size)
conses = []
each_cons(size) do |cns|
conses << cns
end
conses
end
end

def rand_sorted_nums(n, max)
([nil]*n).map{rand(max)}.sort
end

###Asexual recombinators

##The ‘exchange’ recombinator mentioned in the quiz description.
##Splits itinerary into four segments based on three points and swaps
the middles
i1,i2,i3 = rand_sorted_nums(3, itin.length)
itin[0…i1] + itin[i2…i3] + itin[i1…i2] + itin[(i3+1)…-1]
end

##Like adjacent_segment_swap, but splits into 5 segments and swaps 2 and
4
i1,i2,i3,i4 = rand_sorted_nums(4, itin.length)
i1,i2,i3,i4 = rand_sorted_nums(4, itin.length) until i2 != i3
itin[0…i1] + itin[i3…i4] + itin[(i2+1)…i3] + itin[i1…i2] +
itin[(i4+1)…-1]
end

##The reverse recombinator mentioned in the quiz description
##Splits itinerary into three segments based on two points;
##reverses the nodes in the middle
def reverse_segment(itin)
i1,i2 = rand_sorted_nums(2, itin.length)
itin[0…i1] + itin[i1…i2].reverse + itin[(i2+1)…-1]
end

##Simply swaps a random two nodes
def element_swap(itin)
i1, i2 = rand_sorted_nums(2, itin.length)
itin_chld = itin.dup
itin_chld[i1], itin_chld[i2] = itin_chld[i2], itin_chld[i1]
itin_chld
end

##Splits into three segments based on two points.
##Every adjacent pair in the middle segment is swapped. E.g.:
[a,b,c,d,e] -> [b,a,d,c,e]
i1,i2 = rand_sorted_nums(2, itin.length)
itin_chld = itin[0…i1]
itin[i1…i2].each_slice(2) do |a,b|
itin_chld += [b,a].compact
end
itin_chld + itin[(i2+1)…-1]
end

###Sexual recombinators

##Described in Wikipedia’s article on crossovers in genetic algorithms
##Splits female into three segments based on two points. Reorders middle
according
##to the order of the nodes in the male
def partner_guided_reorder(itinf, itinm)
i1,i2 = rand_sorted_nums(2, itinf.length)
itinf[0…i1] +
itinf[i1…i2].sort_by{|el| itinm.index(el)} +
itinf[(i2+1)…-1]
end

##Identifies segments of the male itinerary (genes) that are maximally
fit.
##Reorders the corresponding nodes in the female to match
def fit_gene_exchange(itinf, itinm)
gene_length = rand(Math.sqrt(\$grid.n).floor) + 1
return itinf if 2…(\$grid.pts.length) === gene_length
genes = []
itinm.each_cons(gene_length) do |cns|
genes << cns
end
genes.map! {|gene| [total_driving_distance(gene), gene]}
genes.sort!

itin_chld = itinf.dup
genes.each do |(dist, gene)|
break if dist > gene_length
break if rand(10) == 0

``````gene[1..-1].each do |node|
itin_chld.slice!(itin_chld..index(node))
end
p [gene_length, gene]
itin_chld[itin_chld.index(gene.first)] = gene
``````

end
itin_chld
end

:reverse_segment,
:element_swap,
:partner_guided_reorder,
:fit_gene_exchange,
].map{|sym| method(sym)}

###End of genetic recombinators

def total_driving_distance(itin)
itin.conses(2).inject(0) {|dist, ((x1,y1),(x2,y2))|
dist+Math.sqrt(((y2-y1)**2)+((x2-x1)**2))}
end

def fitness(itin)
point
end

def next_generation(parents, target_size)
(parents * (target_size / parents.length + 1))[0…target_size].map do
|par|
recom = RECOMBINATORS[rand(RECOMBINATORS.size)]
if recom.arity == 1
recom.call(par)
else
recom.call(par,parents[rand(parents.size)])
end
end
end

def genetic_search(initial_population)
pop = initial_population
until fitness(pop.first) <= \$grid.min * DESIRED_FITNESS
pop = next_generation(pop, GENERATION_SIZE * 3).
sort_by{|itin| fitness(itin)}[0…GENERATION_SIZE]
end
pop.first
end

SPACING = 50
BORDER = 20
def draw_itin(itin, filename)
dim = (\$grid.n-1)*SPACING + BORDER * 2
canvas = Magick::Image.new(dim, dim)
gc = Magick::Draw.new
gc.stroke(‘black’)
gc.stroke_width(1)

\$grid.pts.each do |(x,y)|
gc.circle([x,y,x+3.0/SPACING, y].map{|c|cSPACING+BORDER})
end
(itin+[itin.first]).each_cons(2) do |((x1,y1),(x2,y2))|
gc.line([x1,y1,x2,y2].map{|c|cSPACING+BORDER})
end
gc.draw(canvas)
canvas.write(filename)
end

n = ARGV[0].to_i
\$grid = Grid.new(n)
init_pop = next_generation([\$grid.pts] * GENERATION_SIZE,
GENERATION_SIZE)
draw_itin(genetic_search(init_pop), “#{n}x#{n}tour.jpg”)

On Oct 7, 2007, at 9:20 AM, James K. wrote:

n = ARGV[0].to_i
else
(n-1)…step(2, -2) do |y|
itin += [[n-2,y],[n-1,y],[n-1,y-1],[n-2,y-1]]
end
end

itin += (0…n).to_a.reverse.zip([0]*n)

\$grid = Grid.new(n) #Because draw_itin asks for it
draw_itin(itin, “#{n}x#{n}tour2.jpg”)

I believe there’s a typo in the above. Shouldn’t it be:

(n-1).step(2, -2) do |y| # I removed a .

?

James Edward G. II