Fabrication industrielle
Internet des objets industriel | Matériaux industriels | Entretien et réparation d'équipement | Programmation industrielle |
home  MfgRobots >> Fabrication industrielle >  >> Manufacturing Equipment >> Robot industriel

Une introduction à la programmation génétique :un système qui se programme tout seul ?

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

GP est très prometteur dans le domaine de l'ingénierie de contrôle. Dans cet article, nous allons discuter de ce qu'est la programmation génétique, comment elle peut être représentée et jeter un œil à un exemple de programme.

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

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

GP est essentiellement une variante de l'algorithme génétique (AG) conçu à l'origine par John Holland. Comme un GA, GP est un algorithme évolutif s'appuyant sur des opérateurs génétiques tels que la reproduction proportionnelle, le croisement et la mutation pour conduire une population de programmes codés, ou « individus », à travers les générations successives vers une solution.

Cependant, contrairement à un GA, qui utilise généralement un codage de chaîne de bits de longueur fixe, GP utilise une représentation arborescente de taille variable d'un programme réel. Par conséquent, le résultat d'une exécution GP réussie produit un programme informatique qui, lorsqu'il est correctement saisi et exécuté, produit le résultat souhaité.

Nichael Cramer et John Koza sont crédités pour avoir jeté les bases de GP. John Koza (qui détient également un brevet sur la GP) a effectué une quantité importante de recherches sur la GP et son livre phare, "Genetic Programming", est considéré comme le travail fondateur sur le sujet. Les recherches actuelles ont démontré des succès encourageants de GP dans un large éventail d'applications, y compris la navigation de robots, 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 plus haut est au cœur du thème GP car pratiquement n'importe quel programme informatique peut être représenté de cette manière. En pratique, un langage fonctionnel tel que LISP est bien adapté à cette forme et il est facile de voir comment une expression S LISP peut être schématisée sous forme d'arbre (Figure 1).

Ci-dessous, vous trouverez trois représentations distinctes des mêmes informations :

Un fragment de programme simple : COMMENCER SI a Équivalent LISP : (progn (si (a  

Figure 1. Représentation arborescente d'un programme. Notez que (progn arg1 arg2 arg3 ... argn) évalue séquentiellement chaque argument.

Les nœuds intérieurs de l'arbre sont constitués de fonctions tandis que les nœuds feuilles sont constitués de 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 au sein de l'arbre.

Les terminaux incluent généralement des éléments tels que des constantes et des variables. Puisque les terminaux forment les feuilles de l'arbre, ils ont toujours une arité de zéro. Vous devez choisir l'ensemble de fonctions et de terminaux pour le problème que vous essayez de résoudre. Par exemple, les fonctions logiques AND, OR et NOT et les bornes X1 et X2, représentant deux variables d'entrée booléennes, sont appropriées si vous essayez de découvrir un programme capable de synthétiser la fonction booléenne XOR. Une fonction fitness est également requise puisque vous devez fournir les moyens pour qu'un programme soit mesuré par rapport à un autre dans le sens où l'on est meilleur pour résoudre un problème donné.

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

De toute évidence, un programme donnant un score parfait de quatre est considéré comme une solution au problème XOR, comme indiqué dans le Listing 1.

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

Suite :Opérateurs génétiques

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

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.

Robot industriel

  1. Programmation du microprocesseur
  2. Qu'est-ce que la programmation système embarquée et ses langages
  3. Qu'est-ce que le langage de programmation C ? Bases, Introduction, Histoire
  4. Fonctions en programmation C avec exemples :récursif et en ligne
  5. Un système de refroidissement passif peu coûteux qui ne nécessite aucune alimentation
  6. Comment mettre en œuvre un programme d'apprentissage en fabrication
  7. Heidenhain lance un programme de formation CNC en ligne
  8. Les 5 outils qui font prospérer la fabrication au plus juste
  9. Signe que mon équipement hydraulique a besoin d'être réparé