Algorithmes évolutifs: décomposition optimale de la repopulation

Question

Tout est vraiment dans le titre, mais voici une ventilation pour tous ceux qui s’intéressent aux algorithmes évolutifs:

Dans une évaluation environnementale, le principe de base est de générer de manière aléatoire un certain nombre d’organismes (qui ne sont en réalité que des ensembles de paramètres), de les exécuter contre un problème, puis de laisser les plus performants survivre.

Vous repeupler ensuite avec une combinaison de croisements des survivants, de mutations des survivants, ainsi qu'un certain nombre de nouveaux organismes aléatoires.

Faites cela plusieurs milliers de fois, et des organismes efficaces apparaissent.

Certaines personnes font également des choses comme introduire plusieurs "îlots". des organismes, qui sont des populations séparées qui sont autorisés à se croiser de temps en temps.

Ma question est donc la suivante: quels sont les pourcentages optimaux de repopulation?

Je garde les 10% les plus performants et repeuple avec 30% de croisements et 30% de mutations. Les 30% restants sont destinés aux nouveaux organismes.

J'ai également essayé la théorie des îlots multiples et vos résultats à ce sujet m'intéressent également.

Il n’est pas perdu de vue que c’est exactement le type de problème qu’une EE pourrait résoudre. Savez-vous que quelqu'un a essayé cela?

Merci d'avance!

Answer 1

J'ai d'abord essayé de modéliser ce que je pensais des systèmes organiques. Finalement, nous avons décidé que cela n’était pas bon et que nous sommes devenus plus agressifs, avec 10% de patients conservés, 20% mutés, 60% croisés et 10% aléatoires.

Ensuite, j'ai remarqué que mes 10% les plus performants étaient à peu près identiques. J'ai donc augmenté le hasard à 30%. Cela a aidé certains, mais pas beaucoup.

J'ai essayé plusieurs îles, ainsi que le saut de génération, et le réensemencement, ce qui a donné de meilleurs résultats, mais reste très insatisfaisant, très peu de variation dans le nombre de générations les plus élevées (10%) pour obtenir des résultats. Le code a surtout appris à pirater mon évaluation de la condition physique.

Il est très facile d’obtenir les meilleurs résultats, alors ne vous inquiétez pas de ne pas en garder trop. Les métissages aident à réduire les traits positifs et négatifs, ils sont donc utiles, mais ce que vous voulez obtenir, c’est vraiment beaucoup de bonnes races aléatoires. Concentrez-vous sur les mutations et les nouveaux aléas pour apporter des fonctionnalités, et laissez les métis et les plus performants surveillez simplement les meilleurs et affinez-les plus lentement. IE: les choses basées sur la dernière génération ne font que trouver de meilleurs maxima locaux, les randoms trouvent de meilleurs maxima globaux.

Je continue de croire que des réponses optimales à votre question peuvent être trouvées en observant des phénomènes naturels, comme dans un article récent concernant le caractère aléatoire des trajectoires de vol des mouches des fruits, de sorte que les résultats puissent être évités.

La meilleure solution est probablement de le lancer et de l’ajuster, n’ayez pas peur de l’ajuster assez fort, les populations sont robustes. Assurez-vous de mettre en place un moyen de sauvegarder et de continuer.

Answer 2

Les meilleures ressources que j'ai trouvées pour GA et EA étaient les livres de John Koza sur la programmation génétique . . Il aborde le sujet en profondeur - techniques d'encodage du génome, mutation aléatoire, reproduction, réglage de la fonction de mise en forme.

Personnellement, je n’ai écrit qu’une petite poignée de simulateurs à des fins pédagogiques. Ce que j’ai trouvé, c’est que la manière dont j’ai ajusté ces pourcentages était liée aux particularités de la fonction de mise en forme que j’utilisais, au nombre de mutations aléatoires que j’avais introduites et à la façon «intelligente» que j’avais essayé de faire de la mutation et de la reproduction. «intelligent», j'ai essayé de transformer le mutateur et la logique de croisement, plus la population améliorait rapidement son score de condition physique - j'ai également constaté que j'avais été trop conservatrice quant à la probabilité de mutation - mes premiers essais ont atteint des maxima locaux et mal à en sortir.

Rien de tout cela ne vous donne de réponses concrètes, mais je ne pense pas qu’il en existe, l’AG est imprévisible de par sa nature et le réglage de ce type de paramètres peut encore être un art. Bien sûr, vous pouvez toujours essayer une méta-AG, en utilisant ces paramètres comme un chromosome, en recherchant les paramètres qui produisent une forme plus rapide dans l’AG de base que vous utilisez.

Cela dépend de la méta que vous souhaitez obtenir.

Answer 3

C’est un sujet controversé (dans la littérature et Melanie, et al livres ) qui semble être très spécifique à un domaine. Ce qui fonctionne pour un problème d’un type à n paramètres ne fonctionnera presque jamais pour un autre problème, un autre domaine ou un autre ensemble paramétrique.

