Programmation génétique [fermé]

Récemment, je parcourais Reddit et suis tombé sur un post reliant à un exemple "d'algorithme génétique JavaScript". J'ai été vraiment fasciné par les concepts d'algorithmes génétiques et de programmation, mais même après quelques recherches sur Google, je suis toujours légèrement confus. Comment ça marche?

Je suppose que les termes de vocabulaire me déroutent plus que toute autre chose. J'apprécierais de brefs exemples et peut-être des explications. Juste le concept de programmation génétique et comment je pourrais l'implémenter dans mes projets et pourquoi?

On dirait que vous parlez plus des algorithmes génétiques que de la programmation génétique, mais voici ma contribution à votre compréhension.

Il peut être utile de penser aux AG en termes de parties qui les composent.

Supposons donc que vous ayez une sorte de problème. La première chose dont vous avez besoin est un moyen d'exprimer à quoi ressemblera une solution. Si vous avez eu un problème de vendeur itinérant avec les villes A, B, C, D, E, vous savez déjà à quoi pourrait ressembler une solution, un tableau des noms des villes [B, C, A, D, E].

Ceci est le gène .

Autrement connu comme une solution potentielle au problème. Comme Steven A. Lowe le mentionne, les chaînes de bits sont un moyen courant d'encoder les gènes, mais ce n'est pas nécessaire; cela rend simplement certaines choses plus faciles. La partie importante est que vous avez un moyen de représenter une solution de cette manière semblable à un tableau.

Maintenant. Comment savoir si la solution est bonne? Vous avez besoin d'une fonction qui peut vous dire et évaluer la solution. Donc, encore une fois pour TSP, vous pourriez avoir une fonction qui mesure la distance parcourue en utilisant le chemin [B, C, A, D, E]. La «note» que vous attribuez pourrait simplement être la distance parcourue, mais dans des problèmes plus complexes, vous pourriez inclure des choses comme le coût du voyage et d'autres choses.

Il s'agit de la fonction Fitness .

Alors maintenant, vous pouvez prendre une solution potentielle et savoir si elle est bonne. Et après?

Ensuite, nous devons démarrer notre première génération. Nous générons donc un tas de solutions aléatoires. Peu importe qu'ils soient bons ou non. Il s'agit de votre population initiale ou de départ. Vous pouvez appeler cela votre pool génétique.

Vous prenez donc votre pool génétique initial et vous leur appliquez votre fonction de fitness et vous leur donnez tous une note. Vous devez maintenant en prendre deux et en faire une nouvelle population - pour la prochaine génération. Qui choisissez-vous? Eh bien, vous ne voulez pas nécessairement sélectionner uniquement la forme la plus adaptée, cela peut entraîner des problèmes. Au lieu de cela, vous avez besoin d'une fonction de sélection .

Une façon de sélectionner ce qui est facile à visualiser est d'utiliser une sorte de roue: chaque gène est une tranche sur une roue, et leur score de fitness indique la taille de leur tranche (meilleure est la fitness, plus grande est la tranche). Mettez une épingle pointant vers la roue et faites-lui tourner (c.-à-d. Générer un nombre aléatoire). L'épingle pointe vers le premier parent. Recommencez pour le deuxième parent.

Maintenant, vous devez créer de nouveaux enfants. Vous voulez combiner les parents pour produire une nouvelle population. Il existe différentes façons de le faire, mais elles sont toutes appelées la fonction de croisement . Vous pouvez les diviser en deux et échanger les moitiés entre les parents, ou faire une sorte d'entrelacement. Ceci est très analogue aux parents de mammifères qui produisent de nouveaux enfants -> ils apportent tous deux leurs gènes au nouvel enfant.

Une fois que vous avez cette nouvelle génération, vous lancez une mutation aléatoire, mais rare , à chaque enfant. J'ai souvent vu des taux de mutation se produire à moins de 1%. La fonction de mutation changera au hasard quelque chose dans votre gène codé. Si votre gène est une chaîne de bits, il pourrait échanger un peu, s'il s'agit d'un tableau de villes, il pourrait échanger 2 villes de la liste. La partie importante est que c'est un événement relativement rare et qui mélange les choses.

Répétez ce processus jusqu'à un nombre de générations souhaité, ou jusqu'à ce que votre fonction de fitness produise des parents avec des scores de fitness constamment élevés et que vous ayez une solution qui (espérons-le, si vous avez tout fait correctement) est optimale.

C'était un peu verbeux, alors permettez-moi de résumer avec une métaphore:

1. Les gènes sont des gens: les gens résolvent les problèmes
2. Les fonctions de fitness sont des notes: les gens obtiennent une note en fonction de la façon dont ils résolvent un problème
3. Vous sélectionnez 2 personnes pour élever une nouvelle population: vous donnez aux personnes ayant de meilleures notes de meilleures chances de reproduction
4. Lorsque les parents se reproduisent, ils se combinent pour produire des enfants.
5. Vous mutez rarement et aléatoirement leurs enfants
6. Vous notez les enfants de la nouvelle population
7. Rincer et répéter

