Aujourd'hui, j'ai lu cette entrée de blog par Roger Alsing sur la façon de peindre une réplique de la Mona Lisa à l'aide de seulement 50 semi transparent polygones.
Je suis fasciné par les résultats pour ce cas particulier, donc je me demandais (et c'est ma question): comment fonctionne la programmation génétique de travail et quels sont les autres problèmes pourraient être résolus par la programmation génétique?
Il y a débat quant à savoir si Roger Mona Lisa programme de la Programmation Génétique à tous. Il semble plus proche de l'une (1 + 1) Stratégie d'Évolution. Les deux techniques sont des exemples du domaine plus large de Calcul Évolutionnaire, qui comprend également les Algorithmes Génétiques.
La Programmation génétique (GP) est le processus de l'évolution des programmes d'ordinateur (généralement sous la forme d'arbres - souvent des programmes Lisp). Si vous demandez spécifiquement sur les GP, John Koza est largement considéré comme l'expert de premier plan. Son site web comprend de nombreux liens vers plus d'informations. GP est généralement très gourmand en ressources (pour les non-trivial problèmes, il s'agit souvent d'une grande grille de machines).
Si vous demandez plus généralement, les algorithmes évolutionnaires (Ae) sont généralement utilisés pour fournir bonne approximation des solutions à des problèmes qui ne peuvent être résolus facilement en utilisant d'autres techniques (comme NP-dur de problèmes). De nombreux problèmes d'optimisation entrent dans cette catégorie. C'est peut-être trop de calcul intensif pour trouver une solution exacte, mais parfois une quasi-optimale solution est suffisante. Dans ces situations, l'évolution des techniques peut être efficace. En raison de leur nature aléatoire, l'évolution des algorithmes ne sont jamais garantis pour trouver une solution optimale pour n'importe quel problème, mais ils vont souvent de trouver une bonne solution s'il en existe un.
L'évolution des algorithmes peut également être utilisé pour traiter les problèmes que les humains ne sais vraiment pas comment le résoudre. Un EA, libre de tout être humain, des idées préconçues ou des préjugés, peut générer des solutions surprenantes qui sont comparables, voire meilleurs, que les meilleurs d'origine humaine efforts. Il est simplement nécessaire que nous pouvons reconnaître une bonne solution si elle est présentée à nous, même si nous ne savons pas comment faire pour créer une bonne solution. En d'autres termes, nous devons être en mesure de formuler une efficace de la fonction de fitness.
Quelques Exemples
EDIT: Le gratuitement livre, Un Guide de Terrain pour la Programmation Génétique, contient des exemples de cas où le GP a produit de l'homme-concurrentiel des résultats.
Curieusement, la société derrière le caractère dynamique d'animation utilisé dans les jeux comme Grand Theft Auto IV et le dernier Star Wars (The Force Unleashed) utilisé programmation génétique à développer le mouvement des algorithmes. Le site de la société est ici et les vidéos sont très impressionnants:
http://www.naturalmotion.com/euphoria.htm
Je crois qu'ils ont simulé le système nerveux du personnage, puis randomisés les connexions dans une certaine mesure. Ils ont ensuite combiné les 'gènes' des modèles qui marchait plus à créer de plus en plus en mesure "enfants" dans les générations successives. Vraiment fascinant travail de simulation.
J'ai aussi vu des algorithmes génétiques utilisées dans le chemin d'accès de trouver des automates, avec recherche de nourriture des fourmis étant l'exemple le plus classique.
Les algorithmes génétiques peuvent être utilisés pour résoudre la plupart de tout problème d'optimisation. Cependant, dans beaucoup de cas, il y a de mieux, de plus en plus directe des méthodes pour les résoudre. Il est dans la classe de méta-programmation d'algorithmes, ce qui signifie qu'il est capable de s'adapter à peu près tout ce que vous pouvez jeter à elle, étant donné que vous pouvez générer une méthode de codage d'une solution possible, la combinaison et la mutation des solutions, et de décider des solutions qui sont mieux que d'autres. GA a un avantage sur les autres méta-programmation d'algorithmes en ce qu'il peut gérer les maxima locaux de mieux qu'une pure d'escalade de l'algorithme, comme le recuit simulé.
J'ai utilisé de la programmation génétique dans ma thèse de simuler l'évolution des espèces basée sur le terrain, mais c'est bien sûr l'Une-vie de l'application des algorithmes génétiques.
Les problèmes de GA sont bons sont l'escalade des problèmes. Le problème, c'est que normalement c'est plus facile à résoudre la plupart de ces problèmes par la main, à moins que les facteurs qui définissent le problème est inconnue, en d'autres termes vous ne pouvez pas réaliser que la connaissance de quelque chose, dire des choses liées avec les sociétés et les communautés, ou dans les situations où vous avez un bon algorithme, mais vous avez besoin d'affiner les paramètres, ici, GA sont très utiles.
Une situation de réglage fin, j'ai fait était pour affiner plusieurs Othello, l'IA basée sur les mêmes algorithmes, donnant à chacun des styles de jeu différents, rendant ainsi chaque adversaire unique et avec ses propres particularités, puis je les ai eu en concurrence pour choisir le top 16 de l'IA que j'ai utilisé dans mon jeu. L'avantage était qu'ils étaient tous de très bons joueurs de plus ou moins égale compétence, il était donc intéressant pour l'adversaire humain parce qu'ils ne pouvaient pas deviner l'IA aussi facilement.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
