Xavier Nayrac

Rubyiste accro au TDD, serial blogger, apprenti data scientist, heureux utilisateur de Vim, accordéoniste.
Si vous vous sentez particulièrement généreux, suivez moi sur Twitter.

Les algorithmes génétiques démystifiés 43: Économie, la population

| Comments

Niveau : intermédiaire

Après avoir vu dernièrement l’énoncé du problème d’investissement que je me propose de résoudre à l’aide d’un algorithme génétique, on peut maintenant créer la population initiale.

Je me base sur le programme développé pour le problème du sac à dos disponible sur Github. Par contre, le code nécessite la version 2.1 de Ruby (disponible en preview2 à l’heure où j’écris ces lignes).

Tout d’abord la classe Individual, qui recueille toutes les informations sur nos individus: chromosome, score et fitness.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Individual

  class << self
    def random(items)
      new(nil, items)
    end

    def from_chromosome(chromosome)
      new(chromosome)
    end

    def listing(chromosome:, items:)
      chromosome.map.with_index do |gene, index|
        "#{gene} #{items[index].name}"
      end.join("\n")
    end
  end

  attr_accessor :score, :fitness
  attr_reader :chromosome

  def initialize(chromosome = nil, items = nil)
    if chromosome
      @chromosome = chromosome
    else
      @chromosome = []
      items.each_with_index do |item, index|
        @chromosome << rand(0..item.number)
      end
    end
  end
  private_class_method :new

  def >(other)
    return true if other.nil?
    score > other.score
  end
end

J’ai ajouté une méthode de classe listing:

1
2
3
4
5
def listing(chromosome:, items:)
  chromosome.map.with_index do |gene, index|
    "#{gene} #{items[index].name}"
  end.join("\n")
end

Elle utilise les arguments nommés requis de Ruby 2.1 et prend en paramêtre un chromosome et la liste des actions (Knapsack::ITEMS, voir l’article précédent). Elle servira à afficher la liste des actions, avec le nombre retenu pour chacune d’entres elles à la fin de l’algorithme.

Dans la méthode initialize, on peut voir comment je crée les chromosomes de la population initiale:

1
2
3
4
5
6
else
  @chromosome = []
  items.each_with_index do |item, index|
    @chromosome << rand(0..item.number)
  end
end

items se réfère à la liste des actions (Knapsack::ITEMS). Un chromosome est une liste de la même taille que items. Chaque gène (ou emplacement dans la liste) est un nombre compris entre zéro et le nombre maximum d’actions pour cette action particulière (voir encore une fois Knapsack::ITEMS).

Maintenant, pour la création de la population proprement dite, il n’y a rien de nouveau:

1
2
3
4
5
6
7
8
9
class Population < Array
  def initialize(items, population_size)
    population_size.times { self << Individual.random(items) }
  end

  def best
    self.sort_by{|individual| individual.score}.last
  end
end

La prochaine fois on verra l’évaluation…

À demain.

Articles connexes

Commentaires