Class: SimpleGa::GeneticAlgorithm::GeneticSearch

Inherits:
Object
  • Object
show all
Defined in:
lib/simple_ga/genetic_algorithm.rb

Overview

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(initial_population_size, generations) ⇒ GeneticSearch

Returns a new instance of GeneticSearch.



29
30
31
32
33
 
# File 'lib/simple_ga/genetic_algorithm.rb', line 29

def initialize(initial_population_size, generations)
  @population_size = initial_population_size
  @max_generation = generations
  @generation = 0
end

Instance Attribute Details

#population ⇒ Object

Returns the value of attribute population.



26
27
28
 
# File 'lib/simple_ga/genetic_algorithm.rb', line 26

def population
  @population
end

#unique_solutions ⇒ Object

Returns the value of attribute unique_solutions.



27
28
29
 
# File 'lib/simple_ga/genetic_algorithm.rb', line 27

def unique_solutions
  @unique_solutions
end

Instance Method Details

#best_chromosome ⇒ Object

Select the best chromosome in the population.



138
139
140
141
142
143
144
145
146
147
148
 
# File 'lib/simple_ga/genetic_algorithm.rb', line 138

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 ⇒ Object 



67
68
69
70
71
72
 
# File 'lib/simple_ga/genetic_algorithm.rb', line 67

def generate_initial_population
 @population = []
 @population_size.times do
   population << Chromosome.seed
 end
end

#replace_worst_ranked(offsprings) ⇒ Object

Replace worst ranked part of population with new offsprings.



131
132
133
134
135
 
# File 'lib/simple_ga/genetic_algorithm.rb', line 131

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) ⇒ Object

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)



119
120
121
122
123
124
125
126
127
128
 
# File 'lib/simple_ga/genetic_algorithm.rb', line 119

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 ⇒ Object 



35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/simple_ga/genetic_algorithm.rb', line 35

def run
  generate_initial_population       		                    
  search_space = []   					# All possible solutions to the problem.                            
  @max_generation.times do
    selected_to_breed = selection     	# Evaluates current population.           
    selected_to_breed.each do |chromosome|
      search_space << chromosome.data.dup
    end
    offsprings = reproduction selected_to_breed	 
    replace_worst_ranked offsprings
  end
  unique_solutions = uniquify search_space
  
  return best_chromosome
end

#selection ⇒ Object

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.



90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
# File 'lib/simple_ga/genetic_algorithm.rb', line 90

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(search_space) ⇒ Object 



51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/simple_ga/genetic_algorithm.rb', line 51

def uniquify(search_space)
  unique_search_space = search_space.uniq
  # Turns every unselected courses data into nil
  unique_search_space.each do |s|
    0.step(s.length-1, 2) do |index|         # Odd index
      if s[index] == 0
        s[index] = nil
        s[index+1] = nil
      end
    end
  end
  unique_solutions = unique_search_space.uniq

  return unique_solutions
end