Qu'est-ce qui empêche la programmation génétique?

Question

J'ai fait une bonne quantité de travail avec les algorithmes génétiques avec beaucoup de succès jusqu'à présent ignoré de la programmation génétique. Autant que je sache, la plupart des programmes écrits par des programmeurs, et je suis curieux de savoir quelle est la tenue de la programmation génétique de retour?

Quelques explications possibles j'ai pensé à:

1. L'espace de recherche est tout simplement trop grand pour trouver des programmes utiles, parmi le bruit
2. La plupart des applications réelles, ne peut pas fournir suffisamment de données pour permettre l'évaluation de l'aptitude d'un tel espace.
3. Il est difficile de réduire l'efficacité de beaucoup de véritable applications de vers le bas à une seule mesure de remise en forme. En d'autres mots, l'écriture d'une fonction de remise en forme adapté serait probablement entraîner la même quantité de travail que l'écriture du programme.

Des idées?

Answer 1

C'est quelque chose que je considère que dans mes propres recherches, et je dirais qu'il ya de nombreuses raisons:

1. La grande majorité de la recherche dans le GP de terrain a porté sur la production de formules plutôt que le type de logiciel qui est produit par la plupart des programmeurs. Il y a beaucoup de chercheurs en informatique dans le domaine, mais très peu sont concentrés sur la production de programmes que vous attendez, de sorte que les progrès ont été lents dans ce domaine.

2. Il y a une importante plus l'accent sur l'utilisation de LISP, car il peut produire de nice arbre structures qui sont faciles à manipuler et malheureusement impératif programmes ont été négligés parce qu'ils impliquent la résolution des problèmes des problèmes. Pour le GP d'être pris au sérieux par les programmeurs, c'est de produire des programmes impératifs.

3. De véritables programmes contiennent des boucles, mais les boucles sont difficiles à mettre en GP, sans toutes sortes de laid contraintes pour éviter boucle infinie.

4. Programmation génétique n'est pas à l'échelle. C'est bien pour des petits problèmes, avec une petite langue disponible, mais comme vous le dites dans votre premier point de l'espace de recherche devient trop volumineux très rapidement.

5. Par rapport à un programmeur humain, GP peut être très lent. Il est cependant très parallelisable est donc susceptible de bénéficier sensiblement plus grand nombre de cœurs de processeur devenir la norme.

Une autre solution valable serait qu'il est difficile de faire confiance à un code a été généré automatiquement. C'est vrai, mais en pratique, je doute que cela a beaucoup d'impact parce que GP n'est pas en mesure de produire le bon type de programmes dans la première place.

Answer 2

La partie la plus difficile sur la programmation génétique est l'écriture d'une bonne fonction de notation:

• La fonction de notation doit juger correctement si l'algorithme a les propriétés souhaitées. C'est plus difficile qu'il n'y paraît, beaucoup plus difficile que d'écrire une suite de tests. L'algorithme peut s'adapter à tout caprice de votre fonction de notation et de l'optimiser. En essayant d'évoluer strcmp? Votre algorithme peut, au lieu de découvrir un modèle mathématique de la longueur de votre pass/fail de cas de test.

• La fonction de notation doit être capable de juger si l'algorithme de test est partiellement de travail. Programmation génétique s'appuie sur "l'escalade". Un petit bénéfique mutation des besoins à cause d'un minuscule amélioration progressive dans la partition. Si votre pointage fonction de sortie type vrai/faux, alors vous êtes à la recherche de façon aléatoire, pas génétiquement.

Si vous essayez votre main à elle, vous trouverez que la programmation génétique est le summum de la pensée latérale: Votre programme aura tendance à résoudre le problème dans tous les sens, vous ne pensez pas, la plupart d'entre eux inattendu et (pour les applications sérieuses) probablement inutile. Une célèbre affaire de la tentative d'évoluer un oscillateur à l'aide de composants électroniques élémentaires. Il a été jugé sur la simplicité du circuit et si la sortie a oscillé. Il a produit quelque chose d'aussi simple que les chercheurs ont assurer qu'il n'arrivait pas à travailler, mais il l'a fait: Il a été ramasser et à en amplifier les ondes radio à partir de l'environnement.

