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|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”)