Module: RubyLabs::TSPLab

Defined in:
lib/tsplab.rb

Overview

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.

Defined Under Namespace

Classes: ItemWithDirection, Map, MapView, Tour

Instance Method Summary collapse

Instance Method Details

#checkout(m, filename = nil) ⇒ Object

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



969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
 
# File 'lib/tsplab.rb', line 969

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

#esearch(m, maxgen, userOptions = {}) ⇒ Object

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)
=> #<TSPLab::Map [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]>
>> esearch(m, 100)
=> #<TSPLab::Tour [7, 14, 6, 9, 3, 10, 2, 1, 5, 0, 13, 8, 12, 4, 11] (1823.57)>
>> esearch(m, 100, :distribution => :mixed)
=> #<TSPLab::Tour [6, 9, 3, 12, 8, 4, 2, 10, 11, 13, 0, 5, 1, 7, 14] (1472.27)>
>> esearch(m, 100, :distribution => [0.5, 0.0, 0.5])
=> #<TSPLab::Tour [3, 4, 1, 6, 7, 9, 14, 11, 5, 8, 2, 13, 10, 12, 0] (1581.29)>



922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
 
# File 'lib/tsplab.rb', line 922

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

#evolve(population, maxgen, ngen = 0, options = {}) ⇒ Object

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)
=> [#<TSPLab::Tour [0, 5, 9, 13, 12, 10, 11, 4, 8, 14, 2, 7, 1, 6, 3] (2853.56)>, 
    ...
    #<TSPLab::Tour [9, 14, 13, 3, 11, 6, 5, 0, 8, 10, 1, 4, 7, 2, 12] (3527.98)>]
>> evolve(p, 100)
=> #<TSPLab::Tour [5, 0, 13, 12, 9, 10, 11, 8, 4, 14, 7, 1, 2, 6, 3] (2376.64)>

– :begin :evolve



879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
 
# File 'lib/tsplab.rb', line 879

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

#factorial(n) ⇒ Object

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.…



631
632
633
634
635
636
637
 
# File 'lib/tsplab.rb', line 631

def factorial(n)
  f = 1
  for i in 2..n
    f *= i
  end
  return f
end

#init_population(m, n) ⇒ Object

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)
=> [ #<TSPLab::Tour [1, 4, 3, 5, 0, 8, 6, 9, 2, 7] (1823.65)>,
     #<TSPLab::Tour [5, 1, 7, 8, 9, 4, 3, 2, 0, 6] (1835.27)>,
     ...
     #<TSPLab::Tour [1, 5, 6, 3, 8, 4, 2, 0, 7, 9] (2446.24)>,
     #<TSPLab::Tour [3, 2, 9, 8, 5, 4, 1, 0, 6, 7] (2765.43)> ]

– :begin :init_population



726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
 
# File 'lib/tsplab.rb', line 726

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

#ntours(n) ⇒ Object

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



647
648
649
 
# File 'lib/tsplab.rb', line 647

def ntours(n)
  return factorial(n-1) / 2
end

#rebuild_population(population, popsize, userOptions = {}) ⇒ Object

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)
=> [#<TSPLab::Tour [2, 7, 4, 11, 12, 6, 5, 14, 3, 0, 13, 9, 10, 1, 8] (2224.71)>, 
    ...
    #<TSPLab::Tour [2, 7, 4, 11, 12, 6, 5, 14, 3, 0, 13, 9, 8, 10, 1] (2485.64)>]

>> rebuild_population(pop, 20, :distribution => :mixed)
=> [#<TSPLab::Tour [2, 7, 4, 11, 12, 6, 5, 14, 3, 0, 13, 9, 10, 1, 8] (2224.71)>,
    ...
    #<TSPLab::Tour [14, 3, 0, 13, 9, 10, 1, 2, 7, 4, 11, 12, 6, 5, 8] (2329.32)>]

– :begin :rebuild_population



823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
 
# File 'lib/tsplab.rb', line 823

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

#rsearch(m, nsamples, userOptions = {}) ⇒ Object

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)
=> #<TSPLab::Map [0,1,2,3,4,5,6,7,8,9]>
>> m.make_tour(:random)
=> #<TSPLab::Tour [1, 4, 5, 6, 7, 2, 8, 9, 3, 0] (2323.46)>
>> rsearch(m, 100)
=> #<TSPLab::Tour [8, 7, 1, 2, 9, 4, 6, 3, 5, 0] (1356.22)>



683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
 
# File 'lib/tsplab.rb', line 683

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

#select_survivors(population, toplevel = true) ⇒ Object

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)
=> [#<TSPLab::Tour [6, 14, 8, 11, 9, 7, 12, 0, 5, 4, 3, 2, 10, 13, 1] (2926.67)>, 
    #<TSPLab::Tour [13, 6, 3, 2, 12, 7, 4, 10, 5, 1, 8, 11, 9, 14, 0] (3069.48)>, 
    ...
    #<TSPLab::Tour [5, 9, 1, 14, 10, 8, 0, 4, 2, 13, 3, 6, 7, 11, 12] (3455.32)>, 
    #<TSPLab::Tour [0, 4, 6, 14, 2, 5, 7, 8, 11, 9, 10, 12, 13, 3, 1] (3511.14)>]
>> p.length
=> 10
>> select_survivors(p)
=> [#<TSPLab::Tour [6, 14, 8, 11, 9, 7, 12, 0, 5, 4, 3, 2, 10, 13, 1] (2926.67)>, 
    #<TSPLab::Tour [10, 14, 6, 12, 9, 7, 11, 13, 3, 2, 4, 8, 0, 5, 1] (3119.66)>, 
    #<TSPLab::Tour [6, 10, 7, 12, 13, 4, 1, 2, 11, 14, 0, 3, 9, 8, 5] (3156.77)>, 
    #<TSPLab::Tour [11, 10, 1, 0, 5, 12, 8, 13, 2, 14, 6, 4, 7, 9, 3] (3206.06)>]
>> 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



771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
 
# File 'lib/tsplab.rb', line 771

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

#view_map(m, userOptions = {}) ⇒ Object

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



1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
 
# File 'lib/tsplab.rb', line 1000

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

#view_tour(t, userOptions = {}) ⇒ Object

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.



1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
 
# File 'lib/tsplab.rb', line 1020

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

#xsearch(m) ⇒ Object

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)
=> #<TSPLab::Map [0,1,2,3,4,5,6,7,8,9]>
>> ntours(10)
=> 181440
>> xsearch(m)
=> #<TSPLab::Tour [0, 7, 1, 8, 2, 3, 4, 6, 9, 5] (1027.68)>
>> time { xsearch(m) }
=> 41.668501



664
665
666
667
668
 
# File 'lib/tsplab.rb', line 664

def xsearch(m)
  best = m.make_tour
  m.each_tour { |t| best = t if t.cost < best.cost }
  return best
end