Ich habe versucht, GA (genetischer Algorithmus) in Python zu implementieren
Einführung
・ Dies ist mein erster Beitrag, daher kann es schwierig sein, ihn zu sehen. bitte verzeih mir.
・ Im Vergleich zum strengen genetischen Algorithmus können einige Fehler auftreten. (Nun, etwas lernen? Verzeih mir, weil es so aussieht, als ob etwas gut läuft ...)
-Es tut mir leid, wenn der Quellcode schwer zu lesen oder redundant ist, weil ich ihn anderen nicht gezeigt habe. (Ich wäre Ihnen dankbar, wenn Sie mir die schwer lesbaren und nutzlosen Teile mitteilen könnten.)
Es gibt viele Arten von Weisheit exzellenter Google-Lehrer. https://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/GA/GA.htm Es gibt auch Definitionen von Wörtern und diesem Bereich. Bitte beziehen Sie sich auf diese.
https://www.youtube.com/watch?v=w1MF0Iz0p40 Youtube ist immer noch erstaunlich. Sie können so eine interessante und leicht verständliche Sache leicht sehen.
Das Problem möchte ich diesmal lösen
Lassen Sie uns vorerst als Beispielproblem die Koordinaten finden, bei denen der Abstand vom Ursprung 0 im dreidimensionalen Raum (x, y, z) beträgt. Offensichtlich sollte (0,0,0) die Antwort sein ... Versuchen Sie danach, den Abstand vom Ursprung zu ändern oder ihn auf etwa 20 Dimensionen festzulegen.
Programmablauf
Da ich kürzlich die Klasse studiert habe, habe ich versucht, den allgemeinen Ablauf von GA in einer Klasse zu implementieren. Um ehrlich zu sein, sind mir die Vor- und Nachteile einer Zusammenstellung in einer Klasse nicht in den Sinn gekommen ...
Vorerst werde ich zunächst die allgemeine Rolle der Funktionen im Programm erläutern.
Funktionsart
class GA:
#Rufen Sie die Parameter für GA aus der als Argument empfangenen Einstellung ab (Anzahl der Generationen usw.).
def __init__(self, Setting):
#Zeigen Sie die Parameter für GA an, die in der Klasse gehalten werden
def get_parameter(self, flag=0, out_path="./"):
#Der größte Teil der GA-Verarbeitung ist darin geschrieben(So etwas wie die Hauptfunktion)
def Start_GA(self):
#Erstellen Sie zufällig Gene für jedes Individuum als Anfangspopulation
def make_genes(self):
#Eine Funktion, die Gene auswertet (Anpassungsfähigkeit berechnet) und gleichzeitig in absteigender Reihenfolge der Auswertung sortiert und Daten speichert
def evaluate(self, genes, goal):
#Ausgabe von Genen in eine externe Datei zusammen mit Anpassungsfähigkeit
def Out_data(self, genes, evaluated_data, generation):
#Retten Sie hochrangige Personen mit hoher Anpassungsfähigkeit
def Save_elite(self, genes, evaluated_data):
#Eine Funktion, die Eltern auswählt, um die nächste Generation von Kindern zu erstellen.
def select(self, method, genes, evaluated_data):
#Eine Funktion, die ausgewählte Eltern multipliziert (kreuzt), um eine neue Person zu erstellen
def crossover(self, method, genes, Select_id):
#Je größer die Stagnation ist, desto mehr Zufälligkeit wird hinzugefügt, um den Lösungssuchbereich (Mutation) zu erweitern.
def mutation(self, genes, Stagnation):
Unter anderem sind andere Funktionen in der StartGA-Funktion enthalten. Wenn Sie dies ausführen, wird das Programm ausgeführt.
Aktuelles Programm
GA.py
import numpy as np
import random
import os
import copy
class GA:
# Setting=[Name, MaxGeneration, Population, EliteCount, MaxStagnationGeneration, GenesDimension ...]
def __init__(self, Setting):
self.Name = Setting[0]
self.MaxGeneration = Setting[1]
self.Population = Setting[2]
self.EliteCount = Setting[3]
self.MaxStagnationGeneration = Setting[4]
self.GenesDimension = Setting[5]
os.makedirs("./Out/", exist_ok=True)
print("\n GA start!! \n")
# flag==0, Ausgabeflag drucken==1, Dateibeschreibung
def get_parameter(self, flag=0, out_path="./"):
#Pfad für die Dateiausgabe
out_path = out_path + "GA_parameter.txt"
#Inhalt ausgeben
contents = [
f'GA_parameter!!\n',
f'Name: {self.Name}',
f'MaxGeneration: {self.MaxGeneration}',
f'Population: {self.Population}',
f'EliteCount: {self.EliteCount}',
f'GenesDimension: {self.GenesDimension}',
]
#Ändern Sie das Ausgabeziel mit Flag
if flag==0:
for sentense in contents:
print(sentense)
elif flag==1:
with open(out_path, mode="w") as file:
for sentense in contents:
print(sentense, file=file)
#Funktion zum Starten von GA (oder besser gesagt, es ist wie die Hauptfunktion, weil der größte Teil der Verarbeitung darin geschrieben ist?)
def Start_GA(self):
#Derzeitige Generation
generation = 0
#Generationsstagnationswert
Stagnation = 0
#Zielwert
goal = 0
#Die Flugbahn des anpassungsfähigsten Gens
top_genes = list()
#Erstellen Sie zufällig Gene als Anfangspopulation.
genes = self.make_genes()
while(True):
#Endet bei Erreichen der maximalen Generation
if generation >= self.MaxGeneration:
break
else:
#Bewertung der Anpassungsfähigkeit
evaluated_data = self.evaluate(genes, goal)
#Ausgabe-Gendatei und Anpassungsfähigkeit nach außen
self.Out_data(genes, evaluated_data, generation)
#Retten Sie hochrangige Personen mit hoher Anpassungsfähigkeit
elite_genes = copy.deepcopy(self.Save_elite(genes, evaluated_data))
#Wählen Sie Personen mit hoher Anpassungsfähigkeit aus
Select_id = self.select(0, genes, evaluated_data)
#Kreuzung, um neue Gene zu schaffen
genes = self.crossover(0, genes, Select_id)
#Geben Sie Mutationen an, um den Lösungssuchbereich zu erweitern
genes = self.mutation(genes, Stagnation)
#Elite-Gen hinzufügen
genes[len(genes):len(genes)] = elite_genes
#Speichern Sie die anpassungsfähigste Person
top_genes.append(elite_genes[0])
#Wenn nach der zweiten Generation die Stagnation der Anpassungsfähigkeit (der beste Wert der Anpassungsfähigkeit wird nicht aktualisiert) die maximale Anzahl der Stagnation überschreitet, endet das Programm.
if len(top_genes)>=2:
if top_genes[-1]==top_genes[-2]:
#Der Algorithmus endet, wenn die maximale Anzahl von Stagnationen überschritten wird
if Stagnation >= self.MaxStagnationGeneration:
exit()
else:
Stagnation += 1
else:
Stagnation = 0
#Generationen vorantreiben
generation +=1
#Erstellen Sie Gene nach dem Zufallsprinzip. Selbst für eine Person.Erweitern Sie die Dimension um die Anzahl der Gendimensionen
def make_genes(self):
genes = list()
tmp = list()
for child in range(self.Population):
for _ in range(self.GenesDimension):
tmp.append(random.randint(-30,30))
genes.append(tmp)
tmp = list()
# genes.shape=(self.Population, self.GenesDimension)
return genes
#Bewertung von Genen
def evaluate(self, genes, goal):
#Die ausgewerteten Daten werden in einem Wörterbuchtyp gespeichert.(key, value)=(child_id, fitness)
evaluated_data = dict()
for child in range(self.Population):
#Je höher die Anpassungsfähigkeit, desto besser (auf maximal 1 eingestellt).)
fitness = 1/(self.eval_func(genes[child], goal) + 1)
evaluated_data[child] = fitness
#Absteigende Sortierung nach Bewertungswert
evaluated_data = dict(sorted(evaluated_data.items(),reverse=True, key=lambda x:x[1]))
return evaluated_data
#Hilfsfunktion der Auswertung
#Berechnen Sie die Differenz zum Zielwert
def eval_func(self, gene, goal):
sum_value = 0
# self.Berechnen Sie den euklidischen Abstand vom Ursprung im GenesDimension-Raum.
for id in range(len(gene)):
sum_value += gene[id]**2
return abs(np.sqrt(sum_value) - goal) # goal(Zielwert)Berechnen Sie die Abweichung von.
#Ausgabe von Gendaten und Anpassungsfähigkeit an eine externe Datei
def Out_data(self, genes, evaluated_data, generation):
#Genausgabe(Vor dem Sortieren),Gleiches Komma-Trennzeichen wie csv
gene_path = "./Out/" + str(generation) + ".gene"
with open(gene_path, "w") as file:
for child in range(len(genes)):
for id in range(len(genes[child])):
if id==len(genes[child])-1:
print(str(genes[child][id]), file=file)
else:
print(str(genes[child][id]), end=",", file=file)
#Anpassungsausgabe (nach dem Sortieren),Gleiches Komma-Trennzeichen wie csv
fitness_path = "./Out/" + str(generation) + ".fit"
with open(fitness_path, "w") as file:
for id, fitness in evaluated_data.items():
print(str(id) +","+ str(fitness), file=file)
#Retten Sie hochrangige Personen mit hoher Anpassungsfähigkeit
def Save_elite(self, genes, evaluated_data):
elite_id = list()
elite_genes = list()
# elite_ID aus dem Wörterbuch abrufen
for key in evaluated_data.keys():
elite_id.append(key)
#Extrahieren Sie von oben so viele wie die Anzahl der Eliten
for elite in range(self.EliteCount):
elite_genes.append(genes[elite_id[elite]])
return elite_genes
# method==0: Expected value selection
# method==1: Ranking selection
# method==2: Tournament selection
def select(self, method, genes, evaluated_data):
#Speichern Sie ID und Fitness separat in einer Liste
id_list = list()
fitness_list = list()
Select_id = list()
for id, fitness in evaluated_data.items():
id_list.append(id)
fitness_list.append(fitness)
#Erwartete Wertauswahl
if method==0:
roulette = 360
tmp_list = list()
sum_fitness = sum(fitness_list) #Erhalten Sie den Gesamtwert der Anpassungsfähigkeit
cumulative_fitness = np.cumsum(roulette*np.array(fitness_list)/sum_fitness) #Erstellen Sie eine breite 360-Grad-Tabelle mit einer Umdrehung entsprechend dem Grad der Anpassungsfähigkeit
for child in range(self.Population - self.EliteCount): #Anzahl der Personen, die Nicht-Elite-Personen erstellen sollen - Elite-Anzahl der Personen
for _ in range(2): #Wiederholen Sie diesen Vorgang, um die beiden Gene zu kombinieren.
Fate_dice = random.uniform(0,360) # 0~Wirf die schicksalhaften Würfel zwischen 360
Hit_id = 0
while True:
if cumulative_fitness[Hit_id] >= Fate_dice:
break
else:
Hit_id += 1
tmp_list.append(id_list[Hit_id])
Select_id.append(tmp_list)
tmp_list = list()
return Select_id
# method==0: Uniform crossover
# method==1: Multipoint crossover
# method==2: Partial coincidence crossover
def crossover(self, method, genes, Select_id):
new_genes = list()
#Wählen Sie die Gene der nächsten Generation aus_id[child][0]Erstellt mit der ID-Nummer von
for child in range(self.Population - self.EliteCount):
new_genes.append(genes[Select_id[child][0]])
if method==0:
probability = 0.4
for child in range(self.Population - self.EliteCount):
for dim in range(len(genes[0])):
Fate_random = random.uniform(0,1)
if Fate_random <= probability:
new_genes[child][dim] = genes[Select_id[child][1]][dim]
return new_genes
def mutation(self, genes, Stagnation):
probability = 0.4 #Wahrscheinlichkeit einer Mutation
serious_rate = Stagnation/(self.MaxGeneration - self.EliteCount) #Je größer die Stagnation ist, desto wahrscheinlicher ist es, dass sie mutiert.
serious_count = int(len(genes)*serious_rate) #Passen Sie an, wie viel der Sequenz mutiert ist, indem Sie sie mit der Größe der Gensequenz multiplizieren
for child in range(serious_count):
for dim in range(len(genes[0])):
Fate_random = random.uniform(0,1) # 0~
if Fate_random <= probability:
genes[child][dim] += random.randint(-10,10) # -10~
return genes
# Setting=[Name, MaxGeneration, Population, EliteCount, MaxStagnationGeneration, GenesDimension ...]
Setting = ["Sample", 150, 30, 2, 100, 3]
GA = GA(Setting)
GA.Start_GA()
analysis_log.py
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
#
def calc_distance(dataframe):
distance = 0
for col in range(len(dataframe.columns)): #
distance += dataframe[col]**2
distance = np.sqrt(distance) #In make_genes werden Gene im Bereich von -30 bis 30 für eine Achse (x-Achse usw.) erstellt. Für Mutationen werden außerdem Werte im Bereich von -10 bis 10 hinzugefügt. Analyse der Ergebnisse Unter den oben genannten Bedingungen haben wir 30 Individuen pro Generation für ungefähr 150 Generationen berechnet. Das Programm, um das Ergebnis zu sehen, ist wie folgt. Berechnen Sie den Abstand vom Datenrahmen. Wiederholen Sie diesen Vorgang für die Anzahl der Spalten. Berechnen Sie den euklidischen Abstand
return distance
#Datenrahmen kombinieren
def merge_dataframe(origin, add):
origin = pd.concat([origin, add], axis=1)
return origin
#Erstellen Sie ein Diagramm als Zeitreihendaten
def plot_log(distance, MaxGeneration):
y_mean = np.array(distance.mean()) #Ermitteln Sie den Durchschnittswert der Daten
y_median = np.array(distance.median()) #Holen Sie sich Median
y_min = np.array(distance.min()) #Holen Sie sich den Mindestwert
y_max = np.array(distance.max()) #Holen Sie sich das Maximum
x = np.arange(len(y_mean))
xicks = np.arange(0, MaxGeneration+1, MaxGeneration/10) #Anzeige der maximalen Generierung im Speicher+1
plt.plot(x, y_mean, label="mean", color="green")
plt.plot(x, y_median,label="median", color="blue")
plt.plot(x, y_min, label="min", color="red")
plt.plot(x, y_max, label="max", color="cyan")
plt.xlabel("$Generation$", fontsize=15)
plt.ylabel("$distance$", fontsize=15)
plt.xlim(xmin=0)
plt.ylim(ymin=0)
plt.grid(True)
plt.xticks(xicks)
plt.legend()
plt.savefig("analysis_gene.jpg ")
MaxGeneration = 150
for G in range(MaxGeneration):
if G==0:
gene_path = "./Out/" + str(G) + ".gene"
dataframe_0 = pd.read_csv(gene_path, header=None) #Daten lesen
distance_0 = calc_distance(dataframe_0) #Berechnen Sie die Entfernung vom Datenrahmen
else:
gene_path = "./Out/" + str(G) + ".gene"
dataframe = pd.read_csv(gene_path, header=None)
distance = calc_distance(dataframe)
distance_0 = merge_dataframe(distance_0, distance)
plot_log(distance_0, MaxGeneration)
Die horizontale Achse ist die Anzahl der Generationen und die vertikale Achse ist der Abstand vom Ursprung (diesmal ist 0 der Zielwert). Außerdem sind Mittelwert, Median, Min und Max der Durchschnittswert, der Medianwert, der Minimalwert bzw. der Maximalwert in jeder Generation. Die Suche scheint reibungslos zu verlaufen. Ich bin glücklich.
Bei einem Zielwert von 100 werden schließlich 100 Personen pro Generation für etwa 500 Generationen berechnet.
Dann wurde der Zielwert auf 0 zurückgesetzt, die Anzahl der Genachsen (Anzahl der Dimensionen) wurde auf 20 eingestellt und die Berechnung wurde für 150 Individuen und 2000 Generationen durchgeführt.
[Eindruck] Irgendwie finde ich es schön, wenn die Werte aktualisiert würden ... Ich habe viel darüber geschrieben, aber wenn es einen wilden Mann gibt, der es bis zum Ende gelesen hat, würde ich mich sehr freuen, wenn Sie einen Kommentar abgeben.
Recommended Posts