Class: Algorithmically::Evolutionary::Genetic

Inherits:
Object
  • Object
show all
Defined in:
lib/Algorithmically/Evolutionary/genetic.rb

Instance Method Summary collapse

Constructor Details

#initialize(max_gens, num_bits, pop_size, p_crossover) ⇒ Genetic

Returns a new instance of Genetic.



6
7
8
9
10
 
# File 'lib/Algorithmically/Evolutionary/genetic.rb', line 6

def initialize(max_gens, num_bits, pop_size, p_crossover)
  p_mutation = 1.0/num_bits
  best = search(max_gens, num_bits, pop_size, p_crossover, p_mutation)
  puts "done! Solution: f=#{best[:fitness]}, s=#{best[:bitstring]}"
end

Instance Method Details

#binary_tournament(pop) ⇒ Object 



22
23
24
25
26
 
# File 'lib/Algorithmically/Evolutionary/genetic.rb', line 22

def binary_tournament(pop)
  i, j = rand(pop.size), rand(pop.size)
  j = rand(pop.size) if j==i
  (pop[i][:fitness] > pop[j][:fitness]) ? pop[i] : pop[j]
end

#crossover(parent1, parent2, rate) ⇒ Object 



37
38
39
40
41
 
# File 'lib/Algorithmically/Evolutionary/genetic.rb', line 37

def crossover(parent1, parent2, rate)
  ""+parent1 if rand()>=rate
  point = 1 + rand(parent1.size-2)
  parent1[0...point]+parent2[point...(parent1.size)]
end

#onemax(bitstring) ⇒ Object 



12
13
14
15
16
 
# File 'lib/Algorithmically/Evolutionary/genetic.rb', line 12

def onemax(bitstring)
  sum = 0
  bitstring.size.times { |i| sum+=1 if bitstring[i].chr=='1' }
  sum
end

#point_mutation(bitstring, rate = 1.0/bitstring.size) ⇒ Object 



28
29
30
31
32
33
34
35
 
# File 'lib/Algorithmically/Evolutionary/genetic.rb', line 28

def point_mutation(bitstring, rate=1.0/bitstring.size)
  child = ""
  bitstring.size.times do |i|
    bit = bitstring[i].chr
    child << ((rand()<rate) ? ((bit=='1') ? "0" : "1") : bit)
  end
  child
end

#random_bitstring(num_bits) ⇒ Object 



18
19
20
 
# File 'lib/Algorithmically/Evolutionary/genetic.rb', line 18

def random_bitstring(num_bits)
  (0...num_bits).inject("") { |s, i| s<<((rand<0.5) ? "1" : "0") }
end

#reproduce(selected, pop_size, p_cross, p_mutation) ⇒ Object 



43
44
45
46
47
48
49
50
51
52
53
54
55
 
# File 'lib/Algorithmically/Evolutionary/genetic.rb', line 43

def reproduce(selected, pop_size, p_cross, p_mutation)
  children = []
  selected.each_with_index do |p1, i|
    p2 = (i.modulo(2)==0) ? selected[i+1] : selected[i-1]
    p2 = selected[0] if i == selected.size-1
    child = {}
    child[:bitstring] = crossover(p1[:bitstring], p2[:bitstring], p_cross)
    child[:bitstring] = point_mutation(child[:bitstring], p_mutation)
    children << child
    children.size >= pop_size
  end
  children
end

#search(max_gens, num_bits, pop_size, p_crossover, p_mutation) ⇒ Object 



57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
# File 'lib/Algorithmically/Evolutionary/genetic.rb', line 57

def search(max_gens, num_bits, pop_size, p_crossover, p_mutation)
  population = Array.new(pop_size) do |i|
    {:bitstring => random_bitstring(num_bits)}
  end
  population.each { |c| c[:fitness] = onemax(c[:bitstring]) }
  best = population.sort { |x, y| y[:fitness] <=> x[:fitness] }.first
  max_gens.times do |gen|
    selected = Array.new(pop_size) { |i| binary_tournament(population) }
    children = reproduce(selected, pop_size, p_crossover, p_mutation)
    children.each { |c| c[:fitness] = onemax(c[:bitstring]) }
    children.sort! { |x, y| y[:fitness] <=> x[:fitness] }
    best = children.first if children.first[:fitness] >= best[:fitness]
    population = children
    puts " > gen #{gen}, best: #{best[:fitness]}, #{best[:bitstring]}"
    break best[:fitness] == num_bits
  end
  best
end