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

population[RW]

Public Class Methods

new(initial_population_size, generations) click to toggle source
# 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

best_chromosome() click to toggle source

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
generate_initial_population() click to toggle source
# 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(offsprings) click to toggle source

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
reproduction(selected_to_breed) click to toggle source

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
run() click to toggle source
# 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
selection() click to toggle source

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:

  1. The fitness function is evaluated for each individual, providing fitness values

  2. The population is sorted by descending fitness values.

  3. 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.

  4. A random number R is chosen. R is between 0 and the accumulated normalized value (all the normalized fitness values added togheter).

  5. 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.

  6. 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
uniquify(elite_chromosomes) click to toggle source

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

select_random_individual(acum_fitness) click to toggle source
# 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