Ich habe versucht, "einen genetischen Algorithmus (GA) in Python zu implementieren, um das Problem des Handlungsreisenden (TSP) zu lösen".

Einführung

Da dies der erste Beitrag von Qiita ist, geben Sie uns bitte alle Details wie nicht nur den Inhalt, sondern auch das Format und den Schreibstil.

[Implementierung eines genetischen Algorithmus (GA) in Python zur Lösung des Problems des Handlungsreisenden (TSP)](http://samuiui.com/2019/10/27/ Implementierung eines genetischen Algorithmus (ga) in Python Patrol Say /)

Ich habe es tatsächlich versucht. Ich dachte, wenn ich mich an das Codieren gewöhnen würde, müsste ich es nicht einzeln erwähnen. Ich werde so viel wie möglich aufzeichnen, woran ich interessiert bin.

[Hier]((http://samuiui.com/2019/10/27/python implementiert genetischen Algorithmus (ga) und Patrouillen /)) wird wahnsinnig referenziert (& zitiert).

Plötzlich

Auch wenn Sie den Code von [Link ebenfalls oben veröffentlicht] kopieren und einfügen ((http://samuiui.com/2019/10/27/python implementiert den genetischen Algorithmus (ga) und die Patrouillen /)) Manchmal hat es nicht funktioniert. Das ist zum Beispiel natürlich

import numpy as np
import random
import matplotlib.pyplot as plt

Kommen wir zum Hauptthema.

Was ist ein genetischer Algorithmus (GA)?

Wohlhabende Nachkommen von Menschen mit hervorragenden Genen. Im genetischen Algorithmus wird eine gute Lösung auf die gleiche Weise gedeihen.

Wohlstand der Nachkommen

Ein Individuum, das in jedem Element überlegen ist, bringt viele Nachkommen zur Welt. Minderwertige Individuen können nur wenige Nachkommen zur Welt bringen. Das gleiche passiert mit der Bewegung von der Kindergeneration zur Enkelgeneration. Durch die Wiederholung dieses Prozesses werden anspruchsvolle Kinder geboren, die an die Umwelt angepasst sind.

Mutation

Während der Überfahrt werden nur ähnliche Personen gefunden. Unsere Gene sorgen für Vielfalt, indem sie gelegentlich Mutationen verursachen.

Was ist das Travelling Salesman Problem (TSP)?

Das Problem der reisenden Verkäufer ist Es ist eine Art Problem, dass ein Verkäufer n Geschäftsziele in welcher Reihenfolge umrundet. Theoretisch gibt es n! Street-Routen, daher ist das Round-Robin schwierig.

Dieses Mal möchte ich GA mit diesem TSP lösen.

fließen

[Quelle]((http://samuiui.com/2019/10/27/Implementieren eines genetischen Algorithmus (ga) in Python und Patrouillen /))

Erste individuelle Generation

Als frühes Individuum müssen Sie eine Stadt und Gene schaffen.

Stadt

Erzeugt n Städte, deren x- und y-Koordinaten beide im Bereich von 0 bis 1 liegen. Eingabe ist die Anzahl der Städte, Ausgabe ist die Matrix von (Anzahl der Städte) x 2 Implementierungsbeispiel: generate_rand_cities

#Stadt generieren
def generate_rand_cities(num_cities):
    positions = np.zeros((num_cities, 2))
    for i in range(num_cities):
        positions[i, 0] = random.random()
        positions[i, 1] = random.random()
    return positions
#Als Test
generate_rand_cities(10)

Über zufällig (random.random)

random.random()

Erzeugt zufällig Gleitkommazahlen größer oder gleich 0,0 und kleiner als 1,0

Gen

Geben Sie dem Gen Informationen über die Reihenfolge, in der Sie durch die Stadt fahren. Die Länge des Gens entspricht der Anzahl der Städte. Wenn beispielsweise die Anzahl der Städte 6 beträgt, [3, 5, 1, 0, 4, 2] [0, 4, 2, 1, 5, 3] Solche Personen sind möglich.

Weil Gene in einer Generation mehrere Individuen bilden Gene werden durch die Matrix (Anzahl der Individuen von Genen) x (Anzahl der Städte) dargestellt.

Die Eingabe ist die Anzahl der Städte und die Anzahl der Individuen in einer Generation, und die Ausgabe ist die Matrix von (Anzahl der Gene) x (Anzahl der Städte).

Implementierungsbeispiel: generate_init_genes

#Generieren
def generate_init_genes(num_individual, num_cities):
    genes = np.zeros((num_individual, num_cities), dtype=np.int16)
    for i in range(num_individual):
        genes[i,] = random.sample(range(num_cities), k=num_cities)
    return genes
#Als Test
generate_init_genes(15,10)

Über zufällig (random.sample)

Random.sample wird ohne Duplizierung zufällig abgerufen. Zum Beispiel

l = [0, 1, 2, 3, 4]
random.sample(l, 3)

Gibt etwas wie [4, 2, 1] oder [1, 0, 3] aus.

Auswertung

Bei dieser Aufgabe müssen Gene mit kürzeren Signalwegen hoch bewertet werden. Daher wird zunächst die Länge des dem Gen entsprechenden Weges erhalten. Danach wird es innerhalb der Generation verglichen und ausgewertet.

Wege, die Genen entsprechen

Die Referenzquelle berechnete die Entfernung zwischen Städten für jedes Gen. Machen Sie eine Tabelle über die Entfernung zwischen Städten und beziehen Sie sich auf sie in der Reihenfolge der Gene.

Tabelle der Entfernungen zwischen Städten

Implementierungsbeispiel

#Tabelle über Entfernungen zwischen Städten
def generate_dist_table(positions):
    path_table = np.zeros((len(positions), len(positions)))
    for i in range(len(positions)):
        for j in range(len(positions)):
            path_table[i,j] = np.linalg.norm(positions[i]-positions[j])
    return path_table

#Als Test
num_cities = 4
positions = generate_rand_cities(4)
generate_dist_table(positions)

Die Entfernung zwischen zwei Städten wird zweimal berechnet. Ich kann hier immer noch kratzen ...

Die Länge des dem Gen entsprechenden Weges

Basierend auf dieser Tabelle wird die Länge des dem Gen entsprechenden Weges erhalten.

#In der Tabelle finden Sie die Summe der Pfade, die den Genen entsprechen
def sum_path2(path_table, gene):
    sum = 0.
    for i in range(len(gene)-1):
        sum += path_table[int(gene[i]),int(gene[i+1])]
    return sum

#Als Test
cities = generate_rand_cities(10)
genes = generate_init_genes(15,10)
dist_table = generate_dist_table(cities)
for i in range(len(genes)):
    print(sum_path2(dist_table, genes[i]))

Um Gene für jede Generation gemeinsam zu bewerten, legen Sie eine Funktion fest, um Gene für eine Generation gemeinsam auszugeben.

#Berechnung einer Generation für die Summe der Routen
def genes_path2(path_table, genes):
    pathlength_vec = np.zeros(len(genes))
    for i in range(len(genes)):
        pathlength_vec[i] = sum_path2(path_table, genes[i])
    return pathlength_vec

#Als Test
cities = generate_rand_cities(10)
genes = generate_init_genes(15,10)
dist_table = generate_dist_table(cities)
genes_path2(dist_table, genes)

Roulette

Die Länge des dem Gen entsprechenden Weges wurde gefunden. Dieses Mal ist die Bewertung umso höher, je kürzer die Route ist. Je kürzer die Route ist, desto höher ist die Wahrscheinlichkeit, als diejenige ausgewählt zu werden, die Nachkommen hinterlässt. Normalisierung durchführen.

#Roulette
def generate_roulette(fitness_vec):
    total = np.sum(fitness_vec)
    roulette = np.zeros(len(fitness_vec))
    for i in range(len(fitness_vec)):
        roulette[i] = fitness_vec[i]/total
    return roulette

#Als Test
fitness = np.array([20,50,30])
generate_roulette(fitness)

Andererseits

array([0.2, 0.5, 0.3])

Wird sein.

Gene bewerten

Die Länge des dem Gen entsprechenden Weges ist bereits bekannt. Dieses Mal ist die Bewertung umso höher, je kürzer die Route ist. Je kürzer die Route ist, desto höher ist die Wahrscheinlichkeit, als diejenige ausgewählt zu werden, die Nachkommen hinterlässt. Daher wird diesmal die umgekehrte Nummer der Routenlänge verwendet.

#Beispiel für eine Roulette-Ausführung
cities = generate_rand_cities(20)
genes = generate_init_genes(21, 20)
dist_table = generate_dist_table(cities)
paths = genes_path2(dist_table, genes)
inverse_path = 1/paths
print("path length: "+str(paths))
print("roulette table: "+str(generate_roulette(inverse_path)))

Da die Roulette-Tabelle insgesamt 1 hat, kann dies als die Wahrscheinlichkeit interpretiert werden, dass das entsprechende Gen ausgewählt wird. Dies wird verwendet, um Gene auszuwählen.

Auswahl (Auswahl)

#Wählen Sie Personen aus, die basierend auf Roulette gekreuzt werden sollen
def roulette_choice(fitness_vec):
    roulette = generate_roulette(fitness_vec)
    choiced = np.random.choice(len(roulette), 2, replace=True, p=roulette)
    return choiced

#Als Test
cities = generate_rand_cities(20)
genes = generate_init_genes(21, 20)
dist_table = generate_dist_table(cities)
fitness_vec = 1 / genes_path2(dist_table, genes)
roulette_choice(fitness_vec)

Erstellen Sie mit generate_roulette eine Roulette-Tabelle. Wählen Sie anhand der Roulette-Tabelle zwei Gene aus dem Roulette aus.

Über zufällig (random.choice)

random.choice hat Duplikate und wählt zufällig einen Wert aus. Zahlenbereich, der durch das erste Argument ausgewählt wurde, Das zweite Argument ist die zu wählende Zahl. Geben Sie an, ob ein Duplikat mit Ersetzen vorhanden ist (True mit Duplikat). Die Wahrscheinlichkeit, dass jeder ausgewählt wird, wird durch p angegeben.

Kreuzung

Mit roulette_choice können jetzt zwei relativ gute Personen ausgewählt werden. Multiplizieren Sie die beiden Personen. Abhängig von der Form des Gens und auch für dieselbe Genform gibt es mehrere Crossover-Methoden. Zum Beispiel scheint es eine Auftragskreuzung und eine Kreiskreuzung zu geben → Anwendung von GA auf Bestellprobleme Diesmal haben wir eine teilweise Überkreuzung durchgeführt. Die Methode der Teilkreuzung entnehmen Sie bitte dem Bild unten. [Quelle]((http://samuiui.com/2019/10/27/Implementieren eines genetischen Algorithmus (ga) in Python und Patrouillen /))

Implementierung einer teilweisen Frequenzweiche

#Implementierung einer teilweisen Frequenzweiche
def partial_crossover(parent1, parent2):
    num = len(parent1)
    cross_point = random.randrange(1,num-1)   #Brechen
    child1 = parent1
    child2 = parent2
    for i in range(num - cross_point):
        #Wert rechts von der Pause
        target_index = cross_point + i
        target_value1 = parent1[target_index]
        target_value2 = parent2[target_index]
        exchange_index1 = np.where(parent1 == target_value2)
        exchange_index2 = np.where(parent2 == target_value1)
        #Austausch
        child1[target_index] = target_value2
        child2[target_index] = target_value1
        child1[exchange_index1] = target_value1
        child2[exchange_index2] = target_value2
    return child1, child2

#Als Test
genes = generate_init_genes(2, 10)
print("parent1: "+str(genes[0]))
print("parent2: "+str(genes[1]))
child = partial_crossover(genes[0], genes[1])
print("child1:  "+str(child[0]))
print("child2:  "+str(child[1]))

Mutation

Es gibt verschiedene Methoden zur Mutation. Dieses Mal werden wir das tun, was als Translokation bezeichnet wird. Tauschen Sie zwei zufällig ausgewählte Orte aus.

def translocation_mutation2(genes, p_value):
    mutated_genes = genes
    for i in range(len(genes)):
        mutation_flg = np.random.choice(2, 1, p = [1-p_value, p_value])
        if mutation_flg == 1:
            mutation_value = np.random.choice(genes[i], 2, replace = False)
            mutation_position1 = np.where(genes[i] == mutation_value[0])
            mutation_position2 = np.where(genes[i] == mutation_value[1])
            mutated_genes[i][mutation_position1] = mutation_value[1]
            mutated_genes[i][mutation_position2] = mutation_value[0]
    return mutated_genes

#Als Test
genes = generate_init_genes(5, 10)
print("before")
print(genes)
print("after")
print(translocation_mutation2(genes, 0.7))

mutations_flag hat eine Wahrscheinlichkeit von p_value von 1. Daher mutiert das Gen mit einer Wahrscheinlichkeit von p_value.

Visualisierung

Obwohl es nicht im Flussdiagramm geschrieben ist, wird es mit matplotlib visualisiert, um den Übergang von GA zu überprüfen.

Stadtlage

#Visualisierung der Stadtlage
def show_cities(cities):
    for i in range(len(cities)):
        plt.scatter(cities[i][0], cities[i][1])

#Als Test
cities = generate_rand_cities(10)
show_cities(cities)

Routenvisualisierung

def show_route(cities, gene):
    for i in range(len(gene)-1):
        if i == 0:
            plt.text(cities[int(gene[i])][0], cities[int(gene[i])][1], "start")
        else:
            plt.text(cities[int(gene[i])][0], cities[int(gene[i])][1], str(i))
        plt.plot([cities[int(gene[i])][0], cities[int(gene[i+1])][0]], 
                 [cities[int(gene[i])][1], cities[int(gene[i+1])][1]])
    plt.text(cities[int(gene[i+1])][0], cities[int(gene[i+1])][1], "goal")

#Als Test
cities = generate_rand_cities(10)
show_cities(cities)
genes = generate_init_genes(10,10)
show_route(cities,genes[0])

Integration

Implementieren Sie ein Programm, das TSP mit GA mithilfe der bisher erstellten Funktionen löst.

Parameter

#Parameter
num_cities = 10
individuals = 21
generation = 10000
elite = 9
p_mutation = 0.01

Initialisieren

#Initialisieren
cities = generate_rand_cities(num_cities)
genes = generate_init_genes(individuals, num_cities)
dist_table = generate_dist_table(cities)
show_cities(cities)
show_route(cities, genes[0])
plt.show()

Sie sollten dies sehen können

Ausführungsabteilung

Mit ausgezeichneter Elite der Elterngeneration Individuelle Elitekinder, die durch Kreuzung zwischen Elterngenerationen geboren wurden, sind für die Kindergeneration verantwortlich. Bei den Nachkommen treten Mutationen auf, um die endgültigen Nachkommen zu bilden.

#Ausführungsabteilung
top_individual=[]  #Liste der besten Anpassungsfähigkeit für jede Generation
max_fit = 0  #Höchste Anpassungsfähigkeit aller Zeiten
fitness_vec = np.reciprocal(genes_path2(dist_table, genes))
for i in range(generation):
    children = np.zeros(np.shape(genes))
    for j in range(int((individuals-elite)/2+1)):
        parents_indices = roulette_choice(fitness_vec)
        children[2*j], children[2*j+1] = partial_crossover(genes[parents_indices[0]], genes[parents_indices[1]])

    for j in range(individuals-elite, individuals):
        children[j] = genes[np.argsort(genes_path2(dist_table, genes))[j-individuals+elite]]

    children = translocation_mutation2(children, p_mutation)
    top_individual.append(max(fitness_vec))
    genes = children
    fitness_vec = np.reciprocal(genes_path2(dist_table, genes))
    if max(fitness_vec) > max_fit:  #Zeigen Sie die Route an, nachdem Sie die höchste Anpassungsfähigkeit aller Zeiten aufgezeichnet haben
        max_fit = max(fitness_vec)
        show_cities(cities)
        show_route(cities, genes[np.argmax(fitness_vec)])
        plt.text(0.05, 0.0, "generation: " + str(i) + "  distance: " +str(sum_path2(dist_table,genes[np.argmax(fitness_vec)])))
        plt.show()

top_individual ist eine Liste der besten Anpassungsfähigkeit jeder Generation.

Der zuletzt angezeigte Es wird diejenige sein, die in der Reihenfolge herumgeht, in der die Route kürzer wird. Ebenfalls,

plt.plot(top_individual)

Sie können den Übergang der Anpassungsfähigkeit überprüfen, wenn sich die Generierung ändert.

Über numpy (Hinweis)

np.reciprocal () → Gibt das mit jedem invertierten Element an np.argmax () → Gibt den Index des größten jedes Elements an np.argsort () → Indexreihenfolge, wenn jedes Element sortiert ist

Zusammenfassung

Als Standardeinstellung Anzahl der Städte, Genpopulation, Anzahl der evolutionären Generationen, Anzahl der Elite, Wahrscheinlichkeit einer Mutation, Wurde gegeben.

Natürlich gibt es eine bessere Route, wenn Sie die Anzahl der Städte erhöhen, aber sie entwickelt sich nicht zu dieser Route. Außerdem dauert die Berechnung einige Zeit Es gibt noch Raum für Verbesserungen. Als möglicher Punkt

Wie man überquert

Ich weiß nichts, weil ich keine anderen Wege zum Überqueren kenne. Möglicherweise gibt es eine bessere Kreuzungsmethode. Außerdem möchte ich es mit Mutation verbinden.

Wahrscheinlichkeit einer Mutation

Es wird angenommen, dass die Effizienz verbessert wird, wenn sich die Wahrscheinlichkeit einer Mutation in Abhängigkeit von der Ähnlichkeit der Eltern ändert.

Anzahl der aufgenommenen Eliten

Diesmal habe ich mich für die Grundeinstellungen entschieden. Wie bei der Wahrscheinlichkeit einer Mutation kann es jedoch besser sein, dies entsprechend der Ähnlichkeit der Eltern zu ändern. Wenn als Test die Anzahl der Eliten verringert wird, nimmt die Anpassungsfähigkeit nicht zu und es vibriert. Es wird angenommen, dass die Anpassungsfähigkeit in den frühen Stadien nicht erhöht wird, da schlechte Elemente durch Überqueren aufgenommen werden.

Anzahl der Generationen

Die Anzahl der Generationen wurde ebenfalls standardmäßig angegeben, es gibt jedoch Raum für Verbesserungen. Die Anzahl der Generationen steht in direktem Zusammenhang mit der Rechenlast. Wenn die Endbedingung anhand der Änderungsrate der Anpassungsfähigkeit festgelegt wird, muss die Anzahl der Generationen nicht angegeben werden.

Anzahl der Gene

Ebenso ist die Anzahl der Individuen eines Gens an der Berechnung beteiligt. Wenn die Anzahl der Individuen gering ist, muss die Generation der Evolution erhöht werden. Wenn Sie ein geeignetes Verhältnis für die angegebene Anzahl von Städten festlegen, müssen Sie es nicht eingeben.

Ausblick

Am Ende betreten Sie einfach die Stadt und es wird Sie zur richtigen Route führen. Daher erscheint es notwendig, die Crossover-Methode zu untersuchen, wie die Wahrscheinlichkeit einer Mutation angegeben werden kann, und geeignete Werte für die Anzahl der Individuen und die Anzahl der Generationen von Genen zu ermitteln. Ich werde mein Bestes geben.

zufällige Zusammenfassung

• Wählen Sie zufällig ein Element aus: random.choice ()
• Wählen Sie zufällig mehrere Elemente aus (keine Duplizierung): random.sample ()
• Wählen Sie zufällig mehrere Elemente (mit Duplikaten) aus: random.choices ()
• Generieren Sie zufällig Gleitkommazahlen von 0 bis 1: random.random () Aus Zufällig mit Python verwenden