J'ai essayé d'implémenter GA (algorithme génétique) en Python
introduction
・ Ceci est mon premier message, donc il peut être difficile à voir. s'il vous plaît, pardonnez-moi.
・ Il peut y avoir des erreurs par rapport à l'algorithme génétique strict. (Eh bien, apprendre quelque chose? Pardonnez-moi car il semble que ça marche bien ...)
-Je suis désolé si le code source est difficile à lire ou redondant parce que je ne l'ai pas montré à d'autres. (Je vous serais reconnaissant si vous pouviez me dire les parties qui étaient difficiles à lire et celles qui étaient inutiles.)
Qu'est-ce qu'un algorithme génétique?
Il existe de nombreux types de sagesse d'excellents enseignants Google. https://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/GA/GA.htm Il existe également des définitions de mots et de cette zone, veuillez donc vous y référer.
https://www.youtube.com/watch?v=w1MF0Iz0p40 Youtube est toujours incroyable. Vous pouvez facilement voir une chose aussi intéressante et facile à comprendre.
Le problème que je veux résoudre cette fois
Pour le moment, comme exemple de problème, trouvons les coordonnées où la distance de l'origine est 0 dans l'espace tridimensionnel (x, y, z). De toute évidence, (0,0,0) devrait être la réponse ... Après cela, essayez de changer la distance par rapport à l'origine ou de lui donner environ 20 dimensions.
Flux de programme
Depuis que j'ai récemment étudié la classe, j'ai essayé d'implémenter le flux général de l'AG dans une classe. Pour être honnête, les avantages et les inconvénients de les rassembler dans une classe ne me sont pas venus à l'esprit ...
Pour le moment, j'expliquerai d'abord le rôle général des fonctions dans le programme.
Type de fonction
class GA:
#Récupérez les paramètres sur GA à partir du paramètre reçu en argument (nombre de générations, etc.)
def __init__(self, Setting):
#Afficher les paramètres sur l'AG tenue en classe
def get_parameter(self, flag=0, out_path="./"):
#La plupart du traitement GA est écrit dans ce(Quelque chose comme la fonction principale)
def Start_GA(self):
#Créer au hasard des gènes pour chaque individu en tant que population initiale
def make_genes(self):
#Une fonction qui évalue les gènes (calcule l'adaptabilité), et en même temps, trie par ordre décroissant d'évaluation et conserve les données
def evaluate(self, genes, goal):
#Générer des gènes dans un fichier externe avec adaptabilité
def Out_data(self, genes, evaluated_data, generation):
#Sauvez les personnes de haut rang avec une grande adaptabilité
def Save_elite(self, genes, evaluated_data):
#Une fonction qui sélectionne les parents pour créer la prochaine génération d'enfants.
def select(self, method, genes, evaluated_data):
#Une fonction qui multiplie (croise) les parents sélectionnés pour créer un nouvel individu
def crossover(self, method, genes, Select_id):
#Plus la stagnation est importante, plus le caractère aléatoire est ajouté pour étendre la zone de recherche de solution (mutation).
def mutation(self, genes, Stagnation):
Parmi elles, d'autres fonctions sont incorporées dans la fonction StartGA, donc si vous l'exécutez, le programme s'exécutera.
Programme réel
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, indicateur de sortie d'impression==1, description du fichier
def get_parameter(self, flag=0, out_path="./"):
#Chemin de sortie du fichier
out_path = out_path + "GA_parameter.txt"
#Contenu de sortie
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}',
]
#Changer la destination de sortie avec l'indicateur
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)
#Fonction pour démarrer GA (ou plutôt, c'est comme la fonction principale car la plupart du traitement est écrit dans ceci?)
def Start_GA(self):
#Génération actuelle
generation = 0
#Valeur de stagnation de la génération
Stagnation = 0
#Valeur cible
goal = 0
#La trajectoire du gène le plus adaptable
top_genes = list()
#Créez au hasard des gènes en tant que population initiale.
genes = self.make_genes()
while(True):
#Se termine lorsque la génération maximale est atteinte
if generation >= self.MaxGeneration:
break
else:
#Évaluation de l'adaptabilité
evaluated_data = self.evaluate(genes, goal)
#Fichier de gène de sortie et adaptabilité à l'extérieur
self.Out_data(genes, evaluated_data, generation)
#Sauvez les personnes de haut rang avec une grande adaptabilité
elite_genes = copy.deepcopy(self.Save_elite(genes, evaluated_data))
#Sélectionnez des personnes avec une grande adaptabilité
Select_id = self.select(0, genes, evaluated_data)
#Traverser pour créer de nouveaux gènes
genes = self.crossover(0, genes, Select_id)
#Donnez des mutations pour étendre la zone de recherche de solution
genes = self.mutation(genes, Stagnation)
#Ajouter un gène élite
genes[len(genes):len(genes)] = elite_genes
#Sauvez l'individu le plus adaptable
top_genes.append(elite_genes[0])
#Après la deuxième génération, si la stagnation de l'adaptabilité (la meilleure valeur d'adaptabilité n'est pas mise à jour) dépasse le nombre maximum de stagnation, le programme prend fin.
if len(top_genes)>=2:
if top_genes[-1]==top_genes[-2]:
#L'algorithme se termine lorsque le nombre maximum de stagnation est dépassé
if Stagnation >= self.MaxStagnationGeneration:
exit()
else:
Stagnation += 1
else:
Stagnation = 0
#Faire progresser les générations
generation +=1
#Créez des gènes au hasard. Soi pour un individu.Développez la dimension par le nombre de gènes Dimension
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
#Évaluation des gènes
def evaluate(self, genes, goal):
#Les données évaluées sont stockées dans un type de dictionnaire.(key, value)=(child_id, fitness)
evaluated_data = dict()
for child in range(self.Population):
#Plus l'adaptabilité est élevée, mieux c'est (ajusté à un maximum de 1).)
fitness = 1/(self.eval_func(genes[child], goal) + 1)
evaluated_data[child] = fitness
#Tri décroissant selon la valeur d'évaluation
evaluated_data = dict(sorted(evaluated_data.items(),reverse=True, key=lambda x:x[1]))
return evaluated_data
#Fonction auxiliaire d'évaluation
#Calculez la différence avec la valeur cible
def eval_func(self, gene, goal):
sum_value = 0
# self.Calculez la distance euclidienne de l'origine dans l'espace GenesDimension.
for id in range(len(gene)):
sum_value += gene[id]**2
return abs(np.sqrt(sum_value) - goal) # goal(Valeur cible)Calculez l'écart par rapport à.
#Sortie des données de gènes et adaptabilité à un fichier externe
def Out_data(self, genes, evaluated_data, generation):
#Sortie de gène(Avant de trier),Même séparateur de virgule que 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)
#Sortie adaptabilité (après tri),Même séparateur de virgule que 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)
#Sauvez les personnes de haut rang avec une grande adaptabilité
def Save_elite(self, genes, evaluated_data):
elite_id = list()
elite_genes = list()
# elite_Obtenir l'identifiant du dictionnaire
for key in evaluated_data.keys():
elite_id.append(key)
#Extrait du haut autant que le nombre d'élite
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):
#Stockez l'identifiant et la forme physique séparément dans une 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)
#Sélection de la valeur attendue
if method==0:
roulette = 360
tmp_list = list()
sum_fitness = sum(fitness_list) #Obtenez la valeur totale de l'adaptabilité
cumulative_fitness = np.cumsum(roulette*np.array(fitness_list)/sum_fitness) #Créez une large table à 360 degrés avec une rotation en fonction du degré d'adaptabilité
for child in range(self.Population - self.EliteCount): #Nombre d'individus pour créer des individus non élites - Nombre d'individus élites
for _ in range(2): #Répétez pour combiner les deux gènes.
Fate_dice = random.uniform(0,360) # 0~Lancez les dés fatidiques entre 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()
#Sélectionnez les gènes de nouvelle génération_id[child][0]Créé en utilisant le numéro d'identification de
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 #Probabilité de mutation
serious_rate = Stagnation/(self.MaxGeneration - self.EliteCount) #Plus la stagnation est importante, plus elle est susceptible de muter.
serious_count = int(len(genes)*serious_rate) #Ajustez la quantité de séquence mutée en multipliant par la taille de la séquence de gènes
for child in range(serious_count):
for dim in range(len(genes[0])):
Fate_random = random.uniform(0,1) # 0~Obtenez un nombre aléatoire de 1
if Fate_random <= probability:
genes[child][dim] += random.randint(-10,10) # -10~Donne 10 nombres aléatoires (fixes)
return genes
# Setting=[Name, MaxGeneration, Population, EliteCount, MaxStagnationGeneration, GenesDimension ...]
Setting = ["Sample", 150, 30, 2, 100, 3]
GA = GA(Setting)
GA.Start_GA()
Dans make_genes, les gènes sont créés dans la plage de -30 à 30 pour un axe (axe x, etc.). En outre, pour les mutations, des valeurs sont ajoutées dans la plage de -10 à 10.
Analyse des résultats
Dans les conditions ci-dessus, j'ai calculé 30 individus par génération pour environ 150 générations. Le programme pour voir le résultat est le suivant.
analysis_log.py
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
#Calculer la distance par rapport au bloc de données
def calc_distance(dataframe):
distance = 0
for col in range(len(dataframe.columns)): #Répétez autant de fois qu'il y a de colonnes
distance += dataframe[col]**2
distance = np.sqrt(distance) #Calculer la distance euclidienne
return distance
#Combiner des trames de données
def merge_dataframe(origin, add):
origin = pd.concat([origin, add], axis=1)
return origin
#Créer un graphique sous forme de données de série chronologique
def plot_log(distance, MaxGeneration):
y_mean = np.array(distance.mean()) #Obtenez la valeur moyenne des données
y_median = np.array(distance.median()) #Obtenir la médiane
y_min = np.array(distance.min()) #Obtenez la valeur minimale
y_max = np.array(distance.max()) #Obtenez le maximum
x = np.arange(len(y_mean))
xicks = np.arange(0, MaxGeneration+1, MaxGeneration/10) #Pour afficher Max Generation en mémoire+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) #Lecture des données
distance_0 = calc_distance(dataframe_0) #Calculer la distance par rapport au bloc de données
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)
L'axe horizontal représente le nombre de générations et l'axe vertical la distance par rapport à l'origine (0 est la valeur cible cette fois). En outre, moyenne, médiane, min et max sont respectivement la valeur moyenne, la valeur médiane, la valeur minimale et la valeur maximale de chaque génération. La recherche semble se dérouler sans heurts. Je suis heureux.
Enfin, avec la valeur cible fixée à 100, 100 individus par génération sont calculés pour environ 500 générations.
Ensuite, la valeur cible a été renvoyée à 0, le nombre d'axes génétiques (nombre de dimensions) a été fixé à 20 et le calcul a été effectué pour 150 individus et 2000 générations.
[Impression] D'une manière ou d'une autre, je pense que ce serait bien si les valeurs étaient mises à jour ... J'ai beaucoup écrit à ce sujet, mais s'il y a un homme féroce qui l'a lu jusqu'au bout, je serais très heureux si vous commentez.
Recommended Posts