Explorer la puissance et les limites des algorithmes génétiques

À ce stade de la série sur la programmation génétique (PG), nous avons appris ce qu'est la programmation génétique et comment elle représente l'information, comment les opérateurs génétiques fonctionnent dans les algorithmes évolutionnaires, et nous avons travaillé sur l'évolution d'un programme de tri par régression symbolique.

Ici, nous examinerons de haut niveau ce que cette technologie peut accomplir à mesure qu'elle se développe.

Considérations pratiques de la programmation génétique

Pour comprendre ce dernier chapitre de notre série, rappelons-nous l'exemple XOR que nous avons discuté dans la première partie de cette série :

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

Regardons également l'exemple de régression symbolique de l'article précédent :

Approximation polynomiale de sin(x) dans l'intervalle (0 <= x <= pi/2)

(defun program ()
  (+ (* (* (* X X) X)
  (* 0.2283 -0.6535))
  X)
)

Simplifiant le programme ci-dessus, on obtient l'équation équivalente suivante :

polysin(x) = -.1492 x3 + x

Résultats :

x	sin(x)	polysin(x)
0.000	0.000	0.000
0.078	0.077	0.077
0.156	0.155	0.155
0.234	0.231	0.232
0.312	0.306	0.307
0.390	0.380	0.381
0.468	0.451	0.452
0.546	0.519	0.521
0.624	0.584	0.587
0.702	0.645	0.650
0.780	0.703	0.709
0.858	0.756	0.763
0.936	0.805	0.813
1.014	0.848	0.858
1.092	0.887	0.897
1.170	0.920	0.931
1.248	0.948	0.957
1.326	0.970	0.978
1.404	0.986	0.991
1.482	0.996	0.996
1.560	0.999	0.993

Remarquez que les deux exemples, XOR et régression symbolique, renvoient une seule valeur lorsqu'ils sont évalués.

Cette caractéristique n'a pas besoin d'être une restriction, car il est certainement possible qu'une fonction ou un terminal ait un effet de bord lors de son exécution. C'est souvent le cas pour le programme de tri, qui contient une fonction avec l'effet de bord potentiel d'échanger une paire d'éléments dans un vecteur. En pratique, il est courant que des effets de bord soient présents. D'autres exemples d'effets de bord utiles sont l'affectation d'une variable à une autre ou le changement de direction vers laquelle un robot fait face.

Notre ensemble de fonctions peut inclure des fonctions conditionnelles qui donnent aux programmes évolués la capacité de prendre des décisions. Les fonctions conditionnelles évaluent sélectivement leurs arguments. Par exemple, considérons une fonction, d'arité trois, telle que (if arg1 arg2 arg3). La fonction est évaluée en évaluant le premier argument et si le résultat est vrai, le second argument est évalué ; sinon, le troisième argument est évalué. Des constructions itératives sont également possibles, car une fonction peut évaluer l'un de ses arguments plusieurs fois. Une complexité supplémentaire est introduite, cependant, par la nécessité de limiter le nombre d'itérations et le niveau d'imbrication afin d'éviter une situation où l'évaluation d'un individu prendrait un temps excessivement long. Des travaux ont été réalisés pour permettre des formulations récursives, bien que le succès dans ce domaine ait été quelque peu limité.

Bien que les résultats des systèmes PG tendent à être des programmes de type LISP, un système PG n'a pas besoin d'être implémenté en LISP. De nombreux systèmes sont implémentés en C ou C++. Une représentation linéarisée de l'arbre de programme peut être employée et la surcharge de la mémoire dynamique ainsi que la collecte de déchets coûteuse peuvent être évitées. L'efficacité de la fonction d'adaptation mérite une attention particulière car c'est souvent un goulot d'étranglement en raison du grand nombre de fois où elle est invoquée au cours de chaque génération. Un excellent article discutant de diverses techniques d'implémentation peut être trouvé dans Advances in Genetic Programming (cité dans la section Lectures suggérées ci-dessous).

Comme dans d'autres paradigmes d'apprentissage automatique, tels que les réseaux de neurones, le potentiel de surapprentissage des données d'entraînement (cas de test PG) existe. Le surapprentissage peut se produire lorsque la solution « mémorise » efficacement les données, ne fournissant guère plus qu'une table de recherche élaborée. Un moyen simple d'atténuer cet effet est d'utiliser un facteur de parcimonie. Un facteur de parcimonie est généralement une petite fraction multipliée par le nombre de nœuds dans l'arbre de programme, dont le résultat est incorporé dans la fonction d'adaptation. L'idée est de récompenser les solutions plus petites, présumément plus générales. De plus, vous êtes encouragé à utiliser des techniques de plan d'expériences appropriées. Par exemple, si vous tentez de développer un modèle de prédiction, il est judicieux de restreindre l'évaluation de l'adaptation à un sous-ensemble des données disponibles. Ainsi, les données restantes peuvent mesurer la performance prédictive du modèle résultant.

Comme c'est le cas avec les algorithmes évolutionnaires, la PG ne garantit pas de trouver une solution exacte ni même une solution acceptable. Les résultats peuvent varier considérablement d'une exécution à l'autre. Souvent, le processus converge prématurément vers un minimum local. La performance dépend fortement de la complexité du problème, de sa représentation caractérisée par le choix des fonctions et terminaux, et des propriétés de la fonction d'adaptation.

Applications de la programmation génétique

La programmation génétique a été appliquée avec succès à des problèmes dans des domaines tels que :

• Conception de circuits
• Optimisation combinatoire
• Systèmes de contrôle
• Ajustement de courbes / analyse de régression
• Compression de données
• Prévision économique / modélisation financière
• Acquisition de stratégies de jeu
• Induction de séquences mathématiques
• Conception de réseaux de neurones
• Reconnaissance de formes et classification
• Génération de nombres aléatoires
• Navigation robotique
• Intégration et dérivation symboliques
• Conception tridimensionnelle

Orientations futures pour la programmation génétique

Selon la complexité du problème, plusieurs exécutions de PG peuvent être nécessaires pour trouver une solution acceptable, si tant est qu'on puisse en trouver une. Idéalement, nous aimerions que la PG « monte en charge » à mesure que la complexité du problème augmente. Trouver de bonnes façons d'atteindre cet objectif est un domaine de recherche actif. Comme en programmation conventionnelle, la notion de construction de représentations de niveau supérieur via des sous-routines est une façon d'aborder ce problème. Dans Genetic Programming II, Koza discute des méthodes qui peuvent découvrir des sous-routines réutilisables et présente des résultats qui soutiennent la capacité de programmes hiérarchiques et modulaires à résoudre des problèmes plus complexes.

Comme nous l'avons vu, la PG couple les caractéristiques d'auto-organisation de l'algorithme génétique avec la puissance de représentation et la généralité des S-expressions. L'élégance de cette approche simplifie la spécification du problème à celle de fournir une fonction d'adaptation spécifique au domaine et un ensemble approprié de fonctions et terminaux. Applicable à une gamme diversifiée de problèmes, la PG continue d'être un terrain fertile pour la recherche.

Encore à ses débuts, de futures percées pourraient nous mener un pas plus près de ce Saint Graal des systèmes capables d'écrire leurs propres programmes.

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.