Genetic algorithm

genetic.rb

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)