Skip to content

Instantly share code, notes, and snippets.

@nikosd
Created January 18, 2009 11:29
Show Gist options
  • Save nikosd/48610 to your computer and use it in GitHub Desktop.
Save nikosd/48610 to your computer and use it in GitHub Desktop.
Two point partial preservation crossover for PermutationGenotype, also known as Partially Mapped Crossover (PMX).
# 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
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
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment