Module PartiallyMappedCrossover
In: lib/charlie/permutation/permutation.rb

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)

Methods

cross  

Public Instance methods

cross(parent1,parent2)

[Source]

     # File lib/charlie/permutation/permutation.rb, line 146
146:   def cross(parent1,parent2)
147:     p1, p2 = parent1.genes, parent2.genes
148:     raise "Chromosomes too small, should be >= 4" if p1.size < 4
149:     
150:     # Cut-off points must be after first element and before last.
151:     cp1 = rand(p1.size-2) + 1
152:     cp2 = rand(p1.size-2) + 1 while cp2 == cp1 or cp2.nil?
153:     
154:     of1, of2 = Array.new(p2), Array.new(p1)
155:     (cp1..cp2).each do |index|
156:       of1.swap_element_at_index!(index, p1[index])
157:       of2.swap_element_at_index!(index, p2[index])
158:     end
159:     
160:     [of1, of2].map{|of| from_genes(of) }
161:   end

[Validate]