class SimpleGa::GeneticAlgorithm::GeneticSearch
This class is used to automatically:
1. Choose initial population 2. Evaluate the fitness of each individual in the population 3. Repeat 1. Select best-ranking individuals to reproduce 2. Breed new generation through crossover and mutation (genetic operations) and give birth to offspring 3. Evaluate the individual fitnesses of the offspring 4. Replace worst ranked part of population with offspring 4. Until termination
Attributes
Public Class Methods
# File lib/simple_ga/genetic_algorithm.rb, line 28 def initialize(initial_population_size, generations) @population_size = initial_population_size @max_generation = generations @generation = 0 end
Public Instance Methods
Select the best chromosome in the population.
# File lib/simple_ga/genetic_algorithm.rb, line 145 def best_chromosome the_best = @population[0] @population.each do |chromosome| the_best = chromosome if chromosome.fitness > the_best.fitness # chromosome.fitness > the_best.fitness will produce the first best chromosome. # chromosome.fitness >= the_best.fitness will product the last best chromosome. # Hence, it is not a matter of concern unless the risk analysis is important. # e.g. high risk approach and low risk approach. end return the_best end
# File lib/simple_ga/genetic_algorithm.rb, line 74 def generate_initial_population @population = [] @population_size.times do population << Chromosome.seed end end
Replace worst ranked part of population with new offsprings.
# File lib/simple_ga/genetic_algorithm.rb, line 138 def replace_worst_ranked(offsprings) size = offsprings.length # Replacing from the back because the population has been sorted accordingly. @population = @population [0..((-1*size)-1)] + offsprings end
We combine each pair of selected chromosome using the method Chromosome.reproduce
The reproduction will also call the Chromosome.mutate
method with each member of the population. You should implement Chromosome.mutate
to only change (mutate) randomly. E.g. You could effectivly change the chromosome only if
rand < ((1 - chromosome.normalized_fitness) * 0.4)
# File lib/simple_ga/genetic_algorithm.rb, line 126 def reproduction(selected_to_breed) offsprings = [] 0.upto(selected_to_breed.length/2-1) do |i| offsprings << Chromosome.reproduce(selected_to_breed[2*i], selected_to_breed[2*i+1]) end @population.each do |individual| Chromosome.mutate(individual) end return offsprings end
# File lib/simple_ga/genetic_algorithm.rb, line 34 def run generate_initial_population #Generate initial population elite_chromosomes = [] #All possible solutions to the problem @max_generation.times do selected_to_breed = selection #Evaluates current population selected_to_breed.each do |chromosome| elite_chromosomes << chromosome end offsprings = reproduction selected_to_breed #Generate the population for this new generation replace_worst_ranked offsprings end unique_chromosomes = uniquify elite_chromosomes return unique_chromosomes end
Select best-ranking individuals to reproduce
Selection is the stage of a genetic algorithm in which individual genomes are chosen from a population for later breeding. There are several generic selection algorithms, such as tournament selection and roulette wheel selection. We implemented the latest.
Steps:
-
The fitness function is evaluated for each individual, providing fitness values
-
The population is sorted by descending fitness values.
-
The fitness values are then normalized. (Highest fitness gets 1, lowest fitness gets 0). The normalized value is stored in the “normalized_fitness” attribute of the chromosomes.
-
A random number R is chosen. R is between 0 and the accumulated normalized value (all the normalized fitness values added togheter).
-
The selected individual is the first one whose accumulated normalized value (its is normalized value plus the normalized values of the chromosomes prior it) greater than R.
-
We repeat steps 4 and 5, 2/3 times the population size.
# File lib/simple_ga/genetic_algorithm.rb, line 97 def selection @population.sort! { |a, b| b.fitness <=> a.fitness} best_fitness = @population[0].fitness worst_fitness = @population.last.fitness acum_fitness = 0 if best_fitness-worst_fitness > 0 @population.each do |chromosome| chromosome.normalized_fitness = (chromosome.fitness - worst_fitness)/(best_fitness-worst_fitness) acum_fitness += chromosome.normalized_fitness end else @population.each { |chromosome| chromosome.normalized_fitness = 1} end selected_to_breed = [] ((2*@population_size)/3).times do selected_to_breed << select_random_individual(acum_fitness) end selected_to_breed end
elite_chromosomes is an array of chromosomes.
# File lib/simple_ga/genetic_algorithm.rb, line 53 def uniquify(elite_chromosomes) search_space = [] unique_solutions = [] elite_chromosomes.each do |chromosome| search_space << chromosome.data end # Turns every unselected courses data into 0 search_space.each do |solution| 0.step(solution.length-1, 2) do |index| #Odd index solution[index+1] = 0 if solution[index] == 0 end end unique_search_space = search_space.uniq unique_search_space.each do |solution| unique_solutions << Chromosome.new(solution) end return unique_solutions end
Private Instance Methods
# File lib/simple_ga/genetic_algorithm.rb, line 158 def select_random_individual(acum_fitness) select_random_target = acum_fitness * rand local_acum = 0 @population.each do |chromosome| local_acum += chromosome.normalized_fitness return chromosome if local_acum >= select_random_target end end