Algorithmes génétiques

Comment s'en servir ?

Modélisation

Lorsque l'on cherche à résoudre un problème complexe en utilisant des AG, la partie la plus difficile est la modélisation. Comment passe-t-on d'un problème concret à des gènes et des individus ? Nous vous proposons ici de prendre un exemple sur un problème mathématique :

On définit une fonction f(x1, x2, x3, …, xn) = x1 * x2 + x3 - … / xn, la fonctionf applique une suite d'opérateurs (choisis en début d'algorithme) aux paramètres qui lui sont passés.

Le résultat que l'on veut obtenir est f(x1, x2, x3, …, xn) = 10000.

On cherche alors les valeurs de x1, x2, x3, …, xn pour obtenir ce résultat.

On voit rapidement ici qu'avec des algorithmes "classiques", il serait difficile de trouver efficacement une solution au problème, dans un temps raisonnable.

Comment modéliser le problème ?

Tout d'abord, que cherche-t-on ? Il faut bien déterminer ce que l'on cherche, ici c'est une ou plusieurs combinaisons de valeurs. Ensuite, on définit la population, les individus, les gènes : dans notre exercice, il apparaît que les individus sont les différentes combinaisons de valeurs (ce sont les solutions potentielles) qui forment notre population. Ensuite, chaque valeur est comme un gène qui va s'exprimer lorsqu'il est appliqué à la fonction.

Les opérateurs

Il convient alors de définir les opérateurs qui nous permettront de mettre en oeuvre un algorithme génétique. Nous verrons ces opérateurs sont relativement simples :

• Evaluation

  On calcul de f(x,y,z,…) avec les opérandes de la fonction puis on compare le résultat obtenu par rapport au résultat attendu

• Sélection

  On ne retient que les meilleurs solutions en les triant, plus on est proche du résultat attendu, meilleure est la combinaison. On ne retiendra par exemple que la moitié des individus.

• Croisement

  On pose le fait que deux individus "parent" donnent deux individus "enfant" et le croisement a pour effet : le début d’une combinaison devient le début de l’autre en coupant aléatoirement.

• Mutation

  On modifie une des valeurs de certaines suites de manière aléatoire.

On voit ici qu'il serait simple de coder ces fonctions qui serviraient d'opérateurs à notre algorithme. Voici un exemple en pseudo code de ce que pourrait être notre algorithme de résolution :

générer population
Pour i de 0 a nb_essai_max{
  pour tous les individus{
    evaluer(individu)
  }	
  Si meilleur_individu == resultat_attendu{
    arret
  }
  sélectionner(population)
  croiser(population)
  muter(population)
}