Je faisais des recherches pour résoudre avec un algorithme génétique, Je l'ai fait dans le sens d'augmenter le nombre d'étapes pour l'avenir.

Quel est le problème du voyageur de commerce?

C'est un problème de penser à l'ordre dans lequel vous pouvez passer le plus court si vous écrivez un trait à un certain point dans $ n $. Si le nombre de villes à écrire en un coup est $ n $, le nombre de combinaisons possibles est $ \ frac {(n-1)!} {2} $.

Qu'est-ce qu'un algorithme génétique?

C'est l'un des calculs d'évolution qui modélisent l'évolution des êtres vivants. La combinaison de solutions est considérée comme un chromosome, et la solution évolue en répétant des manipulations génétiques telles que le croisement et la mutation pour enfin trouver la meilleure solution.

Flux de classe

Puisque nous programmons en Java, nous examinerons chaque classe dans l'ordre. Le diagramme de classe est comme ci-dessous. Cliquez ici pour consulter la littérature référencée dans la conception [^ 1]

La classe de ce programme est la suivante.

Classe de points: $ x $, $ y $ Stocke chaque coordonnée.
Classe de carte: une classe qui regroupe les données de la classe Point et les rassemble sous forme de carte.
Classe de tournée: une classe qui stocke les itinéraires en fonction de la classe Map.
Classe TourWithGA: Une classe dérivée de la classe Tour qui peut résoudre des algorithmes génétiques.
tspSample class: C'est la classe principale.
classe tspIO: une classe qui lit les coordonnées d'un fichier.
Classe de tri: Une classe pour classer les individus. (Non inclus dans le diagramme de classe ci-dessus.)
Classe de chromosomes: Une classe de chromosomes. Les gènes sont inclus dans une séquence.
Classe d'individus: Une classe de populations. Un ensemble de classes de chromosomes et un chromosome d'élite de type chromosome sont stockés.

Parmi eux, trois algorithmes génétiques sont utilisés: ** TourWithGA **, ** Chromosome ** et ** Individuals **.

En ce qui concerne la manipulation des gènes, la classe Chromosome met en œuvre des méthodes pour calculer la mutation et la compatibilité des gènes, et la classe Individual met en œuvre le croisement, la régénération / sélection de gènes et la conservation d'élite en tant que méthodes.

En tant que stratégie, il est créé en référence à la méthode de croisement d'échange de branche (EXX) proposée par Maekawa et al. [^ 2].

Comportement des algorithmes génétiques

Comme il y a beaucoup de code source, veuillez consulter le code source pour plus de détails. J'expliquerai les spécifications en me concentrant sur le fonctionnement dans l'algorithme génétique.

Données cartographiques

Entrez l'emplacement de la ville dans le problème du voyageur de commerce dans un fichier CSV. Le contenu du fichier CSV est

`berlin52.csv`

Sur la première ligne, saisissez le nombre de villes lisibles. À partir de la deuxième ligne, entrez les coordonnées $ x $ et $ y $ de la ville.

La classe principale du programme est ** tspSample **. Lors de l'exécution en java

$ java tspSample <Fichier CSV à lire>

Veuillez exécuter comme ceci.

Si la lecture réussit,

city_num= 52
565.000	 575.000
25.0000	 185.000
345.000	 750.000
945.000	 685.000
845.000	 655.000
・
・
・

De cette manière, le nombre de villes lues et les données de ville sont sorties vers la console.

Génération individuelle initiale

Générer une population initiale qui manipule génétiquement les enfants de type Individus. Plus précisément, dans la classe des chromosomes, il est exprimé sous forme de séquence de villes sous forme de séquence génique. La classe Tour a une méthode appelée makeTour () qui génère un circuit de manière aléatoire. Après avoir généré le circuit, le circuit est copié dans la séquence du gène.

Calcul de conformité

Le degré de conformité est calculé sur la base de la mise à l'échelle de la loi de puissance. Le nombre de villes $ n $ peut être obtenu à partir de la classe Map, et la longueur du circuit $ l $ peut être obtenue à partir de la méthode getDistance () de la classe Tour.

\mathrm{Fitness} = \left(\frac{n}{l} \right)^3

Jouer / sélectionner

Dans le programme, nous utilisons deux classes individuelles. Effectuer une manipulation génétique avec ** les parents **. Dans la prochaine génération, ** les enfants ** survivront aux chromosomes de leurs parents en fonction du degré de compatibilité chromosomique. $ N_ {\ mathrm {p}} $ est stocké dans les parents, et $ N_ {\ mathrm {c}} $ est stocké dans les enfants. (Cependant, $ N_ {\ mathrm {p}} \ geq N_ {\ mathrm {c}} $)

