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

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

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [October 7, 2007, 4:21pm UTC](https://www.ruby-forum.com/t/re-itinerary-for-a-traveling-salesman-142/116582/1 "2007-10-07T16:21:02Z")

</div>

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

# Square grid (order n\*\*2, where n is an integer \> 1). Grid points are

# spaced on the unit lattice with (0, 0) at the lower left corner and

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

class Grid  
attr\_reader :n, :pts, :min  
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  
def adjacent\_segment\_swap(itin)  
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  
def nonadjacent\_segment\_swap(itin)  
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]  
def adjacent\_el\_swap(itin)  
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

RECOMBINATORS = [:adjacent\_segment\_swap,  
:nonadjacent\_segment\_swap,  
:reverse\_segment,  
:element\_swap,  
:adjacent\_el\_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)  
total\_driving\_distance(itin + [itin.first]) #Must return to starting  
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|c_SPACING+BORDER})  
end  
(itin+[itin.first]).each\_cons(2) do |((x1,y1),(x2,y2))|  
gc.line(_[x1,y1,x2,y2].map{|c|c_SPACING+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”)

---

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [October 7, 2007, 7:29pm UTC](https://www.ruby-forum.com/t/re-itinerary-for-a-traveling-salesman-142/116582/2 "2007-10-07T19:29:29Z")

</div>

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