Alors, comme suggéré par TraumaPony, modifiez-le vous-même pour chaque problème que vous résolvez ou écrivez quelque chose pour l’optimiser à votre place. La meilleure chose à faire est de garder trace de tous vos "tournants de potentiomètres". et peaufiner vos expériences pour vous permettre de tracer le terrain de la solution et de vous faire une idée de la façon d’optimiser rapidement dans cet espace. Essayez également des techniques alternatives telles que l’escalade afin d’avoir une ligne de base à battre.

@Kyle Burton: Les taux de croisement par rapport aux taux de mutation sont également constamment débattus dans chaque classe. des problèmes remis aux AG et aux généralistes.

Answer 4

En supposant que vous disposiez d’une méthode pour quantifier les X% d’exécutants, nous suggérons de ne pas utiliser un seuil codé en dur mais d’analyser la répartition des performances et d’en faire votre seuil quelque part dans la gamme des premières baisses majeures de performances, et ensuite, accordez vos croisements, mutations et nouveaux organismes pour combler les lacunes. De cette façon, si vous avez un très "productif" " courir dans lequel beaucoup de variations ont réussi, vous ne jetez pas un nombre significatif de performants. De plus, si vous avez un message "non productif" Si vous courez, vous pouvez éliminer davantage d’organismes existants au profit d’organismes plus récents qui devraient prendre leur place.

Answer 5

J'ai eu un certain succès en augmentant la diversité de la population en créant des mutations et des croisements à partir de quelques gènes des chromosomes parents.

Cela fonctionne jusqu'à ce que le taux de mutation tombe à zéro. comme il est probable qu’il y aura une pression évolutive périodique pour le faire, vous devez essayer de vous assurer que ces gènes ont un taux minimum.

En pratique, j'ai opté pour un génotype à plusieurs chromosomes. Un chromosome a été codé pour la fonction de reproduction de l'autre. Le «chromosome de reproduction», plus petit, présentait des taux fixes raisonnables de mutation et de croisement.

J'ai constaté que cela arrêterait le plateau classique et la convergence de la population.

En passant, j’ai tendance à faire des croisements et des mutations pour chaque enfant.

Pour les assemblées générales de générations, j’essaie d’éviter complètement l’élitisme, mais lorsque je suis peuplé de plusieurs îles, je garde la plus haute élite de chaque île. Lorsque les îles se rejoignent, toutes les élites peuvent se reproduire ensemble.

Answer 6

Il semble y avoir quelques réponses suggérant l’utilisation d’une 2e AG pour déterminer les paramètres optimaux pour la 1ère AG, sans mentionner la manière de déterminer les paramètres optimaux pour la 2ème. Je ne peux m'empêcher de m'interroger sur les croyances religieuses de ceux qui suggèrent cette approche ...

Answer 7

Comme d'autres l'ont mentionné, la combinaison optimale dépendrait de votre problème spécifique et d'autres facteurs spécifiques tels que la taille de l'espace de la solution.

Avant de discuter de l'évolution de l'évolution d'une génération à l'autre, il est important de prendre en compte la taille de chaque génération. Mon approche consiste généralement à partir d'une population relativement importante (environ 100 000 à 500 000 personnes) d'individus assez diversifiés, ce que Koza suggère dans certains de ses travaux. Pour obtenir cette diversité dès le départ, vous pouvez diviser l’espace de votre solution en compartiments, puis vous assurer qu’au moins un certain nombre de personnes tombe dans chaque compartiment. (Par exemple, si vous avez une représentation arborescente pour chaque individu, veillez à créer des quantités égales de profondeur 2, 3, ..., max_depth.)

En ce qui concerne votre question, il n’existe pas de façon claire de l’aborder, mais en fonction de votre problème, vous souhaiterez peut-être mettre l’accent sur le caractère aléatoire ou le minimiser. Lorsque vous souhaitez le souligner, vous devez garder moins d'individus intacts et introduire un nombre plus élevé de nouveaux individus aléatoires. Vous aimerez généralement procéder de la sorte s’il existe de nombreux maximums locaux dans votre espace solution et que vous souhaitez effectuer une recherche plus large.

Lorsque vous obtenez une ventilation, vous devez prendre en compte un certain nombre d'éléments, notamment la duplication (un grand nombre d'individus identiques ou nouvellement identiques dans la partie supérieure de la consanguinité). Pour réduire cela, vous pouvez parcourir votre population d’une génération à l’autre et remplacer les doublons par de nouveaux individus aléatoires ou croisés.

Cela dit, mon approche actuelle consiste à conserver les 1% supérieurs, à croiser les 20% supérieurs en un nouveau 20%, aux 40% supérieurs dans les 20% suivants, à croiser les 90% supérieurs pour générer les 20% suivants. et générer aléatoirement le reste (39%). S'il y a des doublons, je les enlève et les remplace par de nouveaux individus aléatoires.

Je n’utilise pas de mutations car le nombre élevé d’individus aléatoires doit permettre d’ajouter des "mutations". lors du croisement suivant.

Answer 8

Vous savez ce que vous pouvez faire ... Vous pouvez écrire un algorithme génétique pour déterminer cette distribution optimale.

Mais, en général, je conserve les 12% de croisements supérieurs et 28%; avec 30% chacun pour les autres.