Applications et limitations des algorithmes génétiques

À ce stade de la série de programmation génétique (GP), 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 avons travaillé à faire évoluer un programme de tri par régression symbolique.

Ici, nous examinerons de haut niveau ce que cette technologie peut accomplir au fur et à mesure de son développement.

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

Pour comprendre ce dernier chapitre de notre série, rappelons-nous d'un exemple XOR dont nous avons parlé dans la première partie de cette série :

Une solution parfaite au problème XOR découvert par GP : (programme défun () (ET (OU X1 X2) (PAS (ET X1 X2)) ) ) 

Liste 1. Résultat XOR.

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

Une approximation polynomiale de sin(x) dans l'intervalle (0 <=x <=pi/2) (programme défun () (+ (* (* (* X X) X) (* 0,2283 -0,6535)) X) ) En simplifiant le programme ci-dessus, on obtient l'équation équivalente suivante :polysine(x) =-.1492 x
3
 + x Résultats :

x	sin(x)	polysine(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

Liste 4. Régression symbolique.

Notez que le XOR et les exemples de régression symbolique présentés ici 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 secondaire lors de son exécution. C'est souvent le cas pour le programme de tri, qui contient une fonction avec l'effet secondaire potentiel d'échanger une paire d'éléments dans un vecteur. En pratique, il est courant que des effets secondaires soient présents. Quelques exemples supplémentaires d'effets secondaires utiles sont l'attribution d'une variable à une autre ou la modification de la direction dans laquelle un robot fait face.

Notre ensemble de fonctions peut inclure des fonctions conditionnelles qui permettent aux programmes évolués de prendre des décisions. Les fonctions conditionnelles évaluent sélectivement leurs arguments. À titre d'exemple, considérons une fonction, avec une arité de 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 deuxième argument est évalué; sinon, le troisième argument est évalué. Les constructions itératives sont également possibles, car une fonction peut évaluer plusieurs fois l'un de ses arguments. Une complexité supplémentaire est cependant introduite 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 peut prendre un temps excessivement long. Certains travaux ont été effectué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 GP aient tendance à être des programmes de type LISP, un système GP n'a pas besoin d'être implémenté dans LISP. De nombreux systèmes sont implémentés en C ou C++. Une représentation linéarisée de l'arborescence du programme peut être utilisée et la surcharge de mémoire dynamique ainsi qu'une récupération de place coûteuse peuvent être évitées. L'efficacité de la fonction fitness mérite une attention particulière car elle constitue 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 de mise en œuvre peut être trouvé dans Advances in Genetic Programming (cité dans la section Suggestions de lecture ci-dessous).

Comme dans d'autres paradigmes d'apprentissage automatique, tels que les réseaux de neurones, le potentiel de surajustement des données d'entraînement (cas de test GP) existe. Un surapprentissage peut se produire lorsque la solution « mémorise » efficacement les données, fournissant ainsi un peu plus qu'une table de consultation élaborée. Un moyen simple d'aider à réduire cet effet consiste à 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 du programme, dont le résultat est incorporé dans la fonction de fitness. L'idée est de récompenser des solutions plus petites, vraisemblablement plus générales. De plus, vous êtes encouragé à utiliser des techniques de conception expérimentale appropriées. Par exemple, si vous essayez de développer un modèle de prédiction, il est judicieux de restreindre l'évaluation de la forme physique à un sous-ensemble des données disponibles. De cette façon, les données restantes peuvent mesurer les performances prédictives du modèle résultant.

Comme c'est le cas avec les algorithmes évolutionnaires, GP n'offre aucune garantie de trouver une solution exacte ou même une solution acceptable. Les résultats peuvent varier considérablement d'un essai à l'autre. Souvent, le processus converge prématurément vers un minimum local. Les performances dépendent fortement de la complexité du problème, de sa représentation telle que caractérisée par le choix des fonctions et des terminaux, et des propriétés de la fonction de fitness.

Applications pour la programmation génétique

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

• Conception de circuits
• Optimisation combinatoire
• Systèmes de contrôle
• Ajustement de courbe/analyse de régression
• Compression des données
• Prévisions économiques/modélisation financière
• Acquisition de stratégie de jeu
• Induction de séquences mathématiques
• Conception de réseaux de neurones
• Reconnaissance et classification de modèles
• Génération de nombres aléatoires
• Navigation robotique
• Intégration et différenciation symboliques
• Conception en trois dimensions

Orientations futures pour la programmation génétique

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

Comme nous l'avons vu, GP couple les caractéristiques d'auto-organisation de l'algorithme génétique avec le pouvoir 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'aptitude spécifique au domaine et une fonction appropriée et un ensemble de terminaux. Applicable à un large éventail de problèmes, la médecine générale continue d'être un terrain fertile pour la recherche.

Encore à ses balbutiements, les futures percées pourraient nous conduire un peu plus loin vers ce Saint Graal des systèmes capables de créer leurs propres programmes.

Lecture suggérée

• Kinnear, Jr., K. E. (éd.). Progrès de la programmation génétique . Cambridge, Massachusetts :The MIT Press, 1994.
• Knuth, D. E. L'art de la programmation informatique, volume 3, tri et recherche . Reading, Massachusetts :Addison-Wesley, 1973
• Koza, J.R. Programmation génétique . Cambridge, Massachusetts :The MIT Press, 1992.
• Koza, J.R. Programmation génétique II . Cambridge, Massachusetts :The MIT Press, 1994.
• Montana, D.J. « Programmation génétique fortement typée ». Rapport technique BBN n° 7866, mai 1993.
• Mitchell, Melanie, Une introduction aux algorithmes génétiques , The MIT Press, 1998.