J'étudie les connaissances des algorithmes génétiques nécessaires pour faire fonctionner l'ornithorynque et le deap sur la base de l'article spécial du numéro de mars 2019 de Nikkei Software.
L'algorithme génétique est un algorithme qui imite l'évolution génétique telle que «sélection (sélection)», «croisement» et «mutation». L'algorithme génétique est également un algorithme de choix aléatoire car il utilise beaucoup de nombres aléatoires.
Le problème qui peut être résolu est de satisfaire les deux suivants. ・ Problèmes pouvant être quantifiés (évalués) pour les paramètres d'entrée ・ Le problème de trouver l'entrée qui maximise et minimise la valeur numérique
Gène: composant pour exprimer des traits Chrome: une collection de plusieurs gènes Individu: trait exprimé par un chromosome (parfois appelé individu = chromosome)
La «capacité d'adaptation» est la valeur d'évaluation de l'adéquation d'un individu à l'environnement.
Trois opérations sont effectuées pour augmenter cette adaptabilité. Sélection (sélection): laissez ceux avec une grande adaptabilité (sélectionnez ceux avec une faible adaptabilité) Crossover: produit un enfant qui hérite d'un gène de deux parents Mutation: modifie le gène d'un individu avec une certaine probabilité.
Crossover est une caractéristique des algorithmes génétiques.
Lorsque toutes ces opérations sont terminées une fois, la génération avance d'une unité.
Le problème OneMax est un problème de recherche d'une liste telle que [1,0,0,0,1,0,1,1] qui maximise la somme de la liste composée de 1 et 0. Gène: 0 ou 1 Chromologie: [1,0,0,0,1,0,1,1] Applicabilité: somme des listes (dans ce cas, [1,0,0,0,1,0,1,1] = 4)
Le programme est composé des éléments suivants: réglages des paramètres Fonctions (calculer l'adaptabilité, trier les populations par ordre d'adaptabilité, sélectionner: laisser des individus hautement adaptables, croiser, muter) Traitement principal (génération, sélection, croisement, mutation de la population initiale)
Cinq sont donnés comme paramètres. Longueur du gène, nombre d'individus, nombre de générations, probabilité de mutation, taux de sélection
import random
import copy
#Paramètres
LIST_SIZE = 10 # 0/Longueur de la liste de 1 (longueur du gène)
POPULATION_SIZE = 10 #Population population
GENERATION = 25 #Nombre de générations
MUTATE = 0.1 #Probabilité de mutation
SELECT_RATE = 0.5 #Ratio de sélection
Dans cet exemple, GENERATION = 25, donc il se terminera dans 25 générations. En général, cela prendra fin lorsque l'adaptabilité ne changera pas. Si vous augmentez LIST_SIZE, vous risquez de ne pas atteindre la solution optimale à moins que vous n'augmentiez POPULATION_SIZE GENERATION`. Le réglage de la probabilité de mutation, du taux de sélection, etc. est important, mais cette fois, il est décidé de manière appropriée.
#Calculer l'adaptabilité
def calc_fitness(individual):#l'individu est un chromosome
return sum(individual) #Somme des éléments de la liste des chromosomes
#Trier la population par adaptabilité
def sort_fitness(population):
#Adapter l'adaptabilité et les individus et stocker dans la liste
fp = []
for individual in population:
fitness = calc_fitness(individual)#Calculez l'adaptabilité et mettez-la en forme.
fp.append((fitness, individual)) #Mettre l'adaptabilité et le chromosome en ordre en fp
fp.sort(reverse=True) #Trier par applicabilité(Ordre décroissant)
sorted_population = [] #Un groupe qui stocke des individus triés
for fitness, individual in fp: #Sortez un individu et stockez-le dans un groupe
sorted_population.append(individual)
return sorted_population #En cela, l'applicabilité et les chromosomes triés par ordre décroissant d'applicabilité sont stockés.
#Choix
#Laissez des individus hautement adaptables
def selection(population):
sorted_population = sort_fitness(population)#sort_La population contient une applicabilité et des chromosomes triés.
#Nombre de personnes à quitter. 0 dans le paramétrage.Puisqu'il est 5, 5 individus restent à 10 x 0,5
n = int(POPULATION_SIZE * SELECT_RATE)
return sorted_population[0:n]#Il en reste cinq depuis le début. 0,1,2,3,4
#Traversée
#Tout d'abord, copiez ind1 pour créer une nouvelle ind. Après cela, la plage déterminée de manière aléatoire de r1 à r2 est remplacée par le gène ind2.
def crossover(ind1, ind2):
r1 = random.randint(0, LIST_SIZE - 1)#Déterminez aléatoirement la position de r1
r2 = random.randint(r1 + 1, LIST_SIZE)#Déterminez aléatoirement la position de r2 après r1.
ind = copy.deepcopy(ind1)#Faire une copie de ind1
ind[r1:r2] = ind2[r1:r2]#Prenez une plage déterminée aléatoirement de r1 à r2 à partir du chromosome ind2 et remplacez-la par une copie de ind1,.
return ind
#mutation:設定したmutation確率に従ってmutationさせる
def mutation(ind1):
ind2 = copy.deepcopy(ind1)#Créez ind2 en copiant.
for i in range(LIST_SIZE):
if random.random() < MUTATE:#Créez des nombres au hasard, et si le taux de mutation est inférieur à
ind2[i] = random.randint(0, 1)#Mettez 0 ou 1 là où la mutation est venue
return ind2
#Générer une population initiale
population = [] #Groupe
for i in range(POPULATION_SIZE):
individual = [] #Chrome
for j in range(LIST_SIZE):
# 0/Ajouter 1 avec un nombre aléatoire
individual.append(random.randint(0, 1))
population.append(individual)
for generation in range(GENERATION):
print(str(generation + 1) + u"génération")
#Choix
population = selection(population)
#Répétez le croisement et la mutation. Augmentation du nombre d'individus par croisement et mutation
n = POPULATION_SIZE - len(population)
for i in range(n):
#Sélectionnez au hasard 2 personnes dans le groupe
#Générer des individus croisés
r1 = random.randint(0, len(population) - 1)
r2 = random.randint(0, len(population) - 1)
#Traversée
individual = \
crossover(population[r1], population[r2])
#mutation
individual = mutation(individual)
#Ajouter au groupe
population.append(individual)
for individual in population:
print(individual)
C'est un programme qui peut résoudre le problème One-Max.
1 génération [1, 1, 1, 0, 1, 1, 0, 0, 1, 1] [1, 0, 1, 1, 0, 0, 1, 1, 1, 0] [1, 0, 1, 0, 1, 1, 0, 1, 1, 0] [1, 0, 1, 1, 1, 0, 0, 0, 0, 1] [0, 0, 1, 1, 0, 1, 1, 0, 1, 0] [1, 1, 1, 0, 1, 1, 0, 0, 1, 0] [0, 1, 1, 0, 1, 1, 0, 0, 1, 0] [0, 1, 1, 0, 1, 1, 1, 0, 1, 0] [1, 0, 1, 1, 0, 1, 0, 0, 1, 0] [1, 0, 1, 1, 1, 1, 0, 1, 1, 0]
La solution optimale a été trouvée dans la 14e génération. 14 générations [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 0, 1, 1, 1] [1, 1, 1, 1, 1, 1, 0, 1, 1, 1] [1, 1, 1, 1, 1, 1, 0, 1, 1, 1] [1, 1, 1, 1, 1, 1, 0, 1, 1, 1] [1, 1, 1, 1, 1, 1, 0, 1, 1, 1] [1, 1, 1, 1, 1, 0, 0, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 0, 0, 1, 1, 1] [1, 1, 1, 1, 1, 1, 0, 1, 1, 1]
Dans la 20e génération, jusqu'à 6 solutions sont devenues optimales. 20 générations [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 0, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 0] [1, 1, 1, 0, 1, 1, 1, 1, 1, 1]
Tout est devenu des solutions optimales dans la 25e génération. 25 générations [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Voici comment résoudre le problème de base de OneMax.
La prochaine fois, je résoudrai le problème du voyageur de commerce.
Recommended Posts