lib/individual.rb
# Partially Mapped Crossover (PMX)
#   gene1,2 : parents' gene
#   po_num : points for splitting gene
# Arguments p1 and p2 are splitting points for debugging.
# If you give genes and p1, p2 directly,
#   gene1 = [1, 2, 3, 4, 5, 6, 7]
#   gene2 = [5, 4, 6, 7, 2, 1, 3]
#   p1 = 2, p2 = 5
# p1 and p2 split genes after 2nd element and 6th
#   gene1 = [1, 2 | 3, 4, 5, 6 | 7]
#   gene2 = [5, 4 | 6, 7, 2, 1 | 3]
# and you get children as following .
#   child1 = [3, 5, 6, 7, 2, 1, 4]
#   child2 = [2, 7, 3, 4, 5, 6, 1]

Partially Mapped Crossover (PMX)
gene1,2 : parents' gene
po_num : points for splitting gene
Arguments p1 and p2 are splitting points for debugging.
Partially Mapped Crossover ( PMX ) gene1 2 : parents ' gene po_num : points for splitting gene Arguments p1 and p2 are splitting points for debugging .
def partially_mapped_crossover(gene1, gene2, po_num=2, p1=nil, p2=nil)
    if p1 != nil and p2 != nil
      p1 = p1
      p2 = p2
    elsif po_num == 1
      p1 = rand(gene1.size - 1) + 1
      p2 = gene1.size
    elsif po_num == 2
      p1 = rand(gene1.size - 1) + 1
      p2 = rand(gene1.size - 1) + 1
      while p1 == p2
        p2 = rand(gene1.size - 1) + 1
      end
      if p1 > p2
        tmp = p1
        p1 = p2
        p2 = tmp
      end
    else
      raise "po_num must be 1 or 2!"
    end
    tmp1 = gene1.dup
    tmp2 = gene2.dup
    ary1 = tmp1.slice(p1, p2-p1)
    ary2 = tmp2.slice(p1, p2-p1)
    pre_map = {}  
    ary1.size.times do |i|
      pre_map[ary2[i]] = ary1[i]
    end
    tmph = pre_map.dup
    pre_map.each do |key, val|
      reduce_partial_map(tmph, key, val)
    end
    partial_map = {}  
    [tmph, tmph.invert].each do |h|
      h.each do |k,v|
        partial_map[k] = v
      end
    end
    child1 = []
    child2 = []
    gene1.size.times do |i|
      if (i < p1) or (p2-1 < i)  
        if partial_map[gene1[i]] != nil
          child1[i] = partial_map[gene1[i]]
        else
          child1[i] = gene1[i]
        end
        if partial_map[gene2[i]] != nil
          child2[i] = partial_map[gene2[i]]
        else
          child2[i] = gene2[i]
        end
      else  
        child1[i] = ary2[i - p1]
        child2[i] = ary1[i - p1]
      end
    end 
    if (child1.uniq.size != gene1.size) or (child2.uniq.size != gene2.size)
      raise "Error: Failed to gen children, #{child1.uniq.size}, #{child2.uniq.size}"
    end
    return child1, child2
  end
def partially_mapped_crossover ( gene1 , gene2 , po_num = 2 , p1 = nil , p2 = nil ) if p1 != nil and p2 != nil p1 = p1 p2 = p2 elsif po_num == 1 p1 = rand ( gene1 . size - 1 ) + 1 p2 = gene1 . size elsif po_num == 2 p1 = rand ( gene1 . size - 1 ) + 1 p2 = rand ( gene1 . size - 1 ) + 1 while p1 == p2 p2 = rand ( gene1 . size - 1 ) + 1 end if p1 > p2 tmp = p1 p1 = p2 p2 = tmp end else raise "po_num must be 1 or 2!" end tmp1 = gene1 . dup tmp2 = gene2 . dup ary1 = tmp1 . slice ( p1 , p2 - p1 ) ary2 = tmp2 . slice ( p1 , p2 - p1 ) pre_map = { } ary1 . size . times do | i | pre_map [ ary2 [ i ] ] = ary1 [ i ] end tmph = pre_map . dup pre_map . each do | key , val | reduce_partial_map ( tmph , key , val ) end partial_map = { } [ tmph , tmph . invert ] . each do | h | h . each do | k , v | partial_map [ k ] = v end end child1 = [ ] child2 = [ ] gene1 . size . times do | i | if ( i < p1 ) or ( p2 - 1 < i ) if partial_map [ gene1 [ i ] ] != nil child1 [ i ] = partial_map [ gene1 [ i ] ] else child1 [ i ] = gene1 [ i ] end if partial_map [ gene2 [ i ] ] != nil child2 [ i ] = partial_map [ gene2 [ i ] ] else child2 [ i ] = gene2 [ i ] end else child1 [ i ] = ary2 [ i - p1 ] child2 [ i ] = ary1 [ i - p1 ] end end if ( child1 . uniq . size != gene1 . size ) or ( child2 . uniq . size != gene2 . size ) raise "Error: Failed to gen children, #{child1.uniq.size}, #{child2.uniq.size}" end return child1 , child2 end
Partially Mapped Crossover (PMX)
gene1,2 : parents' gene
po_num : points for splitting gene
Arguments p1 and p2 are splitting points for debugging.
Partially Mapped Crossover ( PMX ) gene1 2 : parents ' gene po_num : points for splitting gene Arguments p1 and p2 are splitting points for debugging .
#p p1, p2
 # Extract partial gene for creating map
 # Create partial map
 # Map must be bi-directional, so create uni-directional map first. Then make it bi-directional.
 # uni-directional map
 #p pre_map
 # Clean map by reducing intermediate elements
 # bi-directional map
 #p partial_map
 # elements are replaced with map
 # replaced without map
 #p gene1.uniq.size, gene2.uniq.size
 #p child1, child2

gene1
<not_specific>
gene2
<not_specific>
po_num
<not_specific>
p1
<not_specific>
p2
<not_specific>