Depuis que je sais que Flash MX 2004 est iminent, je ne code pratiquement plus, car je n'ai pas envie de refaire la même chose en ActionScript 2. Donc je me renseigne sur les techniques de programmation, et notamment sur certains algorithmes.

J'ai découvert au travers de quelques articles sur le web la puissance des algorithmes génétiques, et je compte bientôt en faire une implémentation dans Flash. Voici donc ce que j'en ai compris :

Les algorithmes génétiques sont une solution à utiliser lorsque l'on a aucun moyen de déterminer la solution d'un problème de manière "classique". Une manière "classique" de résoudre un problème peut être d'avoir l'équation d'une solution par exemple. Dans ce cas précis, la solution sera trouvée au bout d'un temps donné. Le problème du "voyageur de commerce" est un bon contexte pour l'utilisation des alogrithmes génétiques.

Le concept des algorithmes génétiques est basé sur la théorie de l'évolution et de la sélection naturelle ennoncé par Darwin. Il consiste à créer une population "d'individus", puis d'effectuer sur cette population des croisements et des mutations aléatoires, puis d'évaluer quels sont les individus qui se rapprochent le plus de la solution cherchée, et d'éliminer ceux qui s'en éloignent le plus. On recommence alors les croisements, sur un nombre donné de générations.
Implémenter un algorithme génétique se fait donc en plusieurs étapes :


  • Créer un codage génétique : trés souvent, il s'agit d'une chaine de caractères représentants les différents "gènes".
  • Créer une méthode d'évaluation : pour évaluer le rapprochement du code génétique par rapport à la solution recherchée. Plus l'évaluation est important, plus l'individu est proche de la solution.
  • Créer une méthode de croisement : cette méthode va retourner un individu descendant de deux autres individus.
  • Créer une méthode de mutation : cette méthode va opérer une mutation sur un gène de l'individu. Elle a une probabilité peu importante de se faire.
  • Imposer une condition de fin : par exemple, "pas plus de 10 générations" ou "les deux meilleurs sont les mêmes depuis 5 générations"

Les modes de séléction pour les croisements sont multiples :

  • On croise les individus pris au hasard.
  • On croise entre eux les meilleurs individus (stratégie élitiste)
  • On choisit toujours le meilleur individu que l'on croise avec un autre pris au hasard (variante de l'élitisme)
  • On croise les parents proches de par leur évaluation.

Une fois que tout cela est fait, on crée une population aléatoire, et on lance la première série de reproduction entre des individus pris au hasard, jusqu'à ce que la condition de fin soit remplie. Et voila !!! :D

Quelques liens qui m'ont servi :


Maintenant, je vais me pencher sur les réseaux de neurones (un ordinateur capable d'apprendre, ca me laisse sans voix).