Class: Wallace::Operators::SubtourExchangeCrossoverOperator

Inherits:
Wallace::Operator show all
Defined in:
lib/operators/subtour_exchange_crossover_operation.rb

Overview

INCREDIBLY SLOW! O(n^3)

Defined Under Namespace

Classes: Subtour

Instance Method Summary collapse

Methods inherited from Wallace::Operator

#initialize, #produce

Constructor Details

This class inherits a constructor from Wallace::Operator

Instance Method Details

#operate(rng, inputs) ⇒ Object 



11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
# File 'lib/operators/subtour_exchange_crossover_operation.rb', line 11

def operate(rng, inputs)

  # Calculate the set of all subtours within each parent
  # chromosome that are greater than length 1 and shorter
  # than the entire tour length.
  len = inputs[0].length
  subtours = (0..1).map do |input|
    Hash[(2...len).map { |k|
      [k, (0...len).cons(k).map { |bounds|
        bounds = bounds.first..bounds.last
        Subtour.new(inputs[input][bounds], bounds)
      }]
    }]
  end

  # Check each k-length subtour for the same vertices.
  subtours = Hash[(2...len).map { |k|
    [ k,
      subtours[0][k].product(subtours[1][k]).select { |s1, s2|
        s1.tour - s2.tour == s2.tour - s1.tour
      }]
  }]

  # Reduce the set of sub-tours to a non-overlapping set.
  # (i.e. there are no (k-1)-length tours contained within a k-length tour).
  #
  # Alternatively we could perform replacements in ascending order
  # of subtour length. Simpler and gives the same result, but more replacements
  # are performed; is there much of a performance gain from pre-processing the
  # set of candidate subtours?
  #
  # For now we will stick to the latter for the sake of simplicity.
  subtours.each_value do |k_subtours|
    k_subtours.each do |s1, s2|
      inputs[0][s1.bounds] = s2.tour
      inputs[1][s2.bounds] = s1.tour
    end
  end

  return inputs

end