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
)