3 # Library to support genetic algorithms
9 # Version 1.1:: 23 April 2008
11 # A single genome in a population
16 # Create a random genome of the given length
17 def initialize(bitstring_or_length)
18 if bitstring_or_length.class == Fixnum
20 (1..bitstring_or_length).each do |i|
24 @genome = bitstring_or_length
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
34 new_genome.genome[i] = 1
36 new_genome.genome[i] = 0
39 new_genome.genome[i] = @genome[i]
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
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]
78 val = val * 2 + bits[0]
79 bits = bits[1..bits.length]
86 (1...self.length).each do |i|
87 if (self[i - 1] == 1) ^ (self[i] == 1)
98 (1...self.length).each do |i|
99 if (binary[i - 1] == 1) ^ (self[i] == 1)
111 def to_bitstring(min_length = 0)
122 while bits.length < min_length do
130 # A population of genomes
132 attr_accessor :individuals
134 # Create a population of a given size
135 def initialize(population_size, genome_length = 0)
137 1.upto(population_size) { @individuals << Genome.new(genome_length) }
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
151 next_population.individuals << parent1 << parent2
154 next_population.individuals.concat parents # pick up any parents that didn't get a chance to mate
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
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)