Initial commit
[trapthecap.git] / src / .svn / text-base / libgenetics.rb.svn-base
1 # == Synopsis
2 #
3 # Library to support genetic algorithms
4 #
5 # == Author
6 # Neil Smith
7 #
8 # == Change history
9 # Version 1.1:: 23 April 2008
10
11 # A single genome in a population
12 class Genome
13
14 attr_accessor :genome
15
16 # Create a random genome of the given length
17 def initialize(bitstring_or_length)
18 if bitstring_or_length.class == Fixnum
19 @genome = []
20 (1..bitstring_or_length).each do |i|
21 @genome << rand(2)
22 end
23 else
24 @genome = bitstring_or_length
25 end
26 end
27
28 # Mutate a genome with the given rate per bit
29 def mutate(mutation_probability = 0.05)
30 new_genome = Genome.new(@genome.length)
31 (0...@genome.length).each do |i|
32 if rand < mutation_probability
33 if @genome[i] == 0
34 new_genome.genome[i] = 1
35 else
36 new_genome.genome[i] = 0
37 end
38 else
39 new_genome.genome[i] = @genome[i]
40 end
41 end
42 new_genome
43 end
44
45 # Mutate a genome in-place with the given rate per bit
46 def mutate!(mutation_probability = 0.05)
47 (0...@genome.length).each do |i|
48 if rand < mutation_probability
49 if @genome[i] == 0
50 @genome[i] = 1
51 else
52 @genome[i] = 0
53 end
54 end
55 end
56 @genome
57 end
58
59 # Crossover two genomes at the given point
60 def crossover(other_genome, crossover_point)
61 raise ArgumentError, "Different size genomes" if @genome.length != other_genome.genome.length
62 raise ArgumentError, "Our of bounds crossover point" if crossover_point < 0 or crossover_point > @genome.length
63 child1 = Genome.new(0)
64 child2 = Genome.new(0)
65 child1.genome = @genome[0, crossover_point] + other_genome.genome[crossover_point, @genome.length]
66 child2.genome = other_genome.genome[0, crossover_point] + @genome[crossover_point, @genome.length]
67 [child1, child2]
68 end
69
70 end
71
72
73 class Array
74 def to_decimal
75 val = 0
76 bits = self.dup
77 while not bits.empty?
78 val = val * 2 + bits[0]
79 bits = bits[1..bits.length]
80 end
81 val
82 end
83
84 def gray_encode
85 gray = self[0..0]
86 (1...self.length).each do |i|
87 if (self[i - 1] == 1) ^ (self[i] == 1)
88 gray << 1
89 else
90 gray << 0
91 end
92 end
93 gray
94 end
95
96 def gray_decode
97 binary = self[0..0]
98 (1...self.length).each do |i|
99 if (binary[i - 1] == 1) ^ (self[i] == 1)
100 binary << 1
101 else
102 binary << 0
103 end
104 end
105 binary
106 end
107
108 end
109
110 class Fixnum
111 def to_bitstring(min_length = 0)
112 bits = []
113 k = self
114 while k > 0 do
115 if k % 2 == 1
116 bits << 1
117 else
118 bits << 0
119 end
120 k = k >> 1
121 end
122 while bits.length < min_length do
123 bits << 0
124 end
125 bits.reverse
126 end
127 end
128
129
130 # A population of genomes
131 class Population
132 attr_accessor :individuals
133
134 # Create a population of a given size
135 def initialize(population_size, genome_length = 0)
136 @individuals = []
137 1.upto(population_size) { @individuals << Genome.new(genome_length) }
138 end
139
140 # Perform the crossover step in a population, giving a new population
141 def crossover(crossover_rate)
142 parents = @individuals.dup # genomes that haven't been parents yet
143 next_population = Population.new(0)
144 while parents.length > 1
145 parent1 = parents.delete_at(rand(parents.length)).dup
146 parent2 = parents.delete_at(rand(parents.length)).dup
147 if rand < crossover_rate
148 child1, child2 = parent1.crossover parent2, rand(parent1.genome.length)
149 next_population.individuals << child1 << child2
150 else
151 next_population.individuals << parent1 << parent2
152 end
153 end
154 next_population.individuals.concat parents # pick up any parents that didn't get a chance to mate
155 next_population
156 end
157
158 # Perform the mutation step in a population, giving a new population
159 def mutation(mutation_rate)
160 parents = @individuals.dup # genomes that haven't been parents yet
161 next_population = Population.new(0)
162 while parents.length > 0
163 parent = parents.pop.dup
164 child = parent.mutate mutation_rate
165 next_population.individuals << child
166 end
167 next_population
168 end
169
170 def make_next_generation(tournament_winner_success_rate = 0.8, game_length = 1000, crossover_rate = 0.7, mutation_rate = 0.05)
171 @individuals = tournament_select_population(tournament_winner_success_rate, game_length, false)
172 @individuals = crossover(crossover_rate)
173 @individuals = mutation(mutation_rate)
174 end
175
176 end