Module: EdgeRecombinationCrossover

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

Overview

Edge recombination operator (en.wikipedia.org/wiki/Edge_recombination_operator)

  • Useful in permutations representing a path, e.g. travelling salesperson.

  • Returns a single child.

  • Permutations of 0…n only, i.e. default second parameter to PermutationGenotype

  • Rather slow.

Instance Method Summary collapse

Instance Method Details

#cross(parent1, parent2) ⇒ Object 



98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
# File 'lib/charlie/permutation/permutation.rb', line 98

def cross(parent1,parent2)
  p1, p2 = parent1.genes, parent2.genes
 
  nb = Array.new(parent1.size){[]}
  (p1 + p1[0..1]).each_cons(3){|l,m,r| nb[m] += [l,r] } # build neighbour lists
  (p2 + p2[0..1]).each_cons(3){|l,m,r| nb[m] += [l,r] } # build neighbour lists
  nb.map(&:uniq!)

  n = (rand < 0.5 ? p1.first : p2.first)
  child = [n]
  (nb.size-1).times{
    nb.each{|l| l.delete n unless l==:done }  # remove n from the lists

    if nb[n].empty?  # nb[n] empty, pick random next
      nb[n] = :done
      n = (0...nb.size).find_all{|x| nb[x] != :done }.at_rand # no neighbors left, pick random
    else # pick neighbour with minimal degree, random tie-breaking
      min_deg = nb[n].map{|x| nb[x].size }.min
      next_n = nb[n].find_all{|x| nb[x].size == min_deg }.at_rand # pick random neighbor with min. degree
      nb[n] = :done
      n = next_n
    end 
    child << n  # add new n to path
  }
  
  return from_genes(child)
end