Les algorithmes génétiques 39: Resolution du sac à dos

La dernière fois on a vu une façon simplement d’évaluer le contenu du sac à dos. Aujourd’hui on met en place l’algorithme génétique proprement dit: sélection, croisement, mutation, etc.

J’ai mis le code complet de l’algorithme sur Github. Celui-ci est basé sur ce qu’on a fait jusqu’ici pour le paradoxe du singe savant et pour le problème des 8 dames. Je vais donc commenter les parties qui changent.

La classe GeneticAlgorithm

class GeneticAlgorithm
  # ...

  def run
    best_ever = nil
    @generations.times do |generation|
      Evaluator.new(@capacity, @population).evaluate
      best = @population.best
      best_ever = best if best > best_ever
      display(generation, best)
      next_generation
    end
    display_best_ever(best_ever)
  end

  private

  # ...

  def display_best_ever(individual)
    puts "----------------------"
    puts "Best ever"
    puts "----------------------"
    puts "score:      #{individual.score}"
    puts "chromosome: #{individual.chromosome_as_list}"
  end

  # ...
end

Voyons la méthode run. La variable best_ever va contenir le meilleur individu, toutes générations confondues. À chaque itération, on compare ce «meilleur de tout les temps» avec le meilleur individu de la génération:

best_ever = best if best > best_ever

C’est pour ça qu’on avait besoin d’une méthode > dans la classe Individual (voir cet article).

À la fin de la méthode run on utilise la nouvelle méthode display_best_ever pour afficher notre meilleure solution.

La classe Mutator

La seconde classe qui change un peu est la classe Mutator:

class Mutator
  def initialize(chromosome_size, mutation_rate)
    @size = chromosome_size
    @rate = mutation_rate
  end

  def mutate(chromosome)
    @size.times do |index|
      chromosome[index] = ! chromosome[index] if rand < @rate
    end
    chromosome
  end
end

Un chromosome étant une liste (un Array) de booléens, la mutation consiste à inverser un élément, true devient false et inversement:

chromosome[index] = ! chromosome[index] if rand < @rate

Le lancement du programme

Le problème n’a pas l’air trop complexe, je me dis donc que 100 générations devraient suffire. La population compte 1 000 individus, ce qui est classique et le taux de mutation est assez élevé (1%):

knapsack_capacity = 400
generations = 100
population = Population.new(Knapsack::ITEMS.size, 1000)
mutation = 0.01
GeneticAlgorithm.new(generations, population, knapsack_capacity, mutation).run

Et voici le moment de vérité:

[~]⇒ ruby knapsack.rb 
Gen: 0 Best score: 922
Gen: 1 Best score: 950
.
.
.
Gen: 57 Best score: 1010
Gen: 58 Best score: 957
Gen: 59 Best score: 1030
.
.
.
Gen: 99 Best score: 957
----------------------
Best ever
----------------------
score:      1030
chromosome: map, compass, water, sandwich, glucose, banana, suntan cream,
waterproof trousers, waterproof overclothes, note-case, sunglasses, socks

La prochaine fois on va analyser ce résultat et faire en sorte de l’améliorer.

À demain.