J'espère que cela t'aides.

encoder une solution à un problème sous forme de chaîne de bits

écrire une fonction (appelée fonction "fitness") qui évalue à quel point la solution encodée est "bonne" et reçoit une chaîne de bits - le résultat est généralement un nombre compris entre 0 et 1

générer au hasard un tas de ces chaînes binaires et évaluer leur forme physique

choisissez une partie du groupe - généralement les plus adaptées - et coupez-les en deux et échangez les moitiés pour créer de nouvelles chaînes de bits (crossover)

puis parfois, retournez au hasard quelques bits dans certaines des nouvelles chaînes de bits (mutation)

répéter jusqu'à ce qu'une bonne solution évolue

pourquoi faire: certains problèmes ont d'énormes espaces de solution possibles, si grands que l'évaluation de toutes les possibilités n'est pas pratique (cf Problème du voyageur de commerce)

Je recommande fortement le livre Algorithmes génétiques dans la recherche, l'optimisation et l'apprentissage automatique

La programmation génétique est un moyen pour les ordinateurs d'écrire des programmes pour vous!

Ne pensez pas aux "programmes" comme MS Word, pensez aux "programmes" comme suit:

function(x){ return x*2; }

Cette fonction (ou programme), en soi, n'a pas de raison d'exister. Nous recherchons des solutions aux problèmes. Si vous avez besoin de trouver la somme de deux nombres, il vous suffit d'ouvrir la calculatrice et de faire le calcul. Et si quelqu'un vous donnait le tableau suivant et vous demandait de comprendre la relation entre resultet xet y:

x   y   result
99  1   (3.02)
79  88   2.01 
21  62   5.01 
84  52  (6.58)
12  70   5.54 
67  18   0.73 

Ces données sont vos données de "formation". Votre ordinateur utilisera ces données pour générer des hypothèses, puis vous les testerez par rapport aux données réelles.

Supposons que vous ne connaissiez pas les statistiques et décidez que ce problème est trop difficile à résoudre par vous-même, vous obtiendrez donc l'ordinateur pour le comprendre pour vous.

Demandez à l'ordinateur de générer au hasard des suppositions

Vous avez l'ordinateur générer un million de réponses, et voyez si l'un d'eux colle (devinez ... un million de fois!). Voici un exemple de quelques suppositions:

function(x,y){ return x+y; } // wrong
function(x,y){ return x/1*1*1*1*1*1+y; } //wrong, silly

Vous le savez peut-être ou non, mais les fonctions ou les programmes peuvent également être représentés sous forme d'arbres, par exemple, la deuxième fonction serait:

