Class: RubyLabs::TSPLab::Tour

Inherits:
Object
  • Object
show all
Defined in:
lib/tsplab.rb

Overview

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

Constant Summary collapse

@@id = 
0

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(m, s) ⇒ Tour

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.



486
487
488
489
490
491
492
 
# File 'lib/tsplab.rb', line 486

def initialize(m, s)
  @matrix = m
  @path = s.clone
  @cost = pathcost
  @id = @@id
  @@id += 1
end

Instance Attribute Details

#cost ⇒ Object (readonly)

Returns the value of attribute cost.



464
465
466
 
# File 'lib/tsplab.rb', line 464

def cost
  @cost
end

#id ⇒ Object (readonly)

Returns the value of attribute id.



464
465
466
 
# File 'lib/tsplab.rb', line 464

def id
  @id
end

#matrix ⇒ Object (readonly)

Returns the value of attribute matrix.



464
465
466
 
# File 'lib/tsplab.rb', line 464

def matrix
  @matrix
end

#op ⇒ Object

Returns the value of attribute op.



465
466
467
 
# File 'lib/tsplab.rb', line 465

def op
  @op
end

#parent ⇒ Object

Returns the value of attribute parent.



465
466
467
 
# File 'lib/tsplab.rb', line 465

def parent
  @parent
end

#path ⇒ Object (readonly)

Returns the value of attribute path.



464
465
466
 
# File 'lib/tsplab.rb', line 464

def path
  @path
end

Class Method Details

.count ⇒ Object

Return the number of Tour objects created.



477
478
479
 
# File 'lib/tsplab.rb', line 477

def Tour.count
  return @@id
end

.reset ⇒ Object

Set the tour counter back to 0.



471
472
473
 
# File 'lib/tsplab.rb', line 471

def Tour.reset
  @@id = 0
end

Instance Method Details

#clone ⇒ Object

Make a “deep copy” of this tour object, giving it a copy of the list of cities.



504
505
506
507
 
# File 'lib/tsplab.rb', line 504

def clone
  # return Tour.new(@matrix, @path, @nm, @nx)
  return Tour.new(@matrix, @path)
end

#cross!(t, i, n) ⇒ Object

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
=> #<TSPLab::Tour [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (2281.08)>
>> t2 = m.make_tour(:random)
=> #<TSPLab::Tour [8, 1, 3, 2, 7, 6, 4, 0, 9, 5] (2039.49)>
>> t.cross!(t2, 2, 5)
=> #<TSPLab::Tour [2, 3, 4, 5, 6, 8, 1, 7, 0, 9] (2492.92)>

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



590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
 
# File 'lib/tsplab.rb', line 590

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

#inspect ⇒ Object Also known as: to_s

Create a string that lists the cities in this object, in order, and the tour cost.



496
497
498
 
# File 'lib/tsplab.rb', line 496

def inspect
  sprintf "#<TSPLab::Tour %s (%.2f)>", @path.inspect, @cost
end

#mutate!(i, d = 1) ⇒ Object

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
=> #<TSPLab::Tour [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (2281.08)>
>> t.mutate!(3)
=> #<TSPLab::Tour [0, 1, 2, 4, 3, 5, 6, 7, 8, 9] (1752.78)>

>> t = m.make_tour
=> #<TSPLab::Tour [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (2281.08)>
>> t.mutate!(3, 5)
=> #<TSPLab::Tour [0, 1, 2, 8, 4, 5, 6, 7, 3, 9] (1919.38)>

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



531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
 
# File 'lib/tsplab.rb', line 531

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

#pathcost ⇒ Object

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.



612
613
614
615
616
617
618
 
# File 'lib/tsplab.rb', line 612

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