Module: RouletteSelection

Defined in:
lib/charlie/selection.rb

Overview

Roulette selection without replacement. Probability of individual i being selected is fitness(i) / sum fitness(1..population size)

Instance Method Summary collapse

Instance Method Details

#next_generation(population) ⇒ Object 



48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/charlie/selection.rb', line 48

def next_generation(population)
  partial_sum = []
  sum = 0
  population.each{|e| partial_sum << (sum += e.fitness) }

  n = population.size
  new_pop = []
  i = [0,0]
  while new_pop.size < n
    i[0] = i[1]
    until i[0]!=i[1]
      i.map!{ # binary search
        r = rand * sum
        l = 0; u = n-1;
        while l!=u
         m = (l+u)/2
         if partial_sum[m] < r
          l = m+1
         else
          u = m
         end
        end
        l
      }
    end
    new_pop += yield(population[i[0]],population[i[1]])
  end
  new_pop.pop until new_pop.size == population.size
  new_pop
end