Quant à la survie, les chromosomes $ N_ {\ mathrm {c}} $ supérieurs sont faits pour survivre dans l'ordre d'adaptabilité des chromosomes chez les parents. Cependant, comme les individus élites doivent toujours être inclus dans la population, si la compatibilité du chromosome le plus compatible de la population est supérieure à la compatibilité du chromosome élite, l'individu élite est le plus compatible de la population. Mettre à jour vers un chromosome supérieur. Sinon, remplacez le chromosome $ N_ {\ mathrm {c}} $ ème par un chromosome élite.

La méthode de sélection du chromosome parent à manipuler génétiquement à partir des enfants survivants de la population consiste à calculer la valeur attendue de survie chez l'individu parent à partir de la formule suivante lorsque le degré de compatibilité du chromosome $ C_i $ chez les enfants est $ f_i $.

\mathrm{Experience} = \frac{N_{\mathrm{p}} \times f_i}{N_{\mathrm{c}} \times \overline{f}}

$ \ Overline {f} $ est l'ajustement moyen des chromosomes chez les enfants. Sélectionnez le chromosome parent par le nombre de valeurs attendues (arrondi après la virgule décimale) et copiez-le dans le parent. La partie après la virgule décimale est utilisée pour la sélection de la roulette.

Pour tous les chromosomes, si vous sélectionnez autant de parents que vous le souhaitez, les parents auront des chromosomes vides. Les autres parents sélectionnent leurs parents par sélection de roulette.

Afin d'éviter que le même chromosome ne soit sélectionné parmi les parents sélectionnés, deux sont choisis au hasard dans le chromosome parent afin qu'ils ne se chevauchent pas, et ils sont croisés.

Croisement / mutation

Le croisement est basé sur la probabilité de croisement et la mutation est basée sur la probabilité de mutation. Voir la référence [2] pour plus de détails.

Correction génétique

L'algorithme génétique a une forte capacité à trouver une solution optimale globale, mais a une faiblesse dans la capacité de recherche locale. Par conséquent, le gène est corrigé par la méthode 2-opt, qui est l'une des méthodes d'amélioration séquentielle dans le problème du voyageur de commerce, avant le calcul de l'aptitude.

Je l'ai essayé

$ N_ {\ mathrm {c}} = 100 $, $ N_ {\ mathrm {p}} = 150 $, nombre maximum de générations: 300, probabilité de croisement: 0,8, probabilité de mutation: 0,1, 52 problème de référence de la ville Berlin52 (valeur optimale) : 7544,366)). .. Pour l'itinéraire terminé, les données seront sorties dans le fichier result.csv dans le même répertoire.

city_num= 52
565.000  575.000
25.0000  185.000
345.000  750.000

(Omis)

595.000  360.000
1340.00  725.000
1740.00  245.000
start...
    0    7742.647
    1    7742.647
    2    7742.647
    3    7742.647
    4    7544.366
    5    7544.366
    6    7544.366

(Omis)

  294    7544.366
  295    7544.366
  296    7544.366
  297    7544.366
  298    7544.366
  299    7544.366
  300    7544.366
7544.366
stop.
Temps de traitement: 3157/ms

à la fin

Ce croisement d'échange de branches est considéré comme la deuxième meilleure méthode après la méthode de croisement d'assemblage de branches pour résoudre le problème d'ordonnancement cyclique avec un algorithme génétique. Actuellement, la méthode utilisant le croisement par assemblage de branches est considérée comme la meilleure méthode pour résoudre l'algorithme génétique du problème du voyageur de commerce. J'aimerais l'essayer un jour. Étant donné que j'étudie les problèmes de planification, j'aimerais créer un programme qui résout les problèmes de planification.

Code source

Le code source est ouvert au public. Le code est peut-être sale parce que j'étais dans un laboratoire qui n'utilise pas beaucoup Java ... (N'hésitez pas à me donner des conseils.) https://github.com/SHIMADONBEY/GAwithTSP.git

Les références

[^ 2]: Maekawa, Tamaki, Kita, Nishikawa: Une solution au problème du voyageur de commerce utilisant un algorithme génétique, Proceedings of the Society of Automatic Measurements, Vol. 31, No 5, pp. 598-605, 1995.

[^ 1]: Hatayama: modélisation orientée objet GA, Faculté d'ingénierie de l'Université d'Ibaraki, 2010.

J'ai essayé de créer un programme en Java qui résout le problème du voyageur de commerce avec un algorithme génétique