Comment savons-nous que la prochaine génération sera meilleure?

J'ai récemment découvert les algorithmes génétiques dans cet article de MSDN , dans lequel il les appelle évolution combinatoire, mais il semble que ce soit la même chose et j'ai du mal à comprendre comment la combinaison de deux solutions potentielles produira toujours une nouvelle solution au moins aussi efficace. bon que ses parents.

Pourquoi cela est-il ainsi? Associer pourrait peut-être produire quelque chose de pire.

Autant que je sache, l'algorithme est basé sur le concept selon lequel lorsqu'un mâle et une femelle d'une espèce produisent une progéniture, cette progéniture aura les caractéristiques des deux parents. Certaines combinaisons seront meilleures, certaines pires et d'autres tout aussi bien. Celles qui sont meilleures (quelle que soit la définition de "meilleure" est appropriée) ont plus de chances de survivre et de produire des enfants présentant les caractéristiques améliorées. Cependant, il y aura des combinaisons plus faibles. Pourquoi n'est-ce pas un problème avec GA?

Un algorithme génétique tente de s'améliorer à chaque génération en éliminant la population. Chaque membre est évalué en fonction d'une fonction de mise en forme et seule une partie des plus performantes est autorisée à se reproduire.

Vous avez cependant raison: rien ne garantit que la prochaine génération améliorera le score de son prédécesseur.

Pensez au programme de belette de Dawkins : "faire évoluer" la chaîne "Methinks it is like a weasel". En partant d'une population de chaînes aléatoires, la fonction fitness évalue la correspondance textuelle la plus proche, qui est perturbée pour produire la génération suivante. Avec une reproduction croisée simple, deux chaînes très performantes combinées pourraient très facilement produire une progéniture moins performante. Même une mutation aléatoire "asexuée" d'une seule corde de bonne condition physique pourrait nuire à la bonne forme physique de l'enfant.

Je pense que cela vaut la peine de noter que ce n’est pas nécessairement un défaut. Avec ce type de recherche, il y a l'idée de maxima locaux . Un membre de la population peut représenter une solution qui n’est pas un résultat optimal, mais qui constitue le meilleur résultat possible sans s’aggraver.

Imaginez que la fonction de mise en forme du programme weasel ne trouve pas seulement la distance d'édition, mais qu'elle ait une certaine notion de «mot» et teste si le dernier mot de la chaîne est le nom d'un animal. Tous les noms d’animaux donnent de bons résultats, mais "weasel"obtiennent un gros bonus.

Maintenant que se passe-t-il si "Methinks it is like a walrus"est évolué? Cela marque bien. Pas aussi bien que la chaîne cible ultime, mais meilleure que d' "Methinks it is like a walrut"autres variations proches qui pourraient être atteintes par une seule étape de mutation.

La chaîne de morses est un maximum local, et la recherche peut rester bloquée à moins que le programme ne permette au score de la génération suivante d’être pire.

Nous ne savons pas que ça va aller mieux, nous savons que ça ne va pas empirer.

À chaque génération, ne consiste pas seulement en l’ospring des meilleurs éléments, mais comprend également les meilleurs éléments eux-mêmes - des clones si vous voulez. Comme ils sont toujours présents, ils marqueront le même résultat qu'avant. Ce qui signifie que si aucun des produits ne sont meilleurs, les gagnants des générations précédentes gagneront à nouveau - et seront mutés / reproduits.

Considérez: avec un progéniteur étant une lettre, par exemple A un enfant muté étant défini en ajoutant un numéro, par exemple A1, des solutions croisées écrites avec des crochets entourant le parent, par exemple, (A1B2) et le noyau de forme de tout individu écrit après celui-ci - plus élevé étant meilleur[12]

Pour la démonstration, considérons un pool de 5, où nous conservons le meilleur 2. et remplissons avec 1 mutate de chaque, plus un croisement

Génération 1

• A [dix]
• B [5]
• C [4]
• D [3]
• E [1]

Gardez A, Bcar ce sont les deux meilleurs, et remplissez les 3 autres slots avec leurs descendants

Génération 2

• A [dix]
• B [5]
• (AB) [7]
• A1 [12]
• B1 [4]

Gardez A, et (AB), comme ils sont les meilleurs 2 - Cela signifie que grand-père Asera toujours dans la piscine car la plupart des enfants travaillent plus faible

Génération 3

• A [dix]
• (AB) [12]
• (A(AB)) [14]
• A2 [8]
• (AB)1 [13]

Gardez (AB)1et (A(AB))- cette fois, aucun grand-parent n'a été maintenu, car deux de leurs enfants les ont battus. Mais si (AB1)a légèrement ont effectué pire que nous aurions continué à la (AB)place.

Cela continue jusqu'à ce que le score se stabilise. Ce qui indique que vous avez atteint une sorte de maximum local (potentiellement un maximum global). Une des raisons pour lesquelles cela serait détecté serait que les mêmes individus continuent à être "clonés" dans la génération suivante. (mais pour les problèmes de grandes dimensions qui peuvent prendre trop de temps, alors mieux vaut peut-être simplement vérifier l'amélioration <une tolérance particulière)

En général, les algorithmes génétiques créent un certain nombre de variations (aléatoires) des parents à chaque génération. Ensuite, une fonction de sélection est appliquée et la progéniture la plus adaptée en fonction de cette fonction survit. La progéniture n'est donc pas nécessairement meilleure car la variation est aléatoire, mais combinée à la sélection, vous obtenez une amélioration dans le temps.

Quand j'ai étudié les algorithmes génétiques au collège, cela a été expliqué ainsi:

Imaginez une solution comme une combinaison de "gènes", dans laquelle chaque gène affecte la qualité de la solution dans son ensemble. Lorsque deux solutions sont couplées, leurs gènes sont choisis au hasard dans chaque parent.

Maintenant, si le gène conduit généralement à une bonne solution, sa fréquence dans le pool de gènes augmente. Dans les cas extrêmes, le gène dominera la population.

Ainsi, lorsque vous pensez aux algorithmes génétiques (et à l'évolution en général), vous ne devez pas penser aux individus. Vous devriez penser aux gènes et aux populations dans leur ensemble. Même si une "meilleure" solution est perdue, cela ne signifie pas que ses gènes sont perdus.

Il existe également une idée d'élitisme dans les algorithmes génétiques. Cela signifie que les meilleures solutions sont toujours conservées d'une génération à l'autre. Cela pourrait accélérer la convergence de l'algorithme, mais il est plus facile pour cet algorithme de rester bloqué dans les optima locaux.

Les algorithmes GA ne sont pas déterministes, ils ne garantissent pas une amélioration à chaque génération et ils ne garantissent pas non plus de trouver un optimum total. Cependant, la phase de sélection d'une AG, utilisant une fonction de mise en forme, rend plus probable la survie des "bonnes solutions".