Class: GeneticAlgorithm

Inherits:
Object
  • Object
show all
Defined in:
lib/open-ship/gga4r/gga4r_main.rb

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(in_pop, prop = {}) ⇒ GeneticAlgorithm

Must be initialized with a Array of chromosomes To be a chomosome the object must implement the next methods:

- fitness
- recombine
- mutate
Accepts the next properties:
 - extra_generations: adds given array of generations to the GeneticAlgorithm's own array of generations.
 - p_combination: probability of combiantion ( by default 0.2 )
 - p_mutation: probability of mutation ( by default 0.01 )
 - max_population: maximum number of individuals that are allowed to form a generation.
 - logger: logger to write messages if given.



20
21
22
23
24
25
26
27
28
29
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 20

def initialize(in_pop, prop = {})    
  @generations = [in_pop]
  @generations += prop[:extra_generations] if prop[:extra_generations]
  @p_combination = prop[:p_combination] || 0.2
  @p_mutation = prop[:p_mutation] || 0.01
  @max_population =  prop[:max_population]
  @logger = prop[:logger] if prop[:logger]
  @use_threads = prop[:use_threads] if prop[:use_threads]
#    mean_fitness
end

Instance Attribute Details

#generations ⇒ Object (readonly)

Returns the value of attribute generations.



7
8
9
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 7

def generations
  @generations
end

#p_combination ⇒ Object (readonly)

Returns the value of attribute p_combination.



7
8
9
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 7

def p_combination
  @p_combination
end

#p_mutation ⇒ Object (readonly)

Returns the value of attribute p_mutation.



7
8
9
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 7

def p_mutation
  @p_mutation
end

Class Method Details

.populate_from_files(a_filenames, prop = {}) ⇒ Object

Returns a GeneticAlgorithm object with the generations loaded from given files and with properties prop. Files must contain the chromosomes in YAML format.



61
62
63
64
65
66
67
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 61

def self.populate_from_files(a_filenames, prop = {})
  a_filenames = [a_filenames] if a_filenames.class == String
  
  loaded_generations = a_filenames.collect { |filename| YAML.load(File.open(filename, "r")) }
  prop[:extra_generations] = loaded_generations[1..-1] if loaded_generations.size > 1
  return GeneticAlgorithm.new(loaded_generations[0], prop)
end

Instance Method Details

#best_fit(num_generation = -1)) ⇒ Object

Returns an array with the best fitted individuals for given generation number ( by default from last generation ).



41
42
43
44
45
46
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 41

def best_fit(num_generation = -1)
  raise "Generation not generated still num generations = #{num_generations}" if num_generation > num_generations  
  generation = @generations[num_generation]
  max_fitness = generation.collect { |chromosome| chromosome.fitness }.max
  generation.select { |chromosome| chromosome.fitness == max_fitness }
end

#evaluation(g) ⇒ Object

Prepares given generation for evaluation ( evaluates its fitness ).



90
91
92
93
94
95
96
97
98
99
100
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 90

def evaluation(g)
  @logger.debug "Evaluation " + g.size.to_s + " chromosomes." if @logger
  i = 0
  g.collect do |chromosome|
    i += 1
    @logger.debug "Evaluating chromosome #{i}:" if @logger
    @logger.debug "#{chromosome.stats.join("\n")}" if @logger
    chromosome.fitness
    chromosome
  end
end

#evaluation_with_threads(g) ⇒ Object

Prepares given generation for evaluation ( evaluates its fitness ), using Threads



104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 104

def evaluation_with_threads(g)
  @logger.debug "Evaluation " + g.size.to_s + " chromosomes." if @logger
  threads = []
  i = 0
  g.each do |chromosome|
    i += 1
    @logger.debug "Evaluating chromosome #{i}:" if @logger
    @logger.debug "#{chromosome.stats.join("\n")}" if @logger
    threads << Thread.new(chromosome) do |t_chromosome|
      t_chromosome.fitness
      @logger.debug "Thread finished #{Thread.current.object_id} - #{Thread.current.status}" if @logger
    end
  end
  # Wait for threads for finish
