[PYTHON] Résolution du problème du voyageur de commerce avec l'algorithme génétique (GA) et sa bibliothèque (vcopt)

: anchor: Objectif de cet article

Dans cet article, nous allons résoudre un exemple simple du problème du voyageur de commerce qui apparaît souvent dans les problèmes d'optimisation mathématique, en utilisant la bibliothèque Python "vcopt", qui est un solveur qui applique l'algorithme génétique (GA). Je vais l'explorer. Voyons également comment résoudre et utiliser vcopt "optimisation globale de la commande représentée par le problème du voyageur de commerce".

: anchor: Qu'est-ce que vcopt?

Un solveur d'optimisation de combinaison utilisant l'algorithme génétique (GA) développé par Vignette & Clarity LLC (https://vigne-cla.com/). Écrit en langage Python. Différentes fonctions sont implémentées dans ce solveur, mais cette fois je vais essayer de trouver une solution avec la fonction [vcopt (). TspGA () function] qui trouve l'optimisation globale de l'ordre (tri).

: anchor: Exemple

Jetons un coup d'œil à un exemple du problème du voyageur de commerce.

: speech_balloon: Problème

`ruby:5.1.problème`


Si vous visitez 5 villes, la distance parcourue entre les villes est indiquée dans le tableau 5..Considérez le problème du voyageur de commerce donné en 1.
Par exemple, A-B-C-D-E-Lorsque vous visitez avec A, la distance totale parcourue est de 30+ 30 + 25 + 30 + 10 =Cela devient 125.
Considérez un itinéraire de patrouille qui nécessite la distance de déplacement la plus courte.

** Tableau 5.1 **

	B	C	D	E
A	30	30	25	10
B		30	45	20
C			25	20
D				30

: speech_balloon: ** Pensée **

Le paramètre de problème définit la distance entre chaque ville, vous pouvez donc obtenir une solution en calculant cette distance pour chaque itinéraire. Dans vcopt, une fonction [** tspGA () **] qui calcule "l'optimisation globale de l'ordre" est fournie en standard, utilisez donc ceci. (Pour plus de détails sur tspGA (), reportez-vous au didacticiel vcopt, etc.)

: desktop: Tutoriel du package d'optimisation facile "vcopt" 　https://vigne-cla.com/vcopt-tutorial/

Cependant, lors de l'utilisation de la fonction ci-dessus [tspGA ()], il est nécessaire de définir la fonction d'évaluation comme l'un des paramètres. Cette fonction d'évaluation doit être mise en œuvre indépendamment en tant que fonction pour calculer la distance totale pour chaque itinéraire.

En outre, bien que non spécifié dans l'énoncé du problème, ce problème suppose que vous quittez la ville A et revenez à la ville A. Si vous montrez l'itinéraire qui fait le tour et qui revient dans un diagramme, vous pouvez imaginer qu'il s'agira d'une figure proche d'un cercle (un cercle déformé) avec des lignes connectées. Les lignes ne se coupent pas au milieu ou ne se chevauchent pas sur le même chemin. C'est ce qu'on appelle une route fermée. Lors de la recherche de ce chemin fermé, vcopt a une explication de la solution, alors appliquez-la.

: desktop: 8-6. Résolution du problème du voyageur de commerce avec vcopt (Comment fermez-vous la route?) 　https://vigne-cla.com/8-6/

: a: ** Réponse **

Considérez le programme. Commencez par charger les bibliothèques requises.

`tspga.py`


from vcopt import vcopt
import numpy as np

La fonction d'évaluation est définie ci-dessous. Comme mentionné ci-dessus, c'est l'un des arguments (paramètres) requis lors de l'exécution de la fonction [tspGA ()].

`tspga.py`


#Une fonction qui calcule la distance entre les villes
def tsp_score(para):

    para_full = np.hstack((0, para, 0))　　... (1)

Ce qui précède permet à vcopt de calculer la valeur de cette fonction d'évaluation lors de la résolution du problème d'optimisation de combinaison, et de la maximiser ou de la minimiser ou de s'approcher de la valeur cible. Puisque le but de ce temps est de réduire au maximum la distance totale dans le problème des patrouilleurs, nous définirons une fonction pour calculer la distance totale lors de la patrouille de chaque ville. Le nom de la fonction est tsp_score. En argument, il s'agit d'un tableau (para) de numéros d'index représentant chaque ville. Une chose à garder à l'esprit ici est qu'il n'inclut pas uniquement la ville A. Le contenu de ce tableau de numéros d'index sera décrit ultérieurement.

Concernant (1) ci-dessus, il y a une explication détaillée dans "Résoudre le problème du voyageur de commerce avec vcopt (Comment fermer la route?)", Mais après avoir quitté la ville A et visité d'autres villes, la ville A à nouveau C'est une phrase pour définir la condition de retour. Le nombre 0 est le numéro d'index de la ville A. Le numéro d'index représentant la ville est défini ci-dessous.

Veuillez ne pas écrire "... (1)" dans le programme.

Ensuite, définissez la distance entre les villes comme une constante.

`tspga.py`


    dis = [[0 for i in range(5)] for j in range(5)]
    dis[0][0] = 50
    dis[0][1] = 30
    dis[0][2] = 30
　　...

Pour ce qui précède, nous avons créé un tableau à deux dimensions avec le nom de constante dis. Par exemple, si vous passez de la ville A (numéro d'index: 0) à la ville B (numéro d'index: 1), définissez la valeur avec dis [0] [1]. La valeur de réglage est 30. Seule une partie de la source ci-dessus est publiée. Dans la source réelle, défini entre toutes les villes. Veuillez vous référer à la source entière à la fin de cet article.

Puisqu'il n'est pas possible de patrouiller successivement dans la même ville, si le même numéro d'index continue, la valeur de distance est fixée à 50. En définissant une valeur élevée pour qu'elle ne circule pas dans la même ville, la valeur de la fonction d'évaluation est augmentée afin qu'elle ne soit pas sélectionnée comme solution d'optimisation.

Le reste de la définition de la fonction d'évaluation est présenté ci-dessous.

`tspga.py`


    distance = 0
    for step in range(5):
        distance += dis[para_full[step]][para_full[step + 1]]

    return distance

Ce qui précède est le processus de calcul de la distance totale (nom de la variable: distance) lors du déplacement entre les villes et de la restitution à l'appelant de la fonction. step est un nombre qui indique le nombre de visites lors de déplacements dans la ville. Bouclez le pas avec 0-4 dans l'instruction for et additionnez la distance parcourue entre la ville stepth et l'étape + 1ère ville.

C'est tout pour la définition de la fonction d'évaluation. Entrez le traitement principal du programme.

`tspga.py`


para = [1,2,3,4]

Ci-dessus sont les paramètres donnés à la fonction [tspGA ()], qui sont les éléments pour considérer la combinaison. Dans ce problème, la ville à visiter est réorganisée (combinée) pour trouver une solution, donc l'élément est le numéro de ville. Cependant, comme mentionné ci-dessus, la ville du point de départ et du point d'arrivée de la patrouille est A, donc la ville A a déjà été décidée et n'est pas soumise au tri (combinaison). La cible est les villes B à E et les numéros d'index sont de 1 à 4.

La fonction d'évaluation [tsp_score ()] définie précédemment a également l'argument para, qui pointe vers la même variable. La fonction tsp_score est appelée en interne lorsque vcopt exécute tsp_score (), et le paramètre para est également défini automatiquement.

Ensuite, exécutez la fonction [tspGA ()] qui calcule la solution de l'optimisation.

`tspga.py`


para, score = vcopt().tspGA(para,       #Éléments à trier
                            tsp_score,  #Fonction d'évaluation
                            0.0)        #Valeur cible

Définissez trois arguments (paramètres) lors de l'appel de tspGA () ci-dessus. Le premier argument est "éléments à trier". Cette fois, il s'agit du numéro d'index de toutes les villes sauf la ville A. Le deuxième argument est la "fonction d'évaluation". Le contenu de la fonction d'évaluation est expliqué dans la partie définition de cette fonction. Le troisième argument est la "valeur cible". La valeur cible est 0. La distance parcourue réelle ne sera jamais 0, mais comme l'itinéraire du circuit avec la distance parcourue la plus courte sera la solution au problème, il sera mis à 0 pour déterminer la direction dans laquelle il diminuera. Pour plus de détails sur les arguments (paramètres), reportez-vous au tutoriel vcopt.

Il existe deux valeurs de retour pour la fonction, para est le tableau trié et score est la distance totale (distance minimale) calculée comme solution optimisée.

Ci-dessous, le para et le score sont affichés sur l'écran à la fin du programme.

`tspga.py`


print('para=',para)
print('score=',score)

C'est la fin de la programmation. Le résultat réel de l'exécution est le suivant.

___________________ info ___________________ para_range : n=4 score_func : <class 'function'> aim : 0.0 show_pool_func : 'bar' seed : None pool_num : 40 max_gen : None core_num : 1 (*vcopt, vc-grendel) ___________________ start __________________ Scoring first gen 40/40
Mini 2-opting first gen 40/40
| +<| gen=80, best_score=110.0 __________________ results _________________ para : [3 2 1 4] score : 110.0 ____________________ end ___________________ para= [3 2 1 4] score= 110.0

Suite à l'optimisation, la solution est la suivante. para = [3 2 1 4] Cela signifie que le circuit de la ville représente les villes D, C, B, E. Cette fois, la ville A est le point de départ et le point d'arrivée, alors j'ai finalement découvert que l'itinéraire de patrouille devrait être le suivant.

** Route de patrouille A → D → C → B → E → A **

La distance totale est de ** 110 **.

L'ensemble du programme est présenté ci-dessous.

`tspga.py`


from vcopt import vcopt
import numpy as np

#Problème de vendeur de patrouille

#Une fonction qui calcule la distance entre les villes
def tsp_score(para):

    para_full = np.hstack((0, para, 0))

    dis = [[0 for i in range(5)] for j in range(5)]
    dis[0][0] = 50
    dis[0][1] = 30
    dis[0][2] = 30
    dis[0][3] = 25
    dis[0][4] = 10
    dis[1][0] = 30
    dis[1][1] = 50
    dis[1][2] = 30
    dis[1][3] = 45
    dis[1][4] = 20
    dis[2][0] = 30
    dis[2][1] = 30
    dis[2][2] = 50
    dis[2][3] = 25
    dis[2][4] = 20
    dis[3][0] = 25
    dis[3][1] = 45
    dis[3][2] = 25
    dis[3][3] = 50
    dis[3][4] = 30
    dis[4][0] = 10
    dis[4][1] = 20
    dis[4][2] = 20
    dis[4][3] = 30
    dis[4][4] = 50

    distance = 0
    for step in range(5):
        distance += dis[para_full[step]][para_full[step + 1]]

    return distance


para = [1,2,3,4]

para, score = vcopt().tspGA(para,       #Éléments à trier
                            tsp_score,  #Fonction d'évaluation
                            0.0)        #Valeur cible

print('para=',para)
print('score=',score)

: ancre: Exposition

Cet article est basé sur les exercices décrits dans les textes de référence suivants sur l'optimisation mathématique.

■ Texte de référence "Optimisation mathématique du texte informatique" Takato Kuno, et al. [Auteur] Société de traitement de l'information [modifier |

: ancre: Opinions etc.

Si vous avez des opinions ou des corrections, veuillez nous en informer.