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