(+ (/ x (* 1 (* 1 (* 1 (* 1 (* 1 1)))) y)

Vous pouvez le faire ressembler davantage à un arbre en l'indentant ainsi (btw, recherchez la notation polonaise inversée et la syntaxe lisp ... mais vous comprendrez pourquoi nous représentons des programmes comme celui-ci sous peu):

(+ 
    (/ x 
        (* 1 
            (* 1 
                (* 1 
                    (* 1 
                        (* 1 1)))) 
    y)

( +est au sommet avec deux "feuilles" de /et y. /lui-même a plusieurs enfants, etc.)

C'est pourquoi vous lisez tant de choses sur les «arbres» dans la programmation génétique. Dans tous les cas, nous connectons les valeurs de xet yà cette fonction et cela nous donne la mauvaise réponse. Pas étonnant cependant, car nous avons généré cela au hasard.

Vous décidez maintenant de générer un million de ces solutions. Ils ont tous tort. Cependant, vous remarquez que certaines réponses sont plus proches de la bonne réponse que d'autres. En d'autres termes, certaines solutions sont plus «adaptées» que d'autres. Notez que l'ordinateur ne sait pas ce qui est "bien" et "mal", vous devez donc fournir votre propre "fonction fitness". Cette fonction reçoit une solution potentielle, les données de formation, et est chargée d'indiquer au système GP à quel point cette solution est «adaptée». Comme vous pouvez l'imaginer, cette fonction est exécutée des millions et des millions de fois.

Ce qui rend GP différent

Voici ce qui rend la programmation génétique différente des suppositions sauvages. Vous décidez de faire une autre série de millions de suppositions; cependant, vous le faites un peu plus intelligemment. Vous prenez les 10% supérieurs des suppositions (celles qui étaient proches des valeurs réelles) et les intégrez à la deuxième génération. Vous prenez également bon nombre de ces solutions (peut-être les mêmes 10% ... je ne me souviens pas) et décidez de les «mélanger».

Vous choisissez au hasard deux solutions, choisissez au hasard des sous-arbres et commencez à les échanger. Une partie de la solution A se retrouve donc sous la solution B et vice versa - vous venez de les «croiser». Vous prenez également des solutions et vous les "mutez" simplement ... prenez un sous-arbre et "vissez-le" un peu (hé, si la solution est terrible, "visser avec elle sans raison" pourrait en fait l'améliorer).

Une bonne façon de penser est la suivante: votre maman et papa ont certains attributs - la couleur des cheveux, la taille, la probabilité de maladie, etc. Si vos deux parents étaient des athlètes olympiques, vous serez également un super athlète, non? Eh bien, les biologistes, les sociologues et même les historiens pourraient contester cette idée, mais les informaticiens ne se préoccupent pas de la moralité de l'eugénisme ici. Ils ont juste vu un "système" faire du bon travail en fournissant des solutions, alors ils ont décidé de le modéliser dans un logiciel.

Si cela ne correspond pas vraiment à la biologie, mais fournit toujours de bonnes réponses ... de nombreux informaticiens disent collectivement "quel que soit le type, et merci pour la terminologie". Notez également que tous vos frères et sœurs et pas exactement les mêmes ... même s'ils ont les mêmes parents. Chaque personne possède des gènes qui mutent pour une raison quelconque (veuillez ne pas le montrer à un biologiste, le but est de comprendre la motivation derrière une grande partie de la terminologie).

Alors maintenant, nous obtenons que l'ordinateur génère des millions de programmes et mesure leur condition physique. Les meilleures solutions survivent jusqu'à la prochaine génération. Nous «mutons» également et faisons des croisements sur la «population» (remarquez comment le langage de la génétique et de la biologie est utilisé). Une fois la deuxième génération créée, la forme physique est à nouveau mesurée. Puisque cette génération a les meilleures solutions de la génération précédente ET que nous avons croisé et muté les meilleures solutions (avec une population médiocre - pour maintenir la diversité), cette génération devrait être au moins un peu meilleure que la génération précédente.

Nous continuons cela pendant un très grand nombre de générations. Nous espérons que chaque génération fournira de meilleures solutions, jusqu'à ce que nous obtenions la bonne réponse. Par exemple:

(+ (- 2.2 (/ x 11) (* 7 (cos y))))

Eh bien regardez ça, c'est correct!
(J'ai copié ceci depuis http://en.wikipedia.org/wiki/Genetic_programming , qui a également une représentation graphique de cet arbre)

Bouts

Il y a quelques problèmes importants, comme comment décider quels "terminaux" ( +, -, *, /, cos, sin, tan) sont disponibles pour votre système GP, comment écrire la fonction fitness et comment le système gère-t-il les programmes non sensoriels tels que (1 + cos)ou (2 / "hello")(parmi beaucoup d'autres).

C'est assez ennuyeux de faire évoluer des équations. Cela devient plus intéressant si votre ensemble de terminaux ressemble à ceci: (tirer, détecter l'ennemi, se déplacer, ...) et votre fonction de fitness mesure votre santé et le nombre de cadavres de monstres martiaux.

J'ai écrit la plupart de cela de mémoire mais c'est l'idée de base. J'ai fait du GP dans mes années universitaires. Vous devriez certainement jouer avec. Ne vous inquiétez pas de comprendre toute la terminologie, téléchargez simplement des systèmes GP gratuits, parcourez quelques exemples pour vous en faire une idée et créez vos propres exemples intéressants (trouvez des relations entre différents ensembles de données, essayez de le connecter au jeu API, etc.)

Survival of the Fittest: Natural Selection with Windows Forms, c'est ainsi que j'ai découvert la programmation génétique. C'est une lecture facile avec du code disponible en téléchargement. L'inconvénient est que GP a besoin d'un moyen pour exécuter le code créé au moment de l'exécution, et au moment où l'article a été écrit, C # n'était pas bien adapté à cette tâche. C'est pourquoi l'exemple utilise CodeDOM pour générer, compiler et exécuter du code au moment de l'exécution, ce qui lui-même ajoute une autre couche de complexité.

Les choses ont changé depuis lors. .NET ayant désormais sa propre API ExpressionTree, ce qui permettrait probablement une implémentation GP plus élégante en C # que celle décrite dans l'article. Mais c'est assez bon pour comprendre comment fonctionne GP.

Ici, vous pouvez télécharger un ebook gratuit sur GP, qui comprend également un exemple de code java très court qui pourrait également vous intéresser.

Les algorithmes génétiques et la programmation génétique sont liés, mais différents concepts.

Les algorithmes génétiques (AG) sont des algorithmes de recherche de problèmes d'optimisation complexes. Dans un GA, vous encodez les paramètres d'une solution à un problème dans une chaîne de bits "ADN", puis "reproduisez" aléatoirement ces chaînes de bits: faites-les reproduire en combinant des parties d'entre elles et appliquez la "survie du plus apte" en supprimant toutes les chaînes de bits vous avez, sauf pour ceux qui sont les meilleurs pour résoudre votre problème.

La programmation génétique (GP) est encore plus compliquée: ici, vous ne représentez pas les programmes par leur ADN (chaînes de bits), mais par des arbres d'analyse que vous générez et sélectionnez.