Module: PartiallyMappedCrossover

Defined in:
lib/charlie/permutation/permutation.rb

Overview

Two point Partial Preservation Crossover for PermutationGenotype, also known as Partially Mapped Crossover (PMX).

The PMX proceeds by choosing two cut points at random:

Parent 1: hkcefd bla igj
Parent 2: abcdef ghi jkl

The cut-out section defines a series of swapping operations to be performed on the second parent. In the example case, we swap b with g, l with h and a with i and end up with the following offspring:

Offspring: igcdef bla jkh

Performing similar swapping on the first parent gives the other offspring:

Offspring: lkcefd ghi abj

Algortithm and description taken from:

"A New Genetic Algorithm For VPRTW", Kenny Qili Zhu, National University of Singapure,
April 13, 2000.

(maybe should be revised with some original documentation)

Instance Method Summary collapse

Instance Method Details

#cross(parent1, parent2) ⇒ Object 



146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
# File 'lib/charlie/permutation/permutation.rb', line 146

def cross(parent1,parent2)
  p1, p2 = parent1.genes, parent2.genes
  raise "Chromosomes too small, should be >= 4" if p1.size < 4
  
  # Cut-off points must be after first element and before last.
  cp1 = rand(p1.size-2) + 1
  cp2 = rand(p1.size-2) + 1 while cp2 == cp1 or cp2.nil?
  
  of1, of2 = Array.new(p2), Array.new(p1)
  (cp1..cp2).each do |index|
    of1.swap_element_at_index!(index, p1[index])
    of2.swap_element_at_index!(index, p2[index])
  end
  
  [of1, of2].map{|of| from_genes(of) }
end