[PYTHON] Lösung des Problems des Handlungsreisenden mit dem genetischen Algorithmus (GA) und seiner Bibliothek (vcopt)

: anchor: Zweck dieses Artikels

In diesem Artikel verwenden wir "vcopt", eine Python-Bibliothek, die als Löser den genetischen Algorithmus (GA) anwendet, um ein einfaches Beispiel für ein Problem mit Handlungsreisenden zu lösen, das häufig bei mathematischen Optimierungsproblemen auftritt. Ich werde es erforschen. Lassen Sie uns auch sehen, wie Sie vcopt "globale Optimierung der Bestellung, die durch das Problem des Handlungsreisenden dargestellt wird" lösen und verwenden können.

: anchor: Was ist vcopt?

Ein Kombinationsoptimierungslöser unter Verwendung des von Vignette & Clarity LLC (https://vigne-cla.com/) entwickelten Genetic Algorithm (GA). Geschrieben in der Python-Sprache. In diesem Solver sind verschiedene Funktionen implementiert, aber dieses Mal werde ich versuchen, eine Lösung mit der Funktion [vcopt (). TspGA () -Funktion] zu finden, die die globale Optimierung der Reihenfolge findet (Sortierung).

: anchor: Beispiel

Schauen wir uns ein Beispiel für das Problem der reisenden Verkäufer an.

: language_balloon: Problem

`ruby:5.1.Problem`


Wenn Sie 5 Städte besuchen, wird die zwischen den Städten zurückgelegte Entfernung in Tabelle 5 angezeigt..Betrachten Sie das in 1 angegebene Problem des Handlungsreisenden.
Zum Beispiel A.-B-C-D-E-Wenn Sie mit A besuchen, beträgt die zurückgelegte Gesamtstrecke 30+ 30 + 25 + 30 + 10 =Es wird 125.
Stellen Sie sich eine Patrouillenroute vor, die die kürzeste Reisedistanz erfordert.

** Tabelle 5.1 **

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

: language_balloon: ** Denken **

Die Problemeinstellung definiert die Entfernung zwischen den einzelnen Städten, sodass Sie eine Lösung finden können, indem Sie diese Entfernung für jede Route berechnen. In vcopt wird standardmäßig eine Funktion [** tspGA () **] bereitgestellt, die die "globale Optimierung der Reihenfolge" berechnet. Verwenden Sie diese Funktion. (Einzelheiten zu tspGA () finden Sie im vcopt-Tutorial usw.)

: desktop: Einfaches Optimierungspaket "vcopt" Tutorial 　https://vigne-cla.com/vcopt-tutorial/

Bei Verwendung der obigen Funktion [tspGA ()] muss jedoch die Auswertungsfunktion als einer der Parameter festgelegt werden. Diese Bewertungsfunktion muss unabhängig implementiert werden, um die Gesamtentfernung für jede Route zu berechnen.

Auch wenn dies in der Problembeschreibung nicht angegeben ist, wird bei diesem Problem davon ausgegangen, dass Sie Stadt A verlassen und wieder zu Stadt A zurückkehren. Wenn Sie die Route anzeigen, die umhergeht und in einem Diagramm zurückkehrt, können Sie sich vorstellen, dass es sich um eine Figur in der Nähe eines Kreises (eines verzerrten Kreises) mit verbundenen Linien handelt. Die Linien brechen nicht in der Mitte oder überlappen sich auf demselben Pfad. Dies wird als gesperrte Straße bezeichnet. Wenn Sie diesen geschlossenen Pfad finden, hat vcopt eine Erklärung der Lösung. Wenden Sie diese an.

: desktop: 8-6. Lösen des Problems mit reisenden Verkäufern mit vcopt (Wie schließen Sie die Straße?) 　https://vigne-cla.com/8-6/

: a: ** Antwort **

Betrachten Sie das Programm. Laden Sie zunächst die erforderlichen Bibliotheken.

`tspga.py`


from vcopt import vcopt
import numpy as np

Die Bewertungsfunktion ist unten definiert. Wie oben erwähnt, ist dies eines der Argumente (Parameter), die beim Ausführen der Funktion [tspGA ()] erforderlich sind.

`tspga.py`


#Eine Funktion, die die Entfernung zwischen Städten berechnet
def tsp_score(para):

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

Das Obige dient dazu, dass vcopt den Wert dieser Bewertungsfunktion bei der Lösung des Kombinationsoptimierungsproblems berechnet und maximiert oder minimiert oder sich dem Zielwert nähert. Da der Zweck dieser Zeit darin besteht, die Gesamtentfernung im Patrouillenverkäuferproblem so weit wie möglich zu reduzieren, definieren wir eine Funktion zur Berechnung der Gesamtentfernung bei der Patrouille jeder Stadt. Der Funktionsname lautet tsp_score. Als Argument ist es ein Array (Abs.) Von Indexnummern, die jede Stadt darstellen. Eine Sache, die Sie hier beachten sollten, ist, dass nicht nur Stadt A enthalten ist. Der Inhalt dieses Indexnummernarrays wird später beschrieben.

In Bezug auf (1) oben gibt es eine ausführliche Erklärung in "Lösen des Problems mit reisenden Verkäufern mit vcopt (Wie sperrt man die Straße?)", Aber nachdem man Stadt A verlassen und andere Städte besucht hat, Stadt A erneut Es ist ein Satz, um die Bedingung festzulegen, zu der zurückgekehrt werden soll. Die Nummer 0 ist die Indexnummer der Stadt A. Die Indexnummer, die die Stadt darstellt, ist unten definiert.

Bitte schreiben Sie nicht "... (1)" in das Programm.

Definieren Sie als Nächstes den Abstand zwischen Städten als Konstante.

`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
　　...

Für das Obige haben wir ein zweidimensionales Array mit dem konstanten Namen dis erstellt. Wenn Sie beispielsweise von Stadt A (Indexnummer: 0) nach Stadt B (Indexnummer: 1) wechseln, setzen Sie den Wert mit dis [0] [1]. Der Einstellwert ist 30. Nur ein Teil der oben genannten Quelle wird veröffentlicht. In der tatsächlichen Quelle zwischen allen Städten einstellen. Bitte beziehen Sie sich auf die gesamte Quelle am Ende dieses Artikels.

Da es nicht möglich ist, dieselbe Stadt nacheinander zu patrouillieren, wird der Entfernungswert auf 50 gesetzt, wenn dieselbe Indexnummer weiterhin besteht. Durch Festlegen eines großen Werts, damit er nicht in derselben Stadt verläuft, wird der Wert der Bewertungsfunktion erhöht, sodass er nicht als Optimierungslösung ausgewählt wird.

Der Rest der Definition der Bewertungsfunktion ist unten gezeigt.

`tspga.py`


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

    return distance

Das Obige ist der Prozess der Berechnung der Gesamtentfernung (Variablenname: Entfernung), wenn zwischen Städten gewechselt und an den Aufrufer der Funktion zurückgegeben wird. Schritt ist eine Zahl, die die Anzahl der Besuche angibt, wenn Sie durch die Stadt reisen. Schleifen Sie den Schritt mit 0-4 in der for-Anweisung und addieren Sie die zurückgelegte Strecke zwischen der stepth Stadt und der step + 1st Stadt.

Das ist alles für die Definition der Bewertungsfunktion. Geben Sie die Hauptverarbeitung des Programms ein.

`tspga.py`


para = [1,2,3,4]

Das Obige sind die Parameter, die der Funktion [tspGA ()] gegeben wurden, die die Elemente sind, um die Kombination zu berücksichtigen. In diesem Problem wird die zu besuchende Stadt neu angeordnet (kombiniert), um eine Lösung zu finden. Das Element ist also die Städtenummer. Wie oben erwähnt, ist die Stadt des Startpunkts und des Endpunkts der Patrouille jedoch A, sodass Stadt A bereits festgelegt wurde und keiner Sortierung (Kombination) unterliegt. Das Ziel sind die Städte B bis E, und die Indexnummern sind 1 bis 4.

Die zuvor definierte Auswertungsfunktion [tsp_score ()] hat auch das Argument para, das auf dieselbe Variable verweist. Die Funktion tsp_score wird intern aufgerufen, wenn vcopt tsp_score () ausführt, und der Parameter para wird ebenfalls automatisch festgelegt.

Führen Sie als nächstes die Funktion [tspGA ()] aus, die die Lösung der Optimierung berechnet.

`tspga.py`


para, score = vcopt().tspGA(para,       #Zu sortierende Elemente
                            tsp_score,  #Bewertungsfunktion
                            0.0)        #Zielwert

Stellen Sie drei Argumente (Parameter) ein, wenn Sie oben tspGA () aufrufen. Das erste Argument ist "zu sortierende Elemente". Diesmal ist es die Indexnummer aller Städte außer Stadt A. Das zweite Argument ist die "Bewertungsfunktion". Der Inhalt der Auswertungsfunktion wird im Definitionsteil dieser Funktion erläutert. Das dritte Argument ist der "Zielwert". Der Zielwert ist 0. Die tatsächliche Fahrstrecke wird niemals 0 sein, aber da die Rundstrecke mit der kürzesten Fahrstrecke die Lösung des Problems darstellt, wird sie auf 0 gesetzt, um die Richtung zu bestimmen, in die sie abnimmt. Einzelheiten zu den Argumenten (Parametern) finden Sie im vcopt-Lernprogramm.

Es gibt zwei Rückgabewerte für die Funktion, para ist das sortierte Array und score ist die Gesamtentfernung (Mindestentfernung), die als optimierte Lösung berechnet wird.

Unten werden Para und Score am Ende des Programms auf dem Bildschirm angezeigt.

`tspga.py`


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

Dies ist das Ende der Programmierung. Das tatsächliche Ausführungsergebnis ist wie folgt.

___________________ 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

Als Ergebnis der Optimierung lautet die Lösung wie folgt. para = [3 2 1 4] Dies bedeutet, dass die Rundstrecke der Stadt die Städte D, C, B, E darstellt. Dieses Mal ist Stadt A der Start- und Endpunkt, also fand ich schließlich heraus, dass die Patrouillenroute wie folgt sein sollte.

** Patrouillenroute A → D → C → B → E → A **

Die Gesamtentfernung beträgt ** 110 **.

Das gesamte Programm ist unten dargestellt.

`tspga.py`


from vcopt import vcopt
import numpy as np

#Patrouillenverkäufer Problem

#Eine Funktion, die die Entfernung zwischen Städten berechnet
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,       #Zu sortierende Elemente
                            tsp_score,  #Bewertungsfunktion
                            0.0)        #Zielwert

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

: Anker: Ausstellung

Dieser Artikel basiert auf den in den folgenden Referenztexten beschriebenen Übungen zur mathematischen Optimierung.

■ Referenztext "Mathematische Optimierung von IT-Texten" Takato Kuno et al. [Autor] Informationsverarbeitungsgesellschaft [Bearbeiten]

: Anker: Meinungen etc.

Wenn Sie Meinungen oder Korrekturen haben, lassen Sie es uns bitte wissen.