threads.each do |thread|
	@logger.debug "#{thread.status}" if @logger
	thread.join
	@logger.debug "#{thread.status}" if @logger
end
  return g
end

#evolve(num_steps = 1) ⇒ Object

Evolves the actual generation num_steps steps (1 by default).



80
81
82
83
84
85
86
87
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 80

def evolve(num_steps = 1)
  num_steps.times do
    @generations << evaluation_with_threads(@generations[-1])
    selection!
    recombination! 
    mutation!
  end
end

#mean_fitness(num = -1)) ⇒ Object

Returns the mean of the fitness for given generation number ( by default from last generation ).



50
51
52
53
54
55
56
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 50

def mean_fitness(num = -1)
  raise "Generation not generated still num generations = #{num_generations}" if num > self.num_generations
  num = self.num_generations if num == -1
  sum_fitness = 0
  @generations[num].each { |chromosome| sum_fitness += chromosome.fitness }
  sum_fitness.to_f / @generations[num].size.to_f
end

#mutation(g) ⇒ Object

Mutates population



154
155
156
157
158
159
160
161
162
163
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 154

def mutation(g)
  @logger.debug "Mutation " + g.size.to_s + " chromosomes." if @logger  
  new_generation = g.dup
  new_generation.each do |chromosome|
    if rand > (1 - @p_mutation)
      @logger.debug "Mutate" if @logger
      chromosome.mutate 
    end
  end
end

#mutation! ⇒ Object 



164
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 164

def mutation!; @generations[-1] = mutation(@generations[-1]); end

#num_generations ⇒ Object

Returns the number of generations that are in the GeneticAlgorithm object.



35
36
37
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 35

def num_generations
  @generations.size - 1
end

#recombination(g) ⇒ Object

Recombines population



136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 136

def recombination(g)
  @logger.debug "Recombination " + g.size.to_s + " chromosomes." if @logger
  new_generation = g.dup.shuffle!
  @logger.debug "Shuffled!" if @logger
  new_children = []
  new_generation.in_groups_of(2) do |chromosome1, chromosome2|
    next if chromosome2.nil?
    if rand > (1 - @p_combination)
      @logger.debug "Recombining" if @logger
      new_children << chromosome1.recombine(chromosome2)
    end
  end
  new_generation + new_children    
end

#recombination! ⇒ Object 



151
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 151

def recombination!; @generations[-1] = recombination(@generations[-1]); end

#remainder_stochastic_sampling(g) ⇒ Object

Remainder Stochastic Sampling algorithm for selection.



167
168
169
170
171
172
173
174
175
176
177
178
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 167

def remainder_stochastic_sampling(g)
  new_generation = []
  g.each do |chromosome|
    num_rep = 0
    if chromosome.fitness > 0
      num_rep += (chromosome.fitness.to_f/mean_fitness).to_i
      num_rep += 1 if rand > (1 - (chromosome.fitness/mean_fitness)%1)
    end
    new_generation = new_generation + ([chromosome] * num_rep)
  end
  new_generation
end

#save_generation(filename, num_generation = -1)) ⇒ Object

Saves into filename and in yaml format the generation that matchs with given generation number ( by default from last generation ).



71
72
73
74
75
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 71

def save_generation(filename, num_generation = -1)
  f = File.new(filename, "w")
  f.write(self.generations[num_generation].to_yaml)
  f.close    
end

#selection(g) ⇒ Object

Selects population to survive and recombine



128
129
130
131
132
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 128

def selection(g)
  g_tmp = remainder_stochastic_sampling(g)
  g_tmp = g_tmp.sort_by {|i| -i.fitness }[0..(@max_population-1)] if @max_population && (g_tmp.size > @max_population)
  g_tmp
end

#selection! ⇒ Object 



133
 
# File 'lib/open-ship/gga4r/gga4r_main.rb', line 133

def selection!; @generations[-1] = selection(@generations[-1]); end