itérations multiples de la sélection de tournoi dans l'algorithme génétique

Question

Hé les gars, je suis un peu confus au sujet de la façon dont fonctionnent les multiples itérations de la sélection de tournois.

Je sais que vous commencez à sélectionner des paires aléatoires (ou k membres) et à mettre le gagnant dans un pool d'accouplement. Vous continuez à le faire jusqu'à ce que la piscine d'accouplement soit remplie.

Cependant, je ne suis pas sûr de ce qui se passe après. Est-ce que nous commençons simplement à accoupler aléatoirement ceux qui sont dans le groupe d'accouplement?

Et puis redémarrez le processus de sélection en choisissant des paires aléatoires de la nouvelle génération?

Merci.

Answer 1

Traditionnellement, après la découverte des gagnants du tournoi, ils forment la prochaine génération. Tous les processus de mutation, de sélection, etc. continuent après cela en cycles.

Answer 2

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

Pour la piscine d'accouplement, cela dépend du type de personnes que vous recherchez, des solutions que vous recherchez, et si vous avez un moyen de combiner les individus d'une manière, il y a de meilleures chances qu'ils produisent un meilleur individu.

Vous pouvez utiliser l'accouplement aléatoire, mais cela vous donnera les «pires» solutions - pire parce que vous n'avez aucune idée si elles vont produire un meilleur individu ou non. Ce sera toujours une bonne solution, et quand j'ai commencé à écrire ces algorithmes, j'ai toujours utilisé l'accouplement aléatoire, mais immédiatement après avoir obtenu un nouvel individu à partir de 2 anciens, j'ai comparé la performance du 3, et je me suis retrouvé 2 parents parfois (et rejeter l'enfant de 1 seconde), ou se retrouver avec 1 parent et 1 enfant. Mais pour être plus efficace, ET si vous savez comment combiner les individus pour qu'ils produisent une meilleure solution (et cela peut être très compliqué), vous pouvez utiliser une fonction d'affinité, qui prend 2 individus et retourne une affinité entre eux. La partie difficile est de déterminer l'affinité. Selon le problème, cela peut être très différent. Par exemple, si je prends le problème du vendeur itinérant, j'ai trouvé les meilleures solutions lors de l'accouplement individuel avec moins de similitude. Donc, ma fonction d'affinité a renvoyé 1 - similarité. De cette façon, je pourrais réduire de 80% le nombre d'itérations et obtenir de très bonnes solutions. Mais gardez à l'esprit que plus votre piscine est grande, plus la fonction d'affinité sera longue à exécuter - les fonctions d'affinité peuvent être O (n²), ou même O (n³), auquel cas cela peut être le goulot d'étranglement de votre algorithme. Dans ce cas, il peut être préférable d'utiliser l'accouplement aléatoire. En conclusion, l'accouplement aléatoire est bon - après tout, nous pouvons dire que cela fonctionne de cette façon dans la vraie vie - mais si vous savez comment calculer une affinité entre deux individus, vous pouvez l'utiliser pour réduire le nombre de les itérations dont vous aurez besoin pour obtenir une bonne solution. Gardez à l'esprit que l'affinité informatique peut être très complexe (et je suppose même que le calcul des meilleures affinités pour un pool donné est NP-complet).

Answer 3

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

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

Faites ce que vous voulez. Vous pouvez les muter tous ... ou vous pouvez jumeler chaque paire que vous choisissez dans le tournoi. Utilisez celui qui fonctionne le mieux. Sois créatif.Comme quelqu'un d'autre sur ce forum l'a souligné: Le petit secret des AG est que c'est plus de l'art que de la science.

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