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 17: Orienté Objet

| Comments

Niveau : intermédiaire

Il est temps de donner du code orienté objet, non ? C’est ce à quoi je vais m’attacher dans cet article et les quelques qui suivront. Après ça, je pense qu’on pourra en finir avec le paradoxe du singe savant et passer à quelque chose de plus intéressant.

Aujourd’hui on voit la création de la population selon le paradigme OO. Il nous faut d’abord pouvoir créer un individu:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Individual
  def self.random(chromosome_size)
    new(nil, chromosome_size)
  end

  def self.from_chromosome(chromosome)
    new(chromosome)
  end

  attr_accessor :score, :fitness
  attr_reader :chromosome

  def initialize(chromosome = nil, chromosome_size = nil)
    if chromosome
      @chromosome = chromosome
    else
      @chromosome = ""
      chromosome_size.times { @chromosome += Gene.random }
    end
  end
  private_class_method :new
end

Il y a deux manières de créer un individu. Lors de l’initialisation de la population, on utilisera Individual.random avec la taille du chromosome. Lors d’un accouplement, on utilisera Individual.from_chromosome avec le chromosome résultant des parents. On note aussi les deux attributs score et fitness. Je ne vais pas m’étaler sur le score, 1 point par lettre bien placée, voilà, vous avez compris. Par contre fitness demande quelques explications puisque c’est la première fois que j’emploie ce terme, pourtant courant en algorithme génétique.

Fitness signifie aptitude. Quand le score mesure la performance d’un individu face à un problème, le fitness mesure un individu par rapport à son environnement, c’est à dire ici par rapport à la population. Il n’y a rien de nouveau, on a déjà fait ça quand on normalisait les scores et qu’on les transformaient en pourcentage (ou en fraction). Jusqu’ici j’étais resté vague en parlant seulement d’évaluation et je profite du code d’aujourd’hui pour introduire cette notion de fitness.

La production d’un gène est assurée par la classe Gene, qui ne demande pas d’explications:

1
2
3
4
5
6
7
class Gene
  @@genes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ "

  def self.random
    @@genes[rand(@@genes.size)]
  end
end

Il reste à concevoir la population:

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

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

La population étant basiquement une liste d’objets Individual, il me semble logique d’hériter de Array. J’ai prévu une méthode best qui permettra d’afficher la progression de l’algorithme et qui pourra aussi servir pour la condition d’arrêt du programme quand individual.score sera égal à la taille de la chaîne recherchée.

Demain ce sera au tour de l’évaluation d’être transformée en code objet.

À demain.

Articles connexes

Commentaires