Les algorithmes génétiques démystifiés 38: Évaluation du sac à dos

Comment évaluer le contenu du sac à dos ? C’est à cette question qu’on répond aujourd’hui, après avoir vu hier la création de la population.

La fonction d’évaluation

Évaluer le contenu du sac à dos est trivial, on calcule sa valeur en ajoutant la valeur de tout les objets, et on calcule son poids en ajoutant le poids de tout les objets. Si le poids total dépasse la capacité du sac à dos, on va considèrer pour l’instant que la solution est invalide, et on ne lui permettra pas de se reproduire. Autrement dit, plus la valeur est importante sans que le poids ne dépasse la capacité, meilleure est l’individu.

La classe Evaluator

Voici le code complet de la classe Evaluator:

class Evaluator
  def initialize(capacity, population)
    @capacity = capacity
    @population = population
  end

  def evaluate
    @population.each {|individual| score(individual) }
    fitness
  end

  private

  def score(individual)
    value = 0
    weight = 0
    individual.chromosome.each_with_index do |item, index|
      if item
        value += Knapsack::ITEMS[index].value
        weight += Knapsack::ITEMS[index].weight
      end
    end
    if weight > @capacity
      individual.score = 0
    else
      individual.score = value
    end
  end

  def fitness
    total = @population.inject(0) {|sum, individual| sum + individual.score }
    size = @population.size
    @population.each do |individual|
      individual.fitness = individual.score.to_f / total * size
    end
  end
end

Explication du code

Ce qui nous intéresse se passe dans la méthode score. Tout d’abord on calcule la valeur totale et le poids total du sac à dos:

    individual.chromosome.each_with_index do |item, index|
      if item
        value += Knapsack::ITEMS[index].value
        weight += Knapsack::ITEMS[index].weight
      end
    end

Je rappelle qu’un chromosome est ici un Array de booléens, d’où la ligne if item pour savoir si l’objet est présent ou non.

Une fois valeur et poids calculés, on peut donner un score:

    if weight > @capacity
      individual.score = 0
    else
      individual.score = value
    end

Si le poids du sac à dos dépasse sa capacité, on invalide l’individu en mettant son score à zéro, ce qui lui interdira par la suite de se reproduire. Sinon, le score est simplement la valeur totale du sac à dos.

La prochaine fois on mettra en place la sélection, le croisement, la mutation, etc…

À demain.