J'ai essayé de faire beaucoup de hits en googlé avec "Circular Salesman Problem Genetic Algorithm".
Le ** problème du vendeur de patrouille ** est le problème de trouver le chemin le plus court pour revenir au point d'origine, en passant par tous les points $ N $ une fois. Le nombre total d'itinéraires passant par tous les points $ N $ et retour est de $ (N-1)! / 2 $. S'il y a 3 points, il y a un moyen. S'il y a 4 points, il y a 3 façons. S'il y a 5 points, il y a 12 façons. À mesure que le nombre de points augmente, le nombre total de routes augmentera de manière explosive. Il faut énormément de temps pour trouver le chemin le plus court parmi eux.
Cependant, si conditionnel, vous pouvez trouver l'itinéraire dans un laps de temps pratique.
Par exemple, si vous savez qu'un point est au sommet d'un polygone convexe, le chemin le plus court est ce polygone convexe. En outre, il existe diverses méthodes de recherche telles que les algorithmes génétiques, les méthodes de recuit et les cartes auto-organisées, à condition qu'elles soient ** presque ** les plus courtes.
** L'algorithme génétique ** est l'un des algorithmes de recherche pour les problèmes d'optimisation des combinaisons, et est basé sur l'évolution des organismes vivants. Puisque le problème du voyageur de commerce est également l'un des problèmes d'optimisation combinés, un algorithme génétique peut être utilisé. La procédure de recherche d'un algorithme génétique est la suivante.
L'algorithme génétique est assimilé à un organisme et est expliqué à l'aide des mots suivants.
Commentaire du laboratoire Suganuma, Université des sciences et technologies de Shizuoka Lancez-vous avec l'algorithme génétique! --SlideShare
Organisez l'algorithme génétique pour le problème du voyageur de commerce.
Soit $ p_0, p_1, \ dots, p_N $ les $ N + 1 $ points par lesquels le vendeur passe. L'itinéraire partant de $ p_0 $, passant par tous les points dans l'ordre numérique des points et retournant à $ p_0 $ peut être exprimé par $ p_0, p_1, \ dots, p_N, p_0 $. $ p_1, p_2, \ dots, p_N, p_0, p_1 $ sont des routes qui commencent le même cercle à partir de $ p_1 $. La longueur du chemin en boucle est la même quel que soit le point que vous choisissez comme point de départ, fixez donc le point de départ à $ p_0 $ et représentez l'itinéraire comme $ p_ {i_1}, \ dots, p_ {i_N} $. De plus, même si le tout est déplacé en parallèle, la longueur du chemin est la même, alors définissez $ p_0 = O $ et déplacez les autres points en parallèle. Le chemin ainsi créé est un individu.
Pour l'adaptabilité, utilisez la longueur du chemin représenté par l'individu.
Lorsque la distance entre deux points $ p, p '$ est $ d (p, p') $, la longueur de l'itinéraire $ p_ {i_1}, \ dots p_ {i_N} $ est $ d (p_0, p_ {i_1}) + d (p_0, p_ {i_N} + \ sum_ {k = 1} ^ {N-1} d (p_ {i_k}, p_ {i_ {k + 1}}) $. Plus la longueur est petite, meilleur est le parcours. Plus le nombre est élevé, meilleure est l'adaptabilité, utilisez donc l'inverse de la longueur ou l'inversion de signe. Cette fois, j'ai utilisé l'inversion de code.
Si plus la valeur est petite, meilleure est l'adaptabilité, utilisez la longueur telle quelle.
Au moment du croisement, au lieu de générer des générations enfants à partir de tous les individus de la génération parentale, la ** sélection ** est faite de sorte que plus les individus sont adaptables, plus il est facile de quitter la progéniture.
De plus, lors de la sélection des individus, plus l'adaptabilité est élevée, plus il est facile de rester dans la progéniture.
Il existe trois choix principaux. Tous ont des avantages et des inconvénients, alors utilisez-les en combinaison.
Sélectionnez par ordre décroissant d'adaptabilité. Comme il reste d'excellents individus, il converge rapidement. D'un autre côté, l'influence des individus excellents dans les premiers stades est forte, et à mesure que les générations augmentent, la diversité peut diminuer et tomber dans une impasse (= solution locale) de l'évolution.
Sélectionnez en fonction de la probabilité calculée à partir de l'adaptabilité. Les gènes à faible adaptabilité restent (bien que moins probables), donc la diversité ne diminue pas. D'un autre côté, les gènes à haute adaptabilité peuvent être rejetés et aucune solution ne peut être trouvée.
Il existe différentes manières de calculer la probabilité.
Extrayez au hasard $ n $ individus de la population et laissez celui qui a la plus grande adaptabilité. Répétez cette opération jusqu'à ce que le nombre requis d'individus soit collecté. Les gènes à faible adaptabilité restent probabilistes, donc la diversité ne diminue pas beaucoup. D'un autre côté, les gènes à haute adaptabilité peuvent être rejetés et aucune solution ne peut être trouvée.
Je présenterai deux manières d'exprimer la route (codage).
Il s'agit d'une méthode d'expression dans laquelle les numéros de points sont disposés tels quels. Les gènes sont des nombres de points $ 1, \ dots, N $. Les chromosomes sont une séquence de gènes non dupliqués, $ g_1, \ dots, g_N $. Si $ g_i = k $, cela signifie passer par $ p_k $ dans le $ i $ th. Ci-dessous, un exemple d'itinéraire passant par 5 points et son codage séquentiel.
\{ p_4, p_1, p_3, p_5, p_2 \} \rightarrow 4, 1, 3, 5, 2
Cette représentation garde toujours $ g_i \ neq g_j (i \ neq j) $.
Le codage précurseur est un nom arbitraire. Je ne connaissais pas le nom officiel.
Il s'agit d'une méthode d'expression qui utilise l'ordre de la séquence de points à l'exclusion des points passés. Le $ i $ e gène $ g_i $ prend jusqu'à $ N-i + 1 $, le nombre de points restants. Si vous avez une séquence de points $ P_1 = p_1, p_2, \ dots, p_N $, voici les étapes pour déterminer $ g_i $:
Vous trouverez ci-dessous un exemple d'itinéraire passant par 5 points et son codage ordinal.
\{ p_4, p_1, p_3, p_5, p_2 \} \rightarrow 4, 1, 2, 2, 1 \\
\begin{array}{lll}
p_1, p_2, p_3, p_4, p_5 & -, -, -, -, - &Supprimer des points tout en enregistrant la position dans la séquence\\
p_1, p_2, p_3, p_5 & 4, -, -, -, - & p_4 est le 4e\\
p_2, p_3, p_5 & 4, 1, -, -, - & p_1 est le premier\\
p_2, p_5 & 4, 1, 2, -, - & p_3 est le deuxième\\
p_2 & 4, 1, 2, 2, - & p_5 est le deuxième\\
& 4, 1, 2, 2, 1 & p_2 est le premier
\end{array}
Cette représentation garde toujours $ g_i \ le N-i + 1
Dans les organismes croisés, il est courant d'échanger des chromosomes appariés ou d'échanger des sections correspondantes entre chromosomes. De plus, il existe diverses mutations car il n'y a pas de restrictions sur la position des gènes et la longueur des chromosomes est flexible.
Étant donné que le chromosome du vendeur a des restrictions dépendant du codage, nous définissons les croisements et les mutations dans cette plage.
―― Puisqu'il y a une restriction selon laquelle chaque gène est codé une fois dans la séquence, il est nécessaire d'opérer de sorte qu'il n'y ait pas de duplication dans les chromosomes croisés (heureusement, les gens intelligents ont conçu des croisements pour les gènes ordonnés. ). En revanche, l'échange de gènes dans un chromosome est facile à décrire car il ne rompt pas les contraintes. --Pour le codage, les restrictions sont déterminées par la position du gène, il est donc plus facile d'échanger des gènes à la même position entre les chromosomes ou simplement de changer le gène, plutôt que d'échanger la position du gène. Peut être décrit.
À partir des deux chromosomes, trouvez le groupe avec la même paire de points et la même paire de positions, et échangez les groupes.
\begin{array}{cc}
Parent 1& 1\acute{2}345678 \\
Parent 2& 6\grave{7}852341
\end{array}
\rightarrow
\begin{array}{c}
1\acute{2}3456\acute{7}8 \\
6\grave{7}8523\grave{4}1
\end{array}
\rightarrow \dots \rightarrow
\begin{array}{c}
1\acute{2}3\acute{4}\acute{5}6\acute{7}8 \\
6\grave{7}8\grave{5}\grave{2}3\grave{4}1
\end{array}
\rightarrow
\begin{array}{cc}
Enfant 1& 1\hat{7}3\hat{5}\hat{2}6\hat{4}8 \\
Enfant 2& 6\hat{2}8\hat{4}\hat{5}3\hat{7}1
\end{array}
Choisissez une position aléatoire $ r $ et regardez les gènes $ {g_1} _r, {g_2} _r $ à cette position dans le parent 1 et le parent 2. Les gènes $ {g_1} _r et {g_2} _r $ sont échangés entre le parent 1 et le parent 2, respectivement. Répétez cette opération plusieurs fois pour générer les chromosomes enfant 1 et enfant 2.
\begin{array}{cc}
Parent 1& 12\acute{3}4567\grave{8} \\
Parent 2& 67\grave{8}52\acute{3}41
\end{array}
\rightarrow
\begin{array}{cc}
Enfant 1& 12\acute{8}4567\acute{3} \\
Enfant 2& 67\grave{3}52\grave{8}41
\end{array}
Le parent 1 hérite de la section aléatoire du chromosome tel quel pour l'enfant. Le parent 2 remplit les blancs en reprenant les gènes manquants chez l'enfant afin qu'ils ne soient pas en panne.
\begin{array}{cc}
Parent 1& \acute{1}\acute{2}\acute{3}|456|\acute{7}\acute{8} \\
Parent 2& 6\grave{7}\grave{8}5\grave{2}\grave{3}4\grave{1}
\end{array}
\rightarrow
\begin{array}{cc}
Enfant& \grave{7}\grave{8}\grave{2}|456|\grave{3}\grave{1}
\end{array}
Déterminez des positions aléatoires $ r_1, \ dots, r_k $ et regardez les gènes $ g_ {r_1}, \ dots, g_ {r_k} $ à ces positions dans le parent 1. Triez ces gènes $ g_ {r_1}, \ dots, g_ {r_k} $ du parent 2 dans l'ordre du parent 1 pour générer les chromosomes de l'enfant 1. Échangez le parent 1 et le parent 2 et faites de même pour générer l'enfant 2.
\begin{array}{cc}
Parent 1& 1\acute{2}3\acute{4}\acute{5}67\acute{8} \\
Parent 2& 67\grave{8}\grave{5}\grave{2}3\grave{4}1
\end{array}
\rightarrow
\begin{array}{cc}
Enfant 1& 67\acute{2}\acute{4}\acute{5}3\acute{8}1
\end{array}
Déterminez des positions aléatoires $ r_1, \ dots, r_k $. L'enfant 1 hérite des gènes $ g_ {r_1}, \ dots, g_ {r_k} $ à ces positions du parent 1. Les gènes manquants sont hérités du parent 2 de manière non ordonnée. Échangez le parent 1 et le parent 2 et faites de même pour générer l'enfant 2.
\begin{array}{cc}
Parent 1& 1\acute{2}3\acute{4}\acute{5}67\acute{8} \\
Parent 2& \grave{6}\grave{7}852\grave{3}4\grave{1}
\end{array}
\rightarrow
\begin{array}{cc}
Enfant& \grave{6}\acute{2}\grave{7}\acute{4}\acute{5}\grave{3}\grave{1}\acute{8}
\end{array}
S'il n'y a qu'un seul enfant, le passage en ordre uniforme et le passage en position uniforme sont équivalents.
Il recherche deux chromosomes pour une section dans laquelle le même ensemble de gènes est aligné et échange les sections pour générer les enfants 1 et 2.
\begin{array}{cc}
Parent 1& 1\acute{2}\acute{3}\acute{4}\acute{5}678 \\
Parent 2& 678\grave{5}\grave{3}\grave{2}\grave{4}1
\end{array}
\rightarrow
\begin{array}{cc}
Enfant 1& 1\grave{5}\grave{3}\grave{2}\grave{4}678 \\
Enfant 2& 678\acute{2}\acute{3}\acute{4}\acute{5}1
\end{array}
Les gènes sont échangés pour chaque section de deux sections sélectionnées au hasard.
\begin{array}{cc}
parent& 1|\acute{2}\acute{3}\acute{4}|56|\grave{7}\grave{8}|
\end{array}
\rightarrow
\begin{array}{cc}
Enfant& 1|\grave{7}\grave{8}|56|\acute{2}\acute{3}\acute{4}|
\end{array}
Déplace une section sélectionnée au hasard vers une autre position.
\begin{array}{cc}
parent& 1|\acute{2}\acute{3}\acute{4}\acute{5}|678
\end{array}
\rightarrow
\begin{array}{cc}
Enfant& 167|\acute{2}\acute{3}\acute{4}\acute{5}|8
\end{array}
Sélectionnez au hasard deux gènes, $ g_1, g_2 $, et déplacez $ g_1 $ avant $ g_2 $. C'est une forme particulière de translocation.
\begin{array}{cc}
parent& 1\acute{2}3456\grave{7}8
\end{array}
\rightarrow
\begin{array}{cc}
Enfant& 1\grave{7}\acute{2}34568
\end{array}
Inverse l'ordre des gènes pour les sections sélectionnées au hasard.
\begin{array}{cc}
parent& 1|\acute{2}\acute{3}\acute{4}|5678
\end{array}
\rightarrow
\begin{array}{cc}
Enfant& 1|\acute{4}\acute{3}\acute{2}|5678
\end{array}
Réorganisez au hasard l'ordre des gènes pour les sections sélectionnées au hasard.
\begin{array}{cc}
parent& 1|\acute{2}\acute{3}\acute{4}\acute{5}|678
\end{array}
\rightarrow
\begin{array}{cc}
Enfant& 1|\acute{4}\acute{2}\acute{5}\acute{3}|678
\end{array}
Deux chromosomes sont coupés et échangés à un endroit aléatoire.
\begin{array}{cc}
Parent 1& g_1 g_2 g_3 | g_4 g_5 g_6 \\
Parent 2& h_1 h_2 h_3 | h_4 h_5 h_6
\end{array}
\rightarrow
\begin{array}{cc}
Enfant 1& g_1 g_2 g_3 | h_4 h_5 h_6 \\
Enfant 2& h_1 h_2 h_3 | g_4 g_5 g_6
\end{array}
Échangez les sections où deux chromosomes sont coupés en deux points aléatoires.
\begin{array}{cc}
Parent 1& g_1 g_2 | g_3 g_4 g_5 | g_6 \\
Parent 2& h_1 h_2 | h_3 h_4 h_5 | h_6
\end{array}
\rightarrow
\begin{array}{cc}
Enfant 1& g_1 g_2 | h_3 h_4 h_5 | g_6 \\
Enfant 2& h_1 h_2 | g_3 g_4 g_5 | h_6
\end{array}
Échangez les sections où deux chromosomes sont coupés en plusieurs points aléatoires.
\begin{array}{cc}
Parent 1& g_1 | g_2 g_3 | g_4 g_5 | g_6 \\
Parent 2& h_1 | h_2 h_3 | h_4 h_5 | h_6
\end{array}
\rightarrow
\begin{array}{cc}
Enfant 1& g_1 | h_2 h_3 | g_4 g_5 | h_6 \\
Enfant 2& h_1 | g_2 g_3 | h_4 h_5 | g_6
\end{array}
Les gènes de chacun des deux chromosomes sont échangés avec une probabilité appropriée.
\begin{array}{cc}
Parent 1& g_1 g_2 g_3 g_4 g_5 g_6 \\
Parent 2& h_1 h_2 h_3 h_4 h_5 h_6
\end{array}
\rightarrow
\begin{array}{cc}
Enfant 1& g_1 h_2 g_3 h_4 h_5 g_6 \\
Enfant 2& h_1 g_2 h_3 g_4 g_5 h_6
\end{array}
Remplacez un gène à une position aléatoire par un autre gène.
\begin{array}{cc}
parent& g_1 g_2 g_3 g_4 g_5 g_6
\end{array}
\rightarrow
\begin{array}{cc}
Enfant& g_1 h_2 g_3 h_4 g_5 g_6
\end{array}
Cela produit un tout nouvel individu, pas un croisement ou une mutation.
J'avais l'intention de publier le programme en présentant brièvement le problème de l'algorithme génétique / vendeur itinérant, mais depuis l'introduction de l'algorithme génétique est devenue une longue phrase, j'écrirai le programme dans un article séparé.
Recommended Posts