Class: Ai4r::GeneticAlgorithm::GeneticSearch

Inherits:
Object
  • Object
show all
Defined in:
lib/ai4r/genetic_algorithm/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

If you want to customize the algorithm, you must modify any of the following classes:
  - Chromosome
  - Population

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(initial_population_size, generations, chromosome_class = TspChromosome, mutation_rate = 0.3, crossover_rate = 0.4, fitness_threshold = nil, max_stagnation = nil, on_generation = nil) ⇒ Object 



40
41
42
43
44
45
46
47
48
49
50
51
52
 
# File 'lib/ai4r/genetic_algorithm/genetic_algorithm.rb', line 40

def initialize(initial_population_size, generations, chromosome_class = TspChromosome,
               mutation_rate = 0.3, crossover_rate = 0.4,
               fitness_threshold = nil, max_stagnation = nil, on_generation = nil)
  @population_size = initial_population_size
  @max_generation = generations
  @generation = 0
  @chromosome_class = chromosome_class
  @mutation_rate = mutation_rate
  @crossover_rate = crossover_rate
  @fitness_threshold = fitness_threshold
  @max_stagnation = max_stagnation
  @on_generation = on_generation
end

Instance Attribute Details

#chromosome_class ⇒ Object (readonly)

Returns the value of attribute chromosome_class.



37
38
39
 
# File 'lib/ai4r/genetic_algorithm/genetic_algorithm.rb', line 37

def chromosome_class
  @chromosome_class
end

#crossover_rate ⇒ Object

Returns the value of attribute crossover_rate.



35
36
37
 
# File 'lib/ai4r/genetic_algorithm/genetic_algorithm.rb', line 35

def crossover_rate
  @crossover_rate
end

#fitness_threshold ⇒ Object

Returns the value of attribute fitness_threshold.



35
36
37
 
# File 'lib/ai4r/genetic_algorithm/genetic_algorithm.rb', line 35

def fitness_threshold
  @fitness_threshold
end

#max_stagnation ⇒ Object

Returns the value of attribute max_stagnation.



35
36
37
 
# File 'lib/ai4r/genetic_algorithm/genetic_algorithm.rb', line 35

def max_stagnation
  @max_stagnation
end

#mutation_rate ⇒ Object

Returns the value of attribute mutation_rate.



35
36
37
 
# File 'lib/ai4r/genetic_algorithm/genetic_algorithm.rb', line 35

def mutation_rate
  @mutation_rate
end

#on_generation ⇒ Object

Returns the value of attribute on_generation.



35
36
37
 
# File 'lib/ai4r/genetic_algorithm/genetic_algorithm.rb', line 35

def on_generation
  @on_generation
end

#population ⇒ Object

Returns the value of attribute population.



35
36
37
 
# File 'lib/ai4r/genetic_algorithm/genetic_algorithm.rb', line 35

def population
  @population
end

Instance Method Details

#best_chromosome ⇒ Object

Select the best chromosome in the population

Returns:

  • (Object) 


170
171
172
173
174
175
176
 
# File 'lib/ai4r/genetic_algorithm/genetic_algorithm.rb', line 170

def best_chromosome
  the_best = @population[0]
  @population.each do |chromosome|
    the_best = chromosome if chromosome.fitness > the_best.fitness
  end
  the_best
end

#generate_initial_population ⇒ Object

Returns:

  • (Object) 


91
92
93
94
95
96
 
# File 'lib/ai4r/genetic_algorithm/genetic_algorithm.rb', line 91

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

#replace_worst_ranked(offsprings) ⇒ Object

Replace worst ranked part of population with offspring

Parameters:

  • offsprings (Object)

Returns:

  • (Object) 


163
164
165
166
 
# File 'lib/ai4r/genetic_algorithm/genetic_algorithm.rb', line 163

def replace_worst_ranked(offsprings)
  size = offsprings.length
  @population = @population[0..(-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)

Parameters:

  • selected_to_breed (Object)

Returns:

  • (Object) 


145
146
147
148
149
150
151
152
153
154
155
156
157
158
 
# File 'lib/ai4r/genetic_algorithm/genetic_algorithm.rb', line 145

def reproduction(selected_to_breed)
  offsprings = []
  0.upto((selected_to_breed.length / 2) - 1) do |i|
    offsprings << @chromosome_class.reproduce(
      selected_to_breed[2 * i],
      selected_to_breed[(2 * i) + 1],
      @crossover_rate
    )
  end
  @population.each do |individual|
    @chromosome_class.mutate(individual, @mutation_rate)
  end
  offsprings
end

#run ⇒ Object

  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
5. Return the best chromosome

Returns:

  • (Object) 


64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/ai4r/genetic_algorithm/genetic_algorithm.rb', line 64

def run
  generate_initial_population                    # Generate initial population
  best = best_chromosome
  best_fitness = best.fitness
  stagnation = 0
  @on_generation&.call(@generation, best_fitness)
  @max_generation.times do
    @generation += 1
    selected_to_breed = selection                # Evaluates current population
    offsprings = reproduction selected_to_breed  # Generate the population for this new generation
    replace_worst_ranked offsprings
    current_best = best_chromosome
    if current_best.fitness > best_fitness
      best_fitness = current_best.fitness
      best = current_best
      stagnation = 0
    else
      stagnation += 1
    end
    @on_generation&.call(@generation, best_fitness)
    break if (@fitness_threshold && best_fitness >= @fitness_threshold) ||
             (@max_stagnation && stagnation >= @max_stagnation)
  end
  best
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 ar 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.

Returns:

  • (Object) 


115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
# File 'lib/ai4r/genetic_algorithm/genetic_algorithm.rb', line 115

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).positive?
    @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