Programmation génétique expliquée : comment les machines apprennent à écrire leur propre code

Peut-être que le « Saint Graal » de l'informatique aura été découvert le jour où nos machines pourront écrire leurs propres programmes. La programmation génétique (PG) est un paradigme d'apprentissage automatique relativement nouveau représentant une étape dans cette direction.

La PG tient une grande promesse dans le domaine de l'ingénierie de contrôle. Dans cet article, nous discuterons de ce qu'est la programmation génétique, comment elle peut être représentée, et examinerons un exemple de programme.

Cet article est le premier d'une série. Pour passer aux entrées suivantes, sélectionnez-en une ci-dessous :

• Opérateurs génétiques dans les algorithmes évolutionnaires
• Exemples d'algorithmes génétiques : faire évoluer un programme de tri et une régression symbolique
• Applications et limites de la programmation génétique

Programmation génétique et algorithmes génétiques

La PG est essentiellement une variation de l'algorithme génétique (AG) conçu à l'origine par John Holland. Comme un AG, la PG est un algorithme évolutionnaire s'appuyant sur des opérateurs génétiques tels que la reproduction proportionnelle à l'adaptation, le croisement et la mutation pour faire avancer une population de programmes encodés, ou « individus », à travers des générations successives vers une solution.

Cependant, contrairement à un AG, qui utilise généralement un encodage de chaîne de bits de longueur fixe, la PG emploie une représentation arborescente de taille variable d'un programme réel. Par conséquent, le résultat d'une exécution de PG réussie produit un programme informatique qui, lorsqu'il reçoit une entrée appropriée et est exécuté, produit le résultat souhaité.

Nichael Cramer et John Koza sont crédités pour avoir posé les fondations de la PG. John Koza (qui détient également un brevet sur la PG) a effectué une quantité significative de recherche sur la PG et son livre phare, « Genetic Programming », est considéré comme l'œuvre séminale sur le sujet. La recherche actuelle a démontré quelques succès encourageants de la PG dans une large gamme d'applications, y compris la navigation robotique, l'acquisition de stratégies de jeu, l'analyse de régression symbolique et les systèmes de contrôle.

Représentation de la programmation génétique

La représentation arborescente mentionnée précédemment est centrale au thème de la PG car pratiquement tout programme informatique peut être représenté de cette façon. En pratique, un langage fonctionnel tel que LISP est bien adapté à cette forme et il est facile de voir comment une S-expression LISP peut être diagramée comme un arbre (Figure 1).

Vous trouverez ci-dessous trois représentations distinctes de la même information :

Un fragment de programme simple :
BEGIN
IF a < b THEN a := a + 1 ELSE b := b * b
c := a * b * 2;
END


Équivalent LISP :
(progn (if (a < b)
  (setq a (+ a 1))
  (setq b (* b b))
  )
  (setq c (* (* a b) 2))
)

Les nœuds intérieurs de l'arbre consistent en des fonctions tandis que les nœuds feuilles consistent en des terminaux. Les fonctions doivent avoir un nombre d'arguments (communément appelé arité) d'au moins un, leur permettant d'être connectées à d'autres fonctions ou terminaux, fournissant ainsi la « colle » pour les branches à l'intérieur de l'arbre.

Les terminaux incluent généralement des choses telles que des constantes et des variables. Puisque les terminaux forment les feuilles de l'arbre, ils ont toujours une arité de zéro. Vous êtes tenu de choisir l'ensemble des fonctions et terminaux pour le problème que vous tentez de résoudre. Par exemple, les fonctions logiques ET, OU et NON et les terminaux X1 et X2, représentant deux variables d'entrée booléennes, sont appropriés si vous tentez de découvrir un programme capable de synthétiser la fonction booléenne XOR. Une fonction d'adaptation est également requise car vous devez fournir les moyens pour qu'un programme soit mesuré par rapport à un autre dans le sens où l'un est meilleur pour résoudre un problème donné.

Par exemple, dans le cas XOR, nous pouvons tester l'adaptation d'un programme en exécutant le programme une fois pour chaque cas d'adaptation correspondant aux quatre entrées booléennes possibles pour X1 et X2 (0 0, 0 1, 1 0, 1 1) et en additionnant le nombre de réponses correctes (0, 1, 1, 0) respectivement, pour chaque cas de test.

Évidemment, un programme produisant un score parfait de quatre est considéré comme une solution au problème XOR, comme montré dans le Listing 1.

Une solution parfaite au problème XOR découverte par la PG :
(defun program ()
  (AND (OR X1 X2)
  (NOT (AND X1 X2) )
  )
)

Prochain : Opérateurs génétiques

Dans le prochain article, nous examinerons les opérateurs génétiques qui rendent les algorithmes évolutionnaires possibles. Nous les utiliserons également dans un exemple d'algorithme plus complexe.

Lectures suggérées

• Kinnear, Jr., K. E. (éd.). Advances in Genetic Programming. Cambridge, Mass. : The MIT Press, 1994.
• Knuth, D. E. The Art of Computer Programming, Volume 3, Sorting and Searching. Reading, Mass. : Addison-Wesley, 1973
• Koza, J. R. Genetic Programming. Cambridge, Mass. : The MIT Press, 1992.
• Koza, J. R. Genetic Programming II. Cambridge, Mass. : The MIT Press, 1994.
• Montana, D. J. « Strongly Typed Genetic Programming. » BBN Technical Report #7866, mai 1993.
• Mitchell, Melanie, An Introduction to Genetic Algorithms, The MIT Press, 1998.