module RubyLabs
=begin rdoc
== TSPLab
The TSPLab module has definitions of classes and methods used in the projects for Chapter 12
of Explorations in Computing. The experiments in this chapter are on the Traveling
Salesman Problem and techniques for solving it with a genetic algorithm. A class called Map
implements a symmetric matrix to represent driving distances, and a class called Tour
represents paths that connect every point on a map. In the genetic algorithm, a "population"
is simply an array of Tour objects, and methods gradually evolve a solution by throwing out
high cost tours and replacing them with new tours that are slight variations of the survivors.
=end
module TSPLab
require 'set'
require "permute.rb"
MapView = Struct.new(:cities, :nodes, :links, :labels, :histogram, :options)
ItemWithDirection = Struct.new(:value, :direction)
# An ItemWithDirection is a struct with two fields, a numeric value and a character that
# represents right or left, used by the Johnson-Trotter algorithm that generates permutations
# of points on a map.
class ItemWithDirection
def inspect # :nodoc:
(self.direction ? "<" : ">") + self.value.inspect
end
end
=begin rdoc
== Map
A Map is a 2D array of distances between pairs of cities. Use the index operator to
look up the distance between two points. For example, given a Map object +m+,
call m[i,j] to find the distance between cities +i+ and
+j+. Indices +i+ and +j+ can be symbols or integers.
=end
class Map
# Create a new Map object. If the argument is an integer +n+, make a map with +n+
# cities at random locations (see the method make_random_map for a description of
# how the cities are chosen). If the argument is a symbol, read a file with that
# name from the TSPLab data directory. If the argument is a string, look for a file
# with that name in the current directory.
#
# Example:
# >> m = Map.new(10)
# => #
# >> m = Map.new(:ireland)
# => #
def initialize(arg)
@labels = Array.new
@dist = Array.new
@coords = Array.new
if arg.class == String || arg.class == Symbol
read_file(arg)
elsif arg.class == Fixnum
make_random_map(arg)
# elsif arg.class == Array
# make_map(arg)
else
raise "Map.new: parameter must be a symbol, a file name, or an integer"
end
end
# Generate a string that lists the cities in this map object.
def inspect
sprintf "#", @labels.join(",")
end
alias to_s inspect
# Print the complete set of driving distances in the map in the form of a
# symmetric matrix. The argument is the field width (number
# of chars in each matrix entry). If no argument is passed, the method uses the
# number of letters in the longest city name as the field width.
#
# Example:
# >> m = Map.new(:ireland)
# => #
# >> m.display
# belfast cork dublin galway limerick
# belfast 0.00
# cork 425.00 0.00
# dublin 167.00 257.00 0.00
# galway 306.00 209.00 219.00 0.00
# limerick 323.00 105.00 198.00 105.00 0.00
def display(fw = nil)
if fw.nil?
lw = labels.inject(0) { |max, x| n = x.to_s.length; (n > max) ? n : max }
dw = (log10(@maxdist).ceil+4)
fw = max(lw+1,dw)
end
res = " " * fw
@labels.each { |name| res << sprintf("%#{fw-1}s ", name.to_s[0..fw-1]) }
res += "\n"
@dist.each_with_index do |a,i|
res += sprintf("%#{fw-1}s ", @labels[i].to_s[0..fw-1])
a.each { |x| res += (x.nil? ? " -- " : sprintf("%#{fw}.2f", x)) }
res += "\n"
end
puts res
end
# Creat a new Tour object that represents a path that connects cities
# in this map. If the argument is an array of city names, the tour will include
# just these cities, in the order they are given (the array does not have to include
# all the cities). If the method is called without any arguments it returns a tour
# that contains all the cities in the order in which they were defined. The third
# situation is to pass a symbol as the first argument in the call, in which case the
# symbol specifies how the new tour is created:
# m.make_tour(:random):: make a complete tour of all cities in a random order
# m.make_tour(:mutate, t1):: the new tour is a copy of t1 with a single point mutation
# m.make_tour(:cross, t1, t2):: the new tour is a cross between tours t1 and t2.
#
# Example:
# >> m = Map.new(10)
# => #
# >> m.make_tour([2,4,6])
# => #
# >> t1 = m.make_tour
# => #
# >> t2 = m.make_tour(:random)
# => #
# >> m.make_tour(:mutate, t1)
# => #
# >> m.make_tour(:cross, t1, t2)
# => #
def make_tour(*args)
begin
args << :nil if args.length == 0
case args[0]
when :nil
tour = Tour.new(self, labels) # note labels returns clone of @labels array...
when :random
tour = Tour.new(self, permute!(labels))
when :mutate
raise "usage" unless args.length >= 2 && args[1].class == Tour && (args[2].nil? || args[2].class == Fixnum)
child = args[1].clone
dmax = args[2] ? args[2] : 1
i = rand(size)
d = 1 + rand(dmax)
# puts "mutate #{i} #{d}"
tour = child.mutate!(i,d)
child.parent = args[1]
child.op = [:mutate, i, d]
when :cross
raise "usage" unless args.length == 3 && args[1].class == Tour && args[2].class == Tour
child = args[1].clone
i = rand(size)
n = 1 + rand(size-1)
# puts "cross #{i} #{n}"
tour = child.cross!(args[2], i, n)
child.parent = args[1]
child.op = [:cross, args[2], i, n]
else
raise "usage" unless args[0].class == Array
a = args[0]
errs = 0
a.each do |x|
if ! @labels.include?(x)
puts "unknown city: #{x}"
errs += 1
end
end
raise "errors in list of cities" if errs > 0
tour = Tour.new(self, a)
end
rescue Exception => e
if e.message == "usage"
puts "Usage:"
puts " make_tour( [x,y,..] )"
puts " make_tour( :random )"
puts " make_tour( :mutate, t [,n] )"
puts " make_tour( :cross, t1, t2 )"
else
puts "make_tour: #{e.message}"
end
return nil
end
return tour
end
# Generate all possible tours of this map. Every tour starts in the first
# city (city 0 when city names are integers, or the first city read from
# the file). Successive tours are generated by the Johnson-Trotter algorithm,
# which generates permutations by exchanging just two cities from the previous
# tour. The Johnson-Trotter algorithm makes it possible to stop iterating
# after all unique tours starting from city 0 have been generated.
#
# Example:
# >> m = Map.new(5)
# => #
# >> m.each_tour { |t| puts t }
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# => nil
def each_tour
a = []
n = @labels.length
for i in 1...n do
a << ItemWithDirection.new(i, true)
end
loop do
# yield [0] + a
yield Tour.new(self, [@labels[0]] + a.map { |x| @labels[x.value] })
mover = nil
for i in 0...a.length
mover = i if movable(a,i) && (mover.nil? || a[i].value > a[mover].value)
end
break if mover.nil?
k = a[mover].value
# puts "mover = #{mover} k = #{k}"
break if k == 2
adj = a[mover].direction ? mover-1 : mover+1
a[adj], a[mover] = a[mover], a[adj]
for i in 0...a.length
if a[i].value > k
a[i].direction ^= true
end
end
end
end
# Return the number of cities in this map.
def size
return @labels.length
end
# Return the first pair of city labels in this map -- used only by
# read_file when loading a map from a file.
def first # :nodoc:
return @labels[0..1]
end
# Iterate over every other pair of city labels except the first -- used
# only by read_file when loading a map from a file.
def rest # :nodoc:
n = @labels.length
@labels.each_with_index do |x,i|
@labels.last(n-i-1).each_with_index do |y,j|
next if i == 0 && j == 0
yield(x,y)
end
end
end
# Return the distance between cities +i+ and +j+ (which can be
# given in either order, i.e. d[i,j] is the same as d[j,i]).
#
# Example:
# >> m = Map.new(:ireland)
# => #
# >> m[:cork, :dublin]
# => 257.0
#
# >> m = Map.new(10)
# => #
# >> m[6,2]
# => 111.07
def [](i,j)
ix = @labels.index(i) or return nil
jx = @labels.index(j) or return nil
ix, jx = jx, ix if ix < jx
@dist[ix][jx]
end
# Update the map by assigning a new distance between cities +i+ and +j+.
#
# Example:
# >> m[6,2] = 110
# => 110
def []=(i,j,val)
raise "Map: can't assign to diagonal" if i == j
ix = index_of(i)
jx = index_of(j)
ix, jx = jx, ix if ix < jx
@dist[ix][jx] = val.to_f
end
# Return a list of city names for this map.
#
# Example:
# >> m = Map.new(:ireland)
# => #
# >> m.labels
# => [:belfast, :cork, :dublin, :galway, :limerick]
def labels
return @labels.clone
end
# Return a copy of the distance matrix for this map, in the form of 2D triangular array of Floats.
#
# Example:
# >> m = Map.new(:ireland)
# => #
# >> m.dist
# => [[0.0], [425.0, 0.0], [167.0, 257.0, 0.0], [306.0, 209.0, 219.0, 0.0], [323.0, 105.0, 198.0, 105.0, 0.0]]
def dist
d = Array.new
@dist.each { |row| d << row.clone }
return d
end
# Return the canvas coordinates of city +x+.
def coords(x)
return @coords[index_of(x)]
end
# deprecated
#
# def delete(i)
# ix = @labels.index(i) or return nil
# (ix...@labels.length).each { |x| @dist[x].slice!(ix) }
# @dist.slice!(ix)
# @labels.slice!(ix)
# end
private
def index_of(i)
if (ix = @labels.index(i)) == nil
ix = @labels.length
@labels << i
@dist[ix] = Array.new
@dist[ix][ix] = 0.0
end
return ix
end
def read_file(fn)
matrixfilename = fn.to_s + ".txt"
matrixfilename = File.join(@@tspDirectory, matrixfilename)
raise "Matrix not found: #{matrixfilename}" unless File.exists?(matrixfilename)
readingLocations = true
@maxdist = 0.0
File.open(matrixfilename).each do |line|
line.chomp!
next if line.length == 0
next if line[0] == ?#
rec = line.split
if rec[0][0] == ?:
readingLocations = false if rec[0] == ":matrix"
# tbd -- deal with other directives
elsif readingLocations
x = rec[2].to_sym
# printf "loc #{x} at #{rec[0]}, #{rec[1]}\n"
@coords[index_of(x)] = [rec[0].to_i, rec[1].to_i]
# p index_of(x)
# p @coords[index_of(x)]
else
i = rec[0].to_sym
j = rec[1].to_sym
d = rec[2].to_f
# printf "dist #{rec[0]} to #{rec[1]} = #{rec[2]}\n"
self[i,j] = d
@maxdist = d if d > @maxdist
end
end
errs = []
i, j = first
errs << [i,j] if j.nil?
self.rest do |i,j|
errs << [i,j] unless self[i,j] != nil
end
raise "Map.new: missing distances #{errs.inspect}" if errs.length > 0
end
def make_random_map(n)
h = Hash.new
a = Array.new
while h.size < n
h[rand(400)] = 1
end
h.keys.each do |k|
x = k / 20
y = k % 20
a << [x*20 + rand(5) + 50, y*20 + rand(5) + 50]
end
make_map(a)
end
# helper method -- compute and save distances between cities named in array +a+
def make_map(a)
@maxdist = 0.0
for i in 0...a.length
for j in (i+1)...a.length
x = a[i][0] - a[j][0]
y = a[i][1] - a[j][1]
d = sqrt(x**2 + y**2)
self[i,j] = d
@maxdist = d if d > @maxdist
end
@coords[i] = a[i]
end
end
# helper method for each_tour iterator, used by Johnson-Trotter algorithm
def movable(a, i)
if a[i].direction
return i > 0 && a[i].value > a[i-1].value
else
return i < a.length-1 && a[i].value > a[i+1].value
end
end
end # class Map
=begin rdoc
== Tour
A Tour object is an array of city names, corresponding to the cities visited, in order,
by the salesman. Attributes are the path, its cost, a unique tour ID, and a reference to
the matrix used to define the distance between pairs of cities.
Class methods access the number of tours created, or reset the tour counter to 0. There
is a constructor, but users should call the make_tour method of the Map class to
create a new tour instead of calling Tour.new.
#--
TODO don't give access to path (unless there's a way to make it read-only -- freeze it?)
=end
class Tour
attr_reader :id, :path, :cost, :matrix
attr_accessor :parent, :op
@@id = 0
# Set the tour counter back to 0.
def Tour.reset
@@id = 0
end
# Return the number of Tour objects created.
def Tour.count
return @@id
end
# Create a new Tour object for Map +m+, visiting cities in the array +a+.
#
# NOTE: this method should not be called directly; make a new Tour by calling
# Map#make_tour instead.
def initialize(m, s)
@matrix = m
@path = s.clone
@cost = pathcost
@id = @@id
@@id += 1
end
# Create a string that lists the cities in this object, in order, and the tour cost.
def inspect
sprintf "#", @path.inspect, @cost
end
alias to_s inspect
# Make a "deep copy" of this tour object, giving it a copy of the list of cities.
def clone
# return Tour.new(@matrix, @path, @nm, @nx)
return Tour.new(@matrix, @path)
end
# Change this tour object by applying a "point mutation" that swaps the city
# at location +i+ in the tour with the city +d+ locations away. +d+ is set to 1 by
# default, i.e. if no value is supplied for +d+ the city at location +i+ is
# exchanged with the one at location +i++1.
#
# Example:
# >> t = m.make_tour
# => #
# >> t.mutate!(3)
# => #
#
# >> t = m.make_tour
# => #
# >> t.mutate!(3, 5)
# => #
#--
# Exchange mutation (called 'EM' by Larranaga et al). Swaps node i with one
# d links away (d = 1 means neighbor). An optimization (has a big impact when
# tours are 20+ cities) computes new cost by subtracting and adding single
# link costs instead of recomputing full path length. Notation: path
# through node i goes xi - i - yi, and path through j is xj - j - yj.
def mutate!(i, d = 1)
raise "mutate!: index #{i} out of range 0..#{@path.length}" unless (i >=0 && i < @path.length)
return if d == 0 # these two special cases won't occur when
if d == @path.length-1 # mutate! called from evolve, but....
i = (i-1) % @path.length
d = 1
end
j = (i+d) % @path.length # location of swap
xi = (i-1) % @path.length # locations before, after i
yi = (i+1) % @path.length
xj = (j-1) % @path.length # locations before, after j
yj = (j+1) % @path.length
if d == 1
@cost -= @matrix[ @path[xi], @path[i] ]
@cost -= @matrix[ @path[j], @path[yj] ]
@cost += @matrix[ @path[xi], @path[j] ]
@cost += @matrix[ @path[i], @path[yj] ]
else
@cost -= @matrix[ @path[xi], @path[i] ]
@cost -= @matrix[ @path[i], @path[yi] ]
@cost -= @matrix[ @path[xj], @path[j] ]
@cost -= @matrix[ @path[j], @path[yj] ]
@cost += @matrix[ @path[xi], @path[j] ]
@cost += @matrix[ @path[j], @path[yi] ]
@cost += @matrix[ @path[xj], @path[i] ]
@cost += @matrix[ @path[i], @path[yj] ]
end
@path[i], @path[j] = @path[j], @path[i]
# uncomment to verify path cost logic
# if (@cost - pathcost).abs > 0.001
# puts "#{i} #{j}" + self.to_s + " / " + @cost.to_s
# end
self
end
# Mutate the current tour by applying a "cross-over" mutation with tour t2.
# The new path for this object will contain all the cities from locations +i+ through
# +j+ in the current path, then all the remaining cities in the order in which they are
# found in tour t2.
#
# Example:
# >> t = m.make_tour
# => #
# >> t2 = m.make_tour(:random)
# => #
# >> t.cross!(t2, 2, 5)
# => #
#--
# Order cross-over (called 'OX1' by Larranaga et al). Save a chunk of the
# current tour, then copy the remaining cities in the order they occur in
# tour t. i is the index of the place to start copying, n is the number to
# copy.
def cross!(t, i, n)
j = (i + n - 1) % @path.length
if i <= j
p = @path[i..j]
else
p = @path[i..-1]
p += @path[0..j]
end
@path = p
t.path.each do |c|
@path << c unless @path.include?(c)
end
@cost = pathcost
self
end
# Compute the cost of this tour by summing the distances between cities in the
# order shown in the current path. In general users do not need to call this
# method, since the path is computed when the object is created, and is updated
# automatically by calls to mutate! and cross!, but this method
# is used in unit tests to make sure the cost is updated properly by the mutation methods.
def pathcost
sum = @matrix[ @path[0], @path[-1] ]
for i in 0..@path.length-2
sum += @matrix[ @path[i], @path[i+1] ]
end
return sum
end
end # class Tour
# Return the value of +n+!, i.e. compute +n+ * +n+-1 * +n+-2 ... 1.
#
# Example:
# >> factorial(10)
# => 3628800
#--
# It's tempting to write factorial with inject, but this is for the
# students to look at....
def factorial(n)
f = 1
for i in 2..n
f *= i
end
return f
end
# Compute the number of possible tours for a map with +n+ cities, taking
# into account the fact that a tour can start at any of the +n+ cities and
# that direction doesn't matter.
#
# Example:
# >> ntours(10)
# => 181440
def ntours(n)
return factorial(n-1) / 2
end
# Do an exhaustive search of all possible tours of cities in map +m+,
# returning the tour object that has the lowest cost path.
#
# Example:
# >> m = Map.new(10)
# => #
# >> ntours(10)
# => 181440
# >> xsearch(m)
# => #
# >> time { xsearch(m) }
# => 41.668501
def xsearch(m)
best = m.make_tour
m.each_tour { |t| best = t if t.cost < best.cost }
return best
end
# Do a random search of the possible tours of cities in map +m+.
# Creates +nsamples+ random tour objects and returns the one that
# has the lowest cost. Optional arguments:
# :pause => 0.01 the amount of time (in seconds) to pause between samples
#
# Example:
# >> m = Map.new(10)
# => #
# >> m.make_tour(:random)
# => #
# >> rsearch(m, 100)
# => #
def rsearch( m, nsamples, userOptions = {} )
options = @@rsearchOptions.merge(userOptions)
Tour.reset
best = m.make_tour(:random)
if @@drawing
make_histogram([]) # clear histogram display
view_tour(best)
init_labels(["#tours:", "cost:"])
end
(nsamples-1).times do |i|
t = m.make_tour(:random)
if t.cost < best.cost
best = t
if @@drawing
view_tour(t)
@@drawing.labels[1].update(sprintf( "cost: %.2f", best.cost ))
end
end
if @@drawing
@@drawing.labels[0].update(sprintf( "#tours: %d", Tour.count ))
end
sleep options[:pause]
end
return best
end
# Create an array with +n+ random tours of the cities in map +m+. The tours
# will be sorted in order of increasing path cost. If the canvas is open,
# a histogram of tour costs is displayed.
#
# Example:
# >> p = init_population(m, 10)
# => [ #,
# #,
# ...
# #,
# # ]
#--
# :begin :init_population
def init_population( m, n )
a = Array.new
n.times do
a << m.make_tour(:random)
end
a.sort! { |x,y| x.cost <=> y.cost }
if @@drawing
make_histogram(a)
end
return a
end
# :end :init_population
# Apply "natural selection" to +population+, which should be an array of tour objects. Sort
# the array by
# fitness, then remove individual +i+ with probability +i+/+n+ where +n+ is the population
# size. Note the first item in the array is always kept since 0/+n+ = 0.
#
# Example:
# >> p = init_population(m, 10)
# => [#,
# #,
# ...
# #,
# #]
# >> p.length
# => 10
# >> select_survivors(p)
# => [#,
# #,
# #,
# #]
# >> p.length
# => 4
#--
# This version of the call to sort! keeps the first tour created if there is a tie:
# p.sort! { |x,y| (x.cost == y.cost) ? (x.id <=> y.id) : (x.cost <=> y.cost) }
#
# This version of the method uses two phases when the map is shown on the screen, in
# order to display deleted populations as gray bars in the histogram.
# :begin :select_survivors
def select_survivors( population, toplevel = true )
population.sort! { |x,y| x.cost <=> y.cost }
n = population.size
(n-1).downto(1) do |i|
if ( rand < (i.to_f / n) )
if @@drawing && toplevel
population[i].op = :zap
else
population.delete_at(i)
end
end
end
if @@drawing && toplevel
show_survivors( population )
(n-1).downto(1) do |i|
population.delete_at(i) if population[i].op == :zap
end
end
return population
end
# :end :select_survivors
# Add new tours to +population+, which should be an array of Tour objects, until the size
# of the array reaches +n+. Each new tour is a mutation of one or two tours currently
# in +p+. The optional arguments is an expression of the form :distribution => :x where +x+
# is an array of three floating point numbers corresponding to the probability of a small point mutation,
# the probability of a large point mutation, and the probability of a crossover. The three numbers
# must sum to 1.0. For convenience, instead of passing an array, the argument +x+ can be the name
# of one of the predefined distributions:
# :mixed [0.5, 0.25, 0.25]
# :all_small [1.0, 0.0, 0.0]
# :all_large [0.0, 1.0, 0.0]
# :all_cross [0.0, 0.0, 1.0]
# The distribution name can also be :random, in which case new tours are not mutations of
# existing tours but rather random tours.
# If no distribution is specified the default is :all_small
#
# Example:
# >> rebuild_population(pop, 10)
# => [#,
# ...
# #]
#
# >> rebuild_population(pop, 20, :distribution => :mixed)
# => [#,
# ...
# #]
#--
# :begin :rebuild_population
def rebuild_population( population, popsize, userOptions = {} )
options = @@esearchOptions.merge(userOptions)
map = population[0].matrix # assume they're all from the same map...
dist = options[:distribution]
psmall, plarge, pcross = options[:profiles][dist]
sdmax = options[:sdmax] || ((map.size > 10) ? (map.size / 10) : 1)
ldmax = options[:ldmax] || ((map.size > 10) ? (map.size / 4) : 1)
prev = population.length # items before this index are from previous generation
while population.length < popsize
r = rand
if r < 1.0 - (psmall + plarge + pcross)
kid = map.make_tour( :random )
elsif r < 1.0 - (plarge + pcross)
mom = population[ rand(prev) ]
kid = map.make_tour( :mutate, mom, sdmax )
elsif r < 1.0 - pcross
mom = population[ rand(prev) ]
kid = map.make_tour( :mutate, mom, ldmax )
else
mom = population[ rand(prev) ]
dad = population[ rand(prev) ]
kid = map.make_tour( :cross, mom, dad )
end
population << kid
end
if @@drawing
update_histogram(population)
end
return population
end
# :end :rebuild_population
# Main loop of the genetic algorithm to find the optimal tour of a set of cities.
# +population+ is an array of tour objects (see init_population). +maxgen+ is the
# number of rounds of selection and rebuilding to execute. The third argument is
# usually omitted, but might be set when this method is called from esearch. It is
# used to continue a previous search. For example, if an earlier search ran for 100
# generations, to continue for another 100 generations, esearch will call this method
# with +maxgen+ = 200 and +ngen+ = 100. Any options passed after +ngen+ will be passed
# on to rebuild_population, to specify which mutation parameters to use.
#
# Example -- create a population and evolve it over 100 generations:
# >> p = init_population(m, 10)
# => [#,
# ...
# #]
# >> evolve(p, 100)
# => #
#--
# :begin :evolve
def evolve( population, maxgen, ngen = 0, options = {} )
popsize = population.length
best = population[0]
while ngen < maxgen
select_survivors( population, false )
rebuild_population( population, popsize, options)
if (population[0].cost - best.cost).abs > 1e-10
best = population[0]
updated = true
else
updated = false
end
ngen += 1
update_tour_display( population, ngen, updated, options[:pause] ) if @@drawing
end
return best
end
# :end :evolve
# Use an evolutionary algorithm to search for the optimal tour of the cities on a map +m+.
# The +maxgen+ argument is the number of cycles of selection and rebuilding to perform.
# The return value is the tour object with the lowest cost in the final population.
#
# The optional arguments following +maxgen+ specify parameters of the evolutionary algorithm. Possible options
# and their defaults are:
# :popsize => 10 population size
# :distribution => :all_small (see note below)
# :pause => 0.02 time (in seconds) to pause between each generation
# The distribution option can be an array of Floats or one of the symbols :mixed, :random,
# :all_small,
# :all_large, or :all_cross passed to the rebuild_population method (see the
# documentation of that method for an explanation).
#
# Example:
# >> m = Map.new(15)
# => #
# >> esearch(m, 100)
# => #
# >> esearch(m, 100, :distribution => :mixed)
# => #
# >> esearch(m, 100, :distribution => [0.5, 0.0, 0.5])
# => #
def esearch( m, maxgen, userOptions = {} )
options = @@esearchOptions.merge(userOptions)
if options[:continue]
if @@previousPopulation
population = @@previousPopulation
options = @@previousOptions
ngen = @@previousNGen
else
puts "no saved population"
return nil
end
else
Tour.reset
population = init_population( m, options[:popsize] )
ngen = 0
if @@drawing
init_labels(["generations:", "tours:", "cost:"])
view_tour( population[0] )
end
end
begin
check_mutation_parameters(options)
rescue Exception => e
puts "esearch: " + e
return false
end
evolve( population, maxgen, ngen, options )
@@previousPopulation = population
@@previousOptions = options
@@previousNGen = maxgen
return population[0]
end
# Save a copy of a map from the TSPLab data directory in the current working directory.
# If the +filename+ argument is not specified the new file will be the name of the map
# with ".txt" appended.
#
# Example:
# >> checkout(:ireland, "my_ireland_map.txt")
# Copy of ireland saved in my_ireland_map.txt
# => nil
def checkout(m, filename = nil)
matrixfilename = m.to_s + ".txt"
matrixfilename = File.join(@@tspDirectory, matrixfilename)
if !File.exists?(matrixfilename)
puts "Map not found: #{matrixfilename}"
return nil
end
outfilename = filename.nil? ? (m.to_s + ".txt") : filename
dest = File.open(outfilename, "w")
File.open(matrixfilename).each do |line|
dest.puts line.chomp
end
dest.close
puts "Copy of #{m} saved in #{outfilename}"
end
# Initialize the RubyLabs Canvas and draw the cities in map +m+. The locations
# of the cities are defined when the map is created. For maps distributed in
# the TSPLab data area (e.g. :ireland) the +x+ and +y+ coordinates of
# each city are part of the data file. For random maps, cities are placed randomly
# on the map.
#
# Options for controlling the color and size of a circle representing a city can
# be passed following +m+. The options, and their defaults, are:
# :dotColor => '#cccccc'
# :dotRadius => 5.0
#
# Example -- display the cities in map +m+ with large green circles:
# >> view_map(m, :dotRadius => 10, :dotColor => 'darkgreen')
# => true
def view_map(m, userOptions = {} )
options = @@mapOptions.merge(userOptions)
Canvas.init(800, 500, "TSPLab")
links = Array.new
nodes = Array.new
r = options[:dotRadius]
m.labels.each do |loc|
x, y = m.coords(loc)
nodes << Canvas::Circle.new( x, y, r, :fill => options[:dotColor] )
Canvas::Text.new(loc.to_s, x+r, y+r)
end
@@drawing = MapView.new(m, nodes, links, [], [], options)
return true
end
# Update the drawing on the RubyLabs canvas to show the paths in tour object +t+.
# Raises an error if the user has not yet called view_map to draw the locations of
# the cities first. A call to view_tour will erase an existing tour and then draw
# a new set of lines showing the path defined by +t+.
def view_tour(t, userOptions = {} )
if @@drawing.nil?
puts "call view_map to initialize the canvas"
return nil
end
options = @@esearchOptions.merge(userOptions)
map = @@drawing.cities
# @@drawing.links.each { |x| x.erase }
Canvas::Line.erase_all(:path)
@@drawing.links.clear
x0, y0 = map.coords(t.path[-1])
for i in 0...t.path.length
x1, y1 = map.coords(t.path[i])
@@drawing.links << Canvas::Line.new(x0, y0, x1, y1, :tags => :path)
x0, y0 = x1, y1
end
@@drawing.nodes.each { |x| x.raise }
return true
end
private
# Helper method, called from evolve to update the best tour and the displayed text
def update_tour_display(population, ngen, new_tour, dt)
if new_tour
view_tour(population[0])
@@drawing.labels[2].update(sprintf( "cost: %.2f", population[0].cost ))
end
update_histogram(population)
@@drawing.labels[0].update(sprintf( "generations: %d", ngen ))
@@drawing.labels[1].update(sprintf( "#tours: %d", Tour.count ))
sleep dt
end
# Helper method, called from select_survivors to update the histogram to show which
# tours have been deleted.
def show_survivors(pop)
hist = @@drawing.histogram
return unless pop.length == hist.length
hist.each_with_index do |box, i|
box.fill = 'gray' if pop[i].op == :zap
end
@@recolor = true
end
# Helper method, called from esearch to validate items passed in the options hash
def check_mutation_parameters(options)
dist = options[:distribution]
profiles = options[:profiles]
raise "specify mutation probabilities with :distribution option" unless dist
floaterr = "distribution must be an array of three numbers between 0.0 and 1.0"
symbolerr = "distribution must be one of #{profiles.keys.inspect}"
if dist.class == Symbol
raise symbolerr unless profiles[dist]
elsif dist.class == Array
raise floaterr unless dist.length == 3
sum = 0.0
dist.each { |x| raise floaterr if (x < 0.0 || x > 1.0); sum += x}
raise "sum of probabilities must be 1.0" unless (sum - 1).abs < Float::EPSILON
profiles[:user] = dist
options[:distribution] = :user
else
raise "#{floaterr} or #{symbolerr}"
end
end
# Helper method called by rsearch and esearch to create text strings on the display
# (for showing the cost of the best tour, etc.)
def init_labels(a)
labelx = 525
labely = 350
dy = 20
@@drawing.labels.each do |x|
x.erase
end
@@drawing.labels.clear
for i in 0...a.length
@@drawing.labels << Canvas::Text.new(a[i], labelx, labely)
labely += dy
end
return @@drawing.labels
end
# Helper method to draw a histogram of tour costs, called at the start of esearch.
# Note: rsearch calls make_histogram with an empty list to erase any previous histogram
# left by a call to esearch
def make_histogram(pop)
if @@drawing.histogram.length > 0
@@drawing.histogram.each { |box| box.erase }
@@drawing.histogram.clear
end
return if pop.length == 0
x = @@histogramOptions[:x]
y = @@histogramOptions[:y]
ymax = @@histogramOptions[:ymax]
w = @@histogramOptions[:binwidth]
scale = ymax / pop[-1].cost
npb = (pop.length / @@histogramOptions[:maxbins]).ceil
nbins = pop.length / npb
(0..pop.length-1).step(npb) do |i|
h = pop[i..(i+npb-1)].inject(0.0) { |sum, tour| sum + tour.cost }
h = (h/npb)*scale
@@drawing.histogram << Canvas::Rectangle.new(x, y+ymax-h, x+w, y+ymax, :fill => 'darkblue' )
x += w
end
@@drawing.options[:scale] = scale
@@histogramOptions[:npb] = npb
@@histogramOptions[:nbins] = nbins
@@recolor = false
end
# After rebuild_population fills in the array again, it calls this method to
# resize the boxes to show fitness of tours and refills the grayed out boxes.
def update_histogram(pop)
y = @@histogramOptions[:y]
ymax = @@histogramOptions[:ymax]
npb = @@histogramOptions[:npb]
scale = @@drawing.options[:scale]
@@drawing.histogram.each_with_index do |box, i|
j = i*npb
if j > pop.length
h = 0
else
h = pop[j..(j+npb-1)].inject(0.0) { |sum, tour| sum + tour.cost }
h = (h/npb)*scale
end
x0, y0, x1, y1 = box.coords
box.coords = x0, y+ymax-h, x1, y1
box.fill = 'darkblue' if @@recolor
end
end
# Outdated attempt to show sequence of ancestors -- if revived, needs to
# be updated for new Tk interface
# def show_lineage(tour, userOptions = {} )
# options = @@lineageOptions.merge(userOptions)
# dt = options[:dt]
# a = []
# while tour.parent
# a << tour
# tour = tour.parent
# end
# init_labels(["id:", "cost:", "op:"]) if @@drawing
# a.reverse.each do |x|
# puts x.inspect + ": " + x.op.inspect
# if @@drawing
# view_tour(x)
# labels = []
# labels << sprintf( "id: %d", x.id )
# labels << sprintf( "cost: %.2f", x.cost )
# labels << sprintf( "op: %s", x.op.inspect )
# update_labels(labels)
# sleep(dt)
# end
# end
# return true
# end
# def update_labels(a)
# labels = @@drawing.labels
# for i in 0...labels.length
# labels[i].update(a[i])
# end
# end
# def test_setup
# m = Map.new(15)
# view_map(m)
# t = m.make_tour(:random)
# view_tour(t)
# return [m, t]
# end
# Values accessible to all the methods in the module
@@tspDirectory = File.join(File.dirname(__FILE__), '..', 'data', 'tsp')
@@mapOptions = {
:dotColor => '#cccccc',
:dotRadius => 5.0,
}
@@rsearchOptions = {
:pause => 0.01,
}
@@esearchOptions = {
:popsize => 10,
:profiles => {
:mixed => [0.5, 0.25, 0.25],
:random => [0.0, 0.0, 0.0],
:all_small => [1.0, 0.0, 0.0],
:all_large => [0.0, 1.0, 0.0],
:all_cross => [0.0, 0.0, 1.0],
},
:distribution => :all_small,
:pause => 0.02,
}
@@histogramOptions = {
:x => 520.0,
:y => 100.0,
:ymax => 200.0,
:maxbins => 50.0,
:binwidth => 5,
}
@@lineageOptions = {
:dt => 2.0,
:first => 0,
:last => -1,
}
@@drawing = nil
@@previousPopulation = nil
end # module TSPLab
end # module RubyLabs
=begin rdoc
== Enumerable
The code for the Traveling Salesman lab (tsplab.rb) extends the Enumerable module
with a method that generates all permutations of a string, array, or any other object
from a class the includes the Enumerable interface.
=end
module Enumerable
# Iterate over all possible permutations of the objects in this enumerable object. The
# permutations are generated in lexicographic order. The new permutations are shallow copies
# of this object.
#
# Example:
# >> s = "ABCD"
# => "ABCD"
# >> s.each_permutation { |x| p x }
# "ABCD"
# "ABDC"
# "ACBD"
# "ACDB"
# "ADBC"
# ...
# "DBCA"
# "DCAB"
# "DCBA"
# => nil
def each_permutation
n = self.length
p = Array(0..n-1)
res = []
loop do
perm = self.clone
for k in 0...n do
perm[k] = self[p[k]]
end
if block_given?
yield perm
else
res << perm
end
# find largest j s.t. path[j] < path[j+1]
j = n-2
while j >= 0
break if p[j] < p[j+1]
j -= 1
end
break if j < 0
# find largest i s.t. path[j] < path[i]
i = n-1
loop do
break if p[j] < p[i]
i -= 1
end
# exchange path[j], path[i]
p[j], p[i] = p[i], p[j]
# reverse path from j+1 to end
tmp = p.slice!(j+1, n-1)
p += tmp.reverse
end
return block_given? ? nil : res
end
end
# Ruby 2.0: String doesn't mix in Enumerable...
class String
def each_permutation
if block_given?
self.chars.each_permutation { |p| yield p.join('') }
else
return self.chars.each_permutation.map { |p| p.join('') }
end
end
end