Itérations multiples de sélection du tournoi en algorithme génétique

Question

Hé les gars, je suis un peu confus au sujet de la façon dont plusieurs itérations des travaux de sélection du tournoi.

Je sais que vous commencez à sélectionner des paires aléatoires (ou des membres de k) et mettre le gagnant dans une piscine d'accouplement. Vous continuez le faire jusqu'à la piscine d'accouplement est rempli.

Cependant, je ne sais pas ce qui se passe par la suite.

Est-ce que nous venons de commencer l'accouplement au hasard ceux qui dans la piscine d'accouplement? Et puis relancer le processus de sélection en choisissant des paires aléatoires de la nouvelle génération?

Merci.

Answer 1

Traditionnellement, après les gagnants du tournoi se trouvent, ils forment la prochaine génération. Tous les processus de mutation, sélection, etc continuer après dans les cycles.

Answer 2

J'ai écrit beaucoup de ces algorithmes génériques, au point que je fait un cadre pour éviter d'écrire le même code encore et encore.

Pour la piscine d'accouplement, cela dépend du genre de personnes que vous cherchez, les solutions que vous recherchez, et si vous avez un moyen de combiner les individus d'une manière, il y a une meilleure chance qu'ils vont produire un meilleure personne.

Vous pouvez utiliser l'accouplement au hasard, mais cela vous donnera les solutions « pire » - pire parce que vous ne savez pas si elles produiront une meilleure personne ou non. Il sera toujours de bonnes solutions, et quand je commencé à écrire ces algorithmes j'ai toujours utilisé l'accouplement au hasard, mais immédiatement après l'obtention d'un nouvel individu de 2 anciens, je compare les performances des 3 et mis au rebut le pire, se retrouver avec la 2 parfois, les parents (et à rejeter le 1-deuxième enfant âgé), ou de se retrouver avec 1 parent et 1 enfant.

Mais pour être plus efficace, et si vous savez comment combiner les individus afin qu'ils produisent une meilleure solution (et cela peut être très difficile), vous pouvez utiliser une fonction d'affinité, qui prend 2 personnes et retourne une affinité entre leur. La partie la plus délicate est de déterminer l'affinité. En fonction du problème, il peut être très différent. Par exemple, si je prends le problème du voyageur de commerce, je suis les meilleures solutions quand personne accouplement avec moins de similitude. Donc, ma fonction d'affinité est revenu 1 -. Similitude

De cette façon, je pouvais réduire le nombre d'itérations de 80% et d'obtenir de très bonnes solutions.

Mais gardez à l'esprit que le plus grand est votre piscine, plus aura la fonction d'affinité pour exécuter - fonctions d'affinité peuvent être O (n²), ou même O (n³), dans quels cas il peut être le goulot d'étranglement votre algorithme. Dans ce cas, il peut être préférable d'utiliser l'accouplement au hasard.

En conclusion, l'accouplement aléatoire est bon - après tout, nous pouvons dire que cela fonctionne de cette façon dans la vie réelle - mais si vous savez comment calculer une affinité entre 2 personnes, vous pouvez l'utiliser pour réduire le nombre d'itérations vous aurez besoin d'obtenir une bonne solution. Gardez à l'esprit que l'affinité de calcul peut être très complexe (et je suppose même que le calcul des meilleures affinités pour une piscine donnée est NP-complet).

Answer 3

Ce n'est pas un bon conseil, mais ...

  

Cependant, je ne suis pas sûr de ce qui se passe après.

Faites ce que vous voulez. Vous pouvez les muter tous ... ou vous pouvez accoupler chaque paire que vous choisissez dans le tournoi. Utilisation selon qui fonctionne le mieux. Soyez créatif.

Comme quelqu'un d'autre sur ce forum a souligné:. Le sale petit secret à propos est que ce AGs est plus un art qu'une science

De plus, pour vraiment obtenir de bons conseils, vous aurez besoin d'une meilleure description du problème que vous voulez résoudre.