Skip to content

Instantly share code, notes, and snippets.

@felipeelias
Created March 30, 2018 14:50
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save felipeelias/33dadcbe54adc8c97dcc272886d218f1 to your computer and use it in GitHub Desktop.
Save felipeelias/33dadcbe54adc8c97dcc272886d218f1 to your computer and use it in GitHub Desktop.
Genetic algorithm
class Chromosome
SIZE = 10
attr_reader :value
def initialize(value)
@value = value
end
def fitness
# Implement in subclass
1
end
def [](index)
@value[index]
end
def mutate(probability_of_mutation)
@value = value.map { |ch| rand < probability_of_mutation ? invert(ch) : ch }
end
def invert(binary)
binary == '0' ? '1' : '0'
end
end
class KnapsackChromosome < Chromosome
CAPACITY = 1_000 # Max weight
SIZE = 100 # Slots
def fitness
weights = [2, 3, 6, 7, 5, 9, 4, 1, 9, 5] * 100
values = [6, 5, 8, 9, 6, 7, 3, 4, 2, 4] * 100
w = weights
.map
.with_index { |w, idx| value[idx].to_i * w }
.inject(:+)
v = values
.map
.with_index { |v, idx| value[idx].to_i * v }
.inject(:+)
w > CAPACITY ? 0 : v
end
end
class GeneticAlgorithm
def generate(chromosome)
value = Array.new(chromosome::SIZE) { %w[0 1].sample }
chromosome.new(value)
end
def select(population)
population.sample(2)
end
def crossover(selection, index, chromosome)
cr1 = selection[0][0...index] + selection[1][index..-1]
cr2 = selection[1][0...index] + selection[0][index..-1]
[chromosome.new(cr1), chromosome.new(cr2)]
end
def run(chromosome, p_cross, p_mutation, iterations = 100)
# initial population
population = 1000.times.map { generate(chromosome) }
current_generation = population
next_generation = []
iterations.times do
# save best fit
best_fit = current_generation.max_by(&:fitness).dup
puts "Best: #{best_fit.fitness}"
(population.size / 2).times do
selection = select(current_generation)
# crossover
if rand < p_cross
selection = crossover(selection, rand(0..chromosome::SIZE), chromosome)
end
# mutation
selection[0].mutate(p_mutation)
selection[1].mutate(p_mutation)
next_generation << selection[0] << selection[1]
end
current_generation = next_generation
next_generation = []
# Make sure best fit chromosome carries over
current_generation << best_fit
end
# return best solution
best_fit = current_generation.max_by(&:fitness)
"#{best_fit.value} => #{best_fit.fitness}"
end
end
ga = GeneticAlgorithm.new
puts ga.run(KnapsackChromosome, 0.2, 0.01, 10000)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment