On Oct 7, 2007, at 8:33 AM, steve d wrote:
You can find my solution here: http://rn86.net/~stevedp/
salesman.tar.gz
Here’s the genetic algorithm I put together to solve it:
#!/usr/bin/env ruby -wKU
require “grid”
require “enumerator”
class GAPath
def self.random(points)
new(points.sort_by { rand })
end
def initialize(points)
@points = points
end
attr_reader :points
def fitness
@fitness ||=
(@points + [@points.first]).enum_cons(2).inject(0) do |sum,
(p1, p2)|
dx, dy = (p1.first - p2.first).abs, (p1.last - p2.last).abs
sum += Math.sqrt(dx * dx + dy * dy)
end
end
def breed(other)
crossover = rand(@points.size - 2) + 1
[ self.class.new( @points[0…crossover] +
(other.points - @points[0…crossover])),
self.class.new( other.points[0…crossover] +
(@points - other.points[0…crossover])) ]
end
def mutate
new_points = @points.dup
i1 = rand(new_points.size)
i2 = nil
loop do
i2 = rand(new_points.size)
break if i1 != i2
end
new_points[i1], new_points[i2] = new_points[i2], new_points[i1]
self.class.new(new_points)
end
end
class GAAlgorithmSolver
def initialize(population)
@population = population
@size = @population.size / 2
select
end
attr_reader :most_fit
def step
evolve
select
end
private
def select
@population = @population.sort_by { |c| c.fitness }
new_population = [@population.first]
@population = @population[1…-1]
chances = @population.enum_for(:each_index).
map { |i| @population.size - i }
total_chances = chances.inject(0) { |sum, c| sum + c }
(@size - 1).times do
selection = rand(total_chances) + 1
chances.each_with_index do |chance, i|
if selection <= chance
new_population << @population.delete_at(i)
chances.delete_at(i)
total_chances -= chance
break
else
selection -= chance
end
end
end
@population = new_population
@most_fit = @population.first
end
def evolve
@population +=
@population.enum_cons(2).map { |p1, p2| p1.breed(p2) }.flatten +
@population.map { |p| p.mutate }
end
end
if FILE == $PROGRAM_NAME
grid = Grid.new(ARGV.shift.to_i)
rescue abort(“Usage: #{File.basename($PROGRAM_NAME)} GRID_SIZE”)
solver =
GAAlgorithmSolver.new(Array.new(grid.n**2) { GAPath.random
(grid.pts) })
start = last = Time.now
off_by = 100
until off_by == 0 or Time.now - start > 60
off_by = 100 * (solver.most_fit.fitness / grid.min - 1)
solver.step
if Time.now - last >= 2
printf “Within %.2f%% with %d seconds left to search…\n”,
off_by, 60 - (Time.now - start)
last = Time.now
end
end
puts “Best path found has a length of #{solver.most_fit.fitness}.”
printf “This is %.2f%% off of the optimal solution.\n”, off_by
puts “The path is:”
solver.most_fit.points.enum_slice(5).inject(String.new) do |
output, row|
“#{output} #{row.inspect[1…-2]}\n”
end.sub(/\A /, “[”).sub(/\Z/, " ]").display
end
END
James Edward G. II