Edit de citer:

Graham-Rowe, Duncan. "Radio émerge de l'électronique, de la soupe." Le New Scientist, vol.175, no.2358, p.19 (31 août 2002). Disponible en ligne à http://www.newscientist.com/news/news.jsp?id=ns99992732

Cependant, le lien semble maintenant être brisé.

Nouveau lien est http://www.newscientist.com/article/dn2732-radio-emerges-from-the-electronic-soup.html

Answer 3

Je sais je suis en retard pour cette partie, mais je voudrais juste faire un couple de points. J'ai eu l'incroyable chance de travailler avec John Koza sur sa Programmation Génétique 4 livre.

Le genre de programmation que la plupart d'entre nous faisons au jour le jour - accrochage GUI événements, poussant pixels, bases de données, etc etc sont certainement pas le type de programmes que GP a pour objectif de construire.

Ce que John Koza fait avec son cluster d'une centaine de machines (si je me souviens bien!) est à la recherche de solutions à des problèmes intéressants (pensez à un problème NP-difficile). C'est triste, mais la plupart des problèmes que nous programmeurs travaillent au jour le jour ne sont pas très intéressant, ou à des problèmes difficiles, surtout juste irritant et beaucoup de temps.

Ce que Ben Jackson dit à propos d'un génétiquement modifiés oscillateur électronique est la chose la plus proche dans ce fil de ce que le Dr Koza et de l'équipe de le faire. Il existe de nombreux exemples de circuits dans le GP de la série de livres.

Ce que Tom Château dit ici à propos de programmes impératifs n'est pas exactement vrai. Le séminal exemple de ce à partir de John et de l'entreprise est la conception de l'antenne exécuter. Il est à peu près un 3d logiciel de dessin avec des commandes telles que le LOGO de dessin de la langue qui conçoit une antenne. Il a moveto, lineto type de commandes pour pousser et éclater de matrices sur une pile. Le GP paquet j'ai juste regardé la semaine dernière, jgap, a l'appui direct: un conteneur de type non-terminal en question qui peut contenir de retour void déclarations et ensuite on a une instruction de retour à la fin. Je crois qu'il a même quelque chose comme des variables locales si je n'ai pas regarder de trop près.

L'original LISP de la conception que le début de GP s'exécute centrée autour de est une sorte de douleur de temps en temps, c'est certainement vrai. C'est quelque chose d'un rite de passage, je pense que d'être gêné à propos de la traduction de la sortie d'un GP exécuter en plus utilisable code.

TL;DR: GP n'est pas vraiment une programmation automatique du système. C'est un système automatisé de l'invention du système.

Answer 4

Je dirais 1. et 3.

En ce qui concerne plus particulièrement le point 3, je dirais que dans la plupart des cas, il est encore plus facile d’écrire le programme lui-même que de définir une fonction cible appropriée et de vérifier que cela conduit à la solution correcte ou acceptable (comment savez-vous que un algorithme dérivé de la programmation génétique fonctionne comme prévu?)

En ce qui concerne le point 1, je dirais que l’espace de recherche a un nombre infini de dimensions.

Answer 5

Trois choses:

1. Comme André dit, il est très difficile d'écrire une fonction de fitness que c'est suffisant. C'est la version ultime de Développement Piloté par les tests. Vous devriez écrire des tests unitaires qui fournissent 100% de couverture d'un comme-encore-non écrites programme. Même alors, une couverture de 100% par lui-même est peu probable d'être suffisant. Lorsque nous avons résolu le problème de façon formelle précisant le précise le comportement de tous les aspects d'un système complexe, et puis vérifier qu'un programme satisfait à la spécification, alors nous pourrions avoir une chance.
2. La Programmation génétique est non-déterministe et mieux adaptée à la génération approximative des solutions plutôt que des solutions exactes.
3. Programmation génétique, lorsqu'il est appliqué à un problème de complexité raisonnable, est extrêmement gourmand en ressources. En 1999, la Programmation Génétique Inc a été à l'aide de 1 000 nœud de cluster pour leur travail sur le terrain.