Class: Wallace::Operators::VariableOnePointCrossoverOperator

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

Overview

The variable one point crossover operator was designed to address the problem of bloat resulting from the crossover on variable length chromosomes using the splice crossover operator.

This operator takes two chromosomes as its input, X and Y, and slices each into two subsequences, A and B, and C and D, respectively. The first subsequence of X (A) is combined with the last subsequence of Y (D) to form one of the child chromosomes. The second child is formed by combining the first subsequence of Y © with the last subsequence of X (B).

The subsequences are chosen at random from the set of legal sub-sequences. More details on the process are given in “operate”.

The key feature of this operator is that it guarantees that the length of the child chromosomes will fall within some given bounds. This feature helps to control the problem of bloat in problems using variable length chromosomes and can significantly improve performance in certain cases.

WARNING: Operates on the assumption that the input individuals obey the length constraints. WARNING: The length of each input chromosome must be at least 2, failing this the original

inputs are simply returned.

Author: Chris Timperley

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods inherited from Wallace::Operator

#produce

Constructor Details

#initialize(opts = {}) ⇒ VariableOnePointCrossoverOperator

Constructs a new variable one point crossover operator.

Parameters:

  • opts, a hash of keyword options for this constructor. -> id, the unique identifier for this operator. -> bounds, the bounds upon the length of child chromosomes produced by this operator.



34
35
36
37
 
# File 'lib/operators/variable_one_point_crossover_operation.rb', line 34

def initialize(opts = {})
  super(opts)
  @bounds = opts[:bounds]
end

Instance Attribute Details

#bounds ⇒ Object

Returns the value of attribute bounds.



26
27
28
 
# File 'lib/operators/variable_one_point_crossover_operation.rb', line 26

def bounds
  @bounds
end

Instance Method Details

#operate(rng, parents) ⇒ Object

Produces two child chromosomes using two parent chromosomes according to the rules of this genetic operator.

Parameters:

  • rng, the RNG to use to select the crossover point.

  • parents, the parent chromosomes used in the operation.

Returns: An array containing two child chromosomes formed using data from the parent chromosomes.



48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
# File 'lib/operators/variable_one_point_crossover_operation.rb', line 48

def operate(rng, parents)

  # Calculate the length of each parent.
  x, y = parents[0].length, parents[1].length

  # If either parent chromosome is shorter than length 2 then return them as the child
  # chromosomes (else the operation will fail).
  return parents if x < 2 or y < 2 

  # Pseudo-randomly select the first sub-sequence of X (A) such that
  # 1 <= |A| < |X|. Let B be the remaining part of X.
  a = rng.rand(1...x)
  b = x - a

  # Using the chosen A, find all the possible values of |D| such that
  # MIN <= |A| + |D| <= MAX. Restrict the set of possible values for |D|
  # to those which produce a legal |C| (i.e. MIN <= |B| + |C| <= MAX)
  # before sampling a value uniformly at random.
  d = ([1, @bounds.min - a].max..[y, @bounds.max - a].min).to_a.select{ |v|
    @bounds.cover?(b + y - v)
  }.sample(random: rng)
  c = y - d

  # Gather and combine the subsequences into the child chromosomes using
  # their calculated lengths.
  return [
    parents[0].first(a) + parents[1].last(d),
    parents[1].first(c) + parents[0].last(b)
  ]

end