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

32

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?

Avrohom Yisroel
la source
12
However, there will be combinations that are weaker. Why isn't this an issue with GA?- Parce que les combinaisons les plus faibles sont rejetées.
Robert Harvey
6
Nous savons que la prochaine génération ne sera pas pire car nous ne jetons pas les bons mais nous rejetons les mauvais. Et il y a une chance raisonnable que combiner certains des meilleurs en fasse un meilleur, mais ce n'est pas garanti.
user253751
7
Why isn't this an issue with GA?Eh bien, c’est le cas ou plus exactement. L'un des nombreux (nombreux) paramètres à optimiser à l'aide des GA est la taille de la population: si elle est trop basse, vous pouvez ne produire que des individus plus faibles, mais si elle est trop élevée, le temps de calcul associé à la fonction fitness peut être trop élevé.
Loufylouf
3
C'est une différence entre la reproduction et le désherbage : le stade de reproduction peut (va) produire une progéniture plus mauvaise, mais le stade de désherbage va (devrait) éliminer les moins performants avant le prochain stade de reproduction.
TripeHound
Merci à tous. Si je comprends bien, c'est la façon dont il l'a formulée dans l'article qui m'a jeté hors de la piste. Il a déclaré: " Le nouvel organisme, vraisemblablement très bon, remplace un organisme pauvre ", ce qui a motivé ma question. On dirait que c'était faux :)
Avrohom Yisroel

Réponses:

43

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.

Josh Caswell
la source
1
Pertinent: youtube.com/watch?v=YT1vXXMsYak - la démonstration du programme informatique de Dawkin dure environ 12 minutes, bien que l'ensemble de la conférence mérite d'être visionnée, car elle décrit les bases théoriques de base sur lesquelles repose l'évolution (qu'elle soit biologique ou simulée). mis à la terre.
Periata Breatta
24
En effet, vous autoriserez parfois la survie d’un certain pourcentage de membres moins performants afin d’accroître la "diversité génétique", ainsi que des mutations complètement aléatoires qui ne sont basées sur aucun membre existant.
Jörg W Mittag
@ JoshCaswell Merci pour cela. Bien que toutes les réponses aient été excellentes, je vais marquer ceci comme accepté, car il couvre tout ce que j'ai demandé et quelques choses que je n'avais pas encore demandé!
Avrohom Yisroel
Heureux d'avoir pu aider, @AvrohomYisroel
Josh Caswell
6

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)

Lyndon White
la source
1
"Dans 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" Cela dépend de la mise en œuvre. Certaines implémentations ne le font pas. Cela s'appelle parfois "élitisme".
Jpmc26
4

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.

JacquesB
la source
4
Ah, on dirait que l'article était un peu trompeur. Il a déclaré: " Le nouvel organisme, vraisemblablement très bon, remplace un organisme pauvre ", ce qui m'a confondu. Je suppose que s’il combine beaucoup d’organismes, on s’attendrait globalement à une augmentation, même si les nouveaux organismes individuels pourraient être plus faibles que les précédents. Est-ce correct? Merci
Avrohom Yisroel
@ AvrohomYisroel: Exactement.
JacquesB
1
@AvrohomYisroel: Méfiez-vous de la compréhension approximative des non-spécialistes. (Aussi, méfiez-vous de la précision "mur de jargon" des spécialistes.)
Eric Towers
@ EricTowers Ouais, je vois le problème! Je pensais qu'il était un expert, à en juger par les articles précédents qu'il a écrits, mais il semble clairement avoir commis de grosses erreurs dans cet article.
Avrohom Yisroel
4

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.

Euphorique
la source
2

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".

Doc Brown
la source