Two point partial preservation crossover for PermutationGenotype, also known as Partially Mapped Crossover (PMX).

pmx_operator.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)
module PartiallyMappedCrossover
  def cross(parent1,parent2)
    p1, p2 = parent1.genes, parent2.genes
    raise "Too small chromosomes" if p1.size < 4
    
    # Cut-off points must be after first element and before last. So (in Arrays terms) between 1 and N-2
    cp1 = rand(p1.size-2) while cp1 == 0 or cp1.nil?
    cp2 = rand(p1.size-2) while cp2 == cp1 or cp2 == 0 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
end

class Array
  # TODO: Update the generic RuntimeErrors with some custom Errors.
  
  # Swaps element1 with element2 inside an array. For example :
  #   a = [1, 2, 3, 4, 5]
  #   a.swap_element(5,3) => [1, 2, 5, 4, 3]
  #
  # Raises a RuntimeError in any of the following cases:
  #
  # * Array does not contain element1
  # * Array does not contain element2
  # * element1 occurs more than 1 time in the Array
  # * element2 occurs more than 1 time in the Array
  def swap_elements(element_to_be_replaced, new_element_value)
    self.enforce_swap_constraints!(element_to_be_replaced, new_element_value)
    new_ar = self.dup
    new_element_index, old_element_index = new_ar.index(element_to_be_replaced), new_ar.index(new_element_value)
    new_ar[new_element_index], new_ar[old_element_index] = new_element_value, replaced_element_value
    new_ar
  end
  
  # Same as swap_elements except it swaps elements of the calling Array and returns the new_element_value and the replaced_element_value
  def swap_elements!(element_to_be_replaced, new_element_value)
    self.enforce_swap_constraints!(element_to_be_replaced, new_element_value)
    new_element_index, old_element_index = self.index(element_to_be_replaced), self.index(new_element_value)
    self[new_element_index], self[old_element_index] = new_element_value, replaced_element_value
  end
  
  # Same as swap_elements except it accepts and index (of item to be replaced) and a new value for that index.
  def swap_element_at_index(index, value)
    self.enforce_swap_constraints!(self[index], value)
    new_ar = self.dup
    old_element_index = new_ar.index(value)
    new_ar[index], new_ar[old_element_index] = value, new_ar[index]
    new_ar
  end
  # Same as swap_element_at_index except it swaps elements of the calling Array and returns the new_element_value 
  # and the replaced_element_value.
  def swap_element_at_index!(index, value)
    self.enforce_swap_constraints!(self[index], value)
    old_element_index = self.index(value)
    self[index], self[old_element_index] = value, self[index]
  end
  
  # Returns true if the Array contains the specified element multiple times.
  def contains_multiple?(element)
    return true if self.index(element) != nil and self.index(element) != self.rindex(element)
  end
  
  protected
  def enforce_swap_constraints!(element_to_be_replaced, new_element_value)
    raise "Element #{element_to_be_replaced} has multiple occurancies in Array" if self.contains_multiple?(element_to_be_replaced)
    raise "Element #{new_element_value} has multiple occurancies in Array" if self.contains_multiple?(new_element_value)
    raise "Element #{element_to_be_replaced} is not inside the Array" unless self.include?(element_to_be_replaced)
    raise "Element #{element_to_be_replaced} is not inside the Array" unless self.include?(element_to_be_replaced)
  end
end

pmx_operator_array_extensions_spec.rb

require 'pmx_operator'

describe Array,'#swap_with_index!' do
  before do
    @sample = %w(a b c d e f)
  end
  
  it "should do it's job" do
    @sample.swap_element_at_index!(1,'f')
    @sample.should == %w(a f c d e b)
  end
end

pmx_operator_spec.rb

require 'pmx_operator'
include PartiallyMappedCrossover

describe "PartiallyMappedCrossover" do
  # Mocked Genotype#from_genes
  def from_genes(g)
    return g
  end
  
  before(:each) do
    @parent1 = mock("Genotype")
    @parent2 = mock("Genotype")
  end

  it "should produce valid results" do
    @parent1.should_receive(:genes).and_return(%w(h k c e f d b l a i g j))
    @parent2.should_receive(:genes).and_return(%w(a b c d e f g h i j k l))
    should_receive(:rand).twice.and_return(6,8)
    cross(@parent1,@parent2).should == [%w(i g c d e f b l a j k h), %w(l k c e f d g h i a b j)]
  end
  
  it "should not accept too small chromosomes (less than three genes)" do
    @parent1.should_receive(:genes).and_return(%w(h k c))
    @parent2.should_receive(:genes).and_return(%w(a b c))
    lambda {cross(@parent1,@parent2)}.should raise_error
  end
end