Ich studiere das Wissen über genetische Algorithmen, die für den Betrieb von Schnabeltieren und Gehörlosen erforderlich sind, basierend auf dem Sonderartikel der März 2019-Ausgabe von Nikkei Software.
Der genetische Algorithmus ist ein Algorithmus, der die genetische Evolution nachahmt, wie "Selektion (Selektion)", "Crossover" und "Mutation". Der genetische Algorithmus ist auch ein Zufallsauswahlalgorithmus, da er viele Zufallszahlen verwendet.
Das Problem, das gelöst werden kann, besteht darin, die folgenden zwei zu erfüllen. ・ Probleme, die für Eingabeparameter quantifiziert (ausgewertet) werden können ・ Das Problem, die Eingabe zu finden, die den numerischen Wert maximiert und minimiert
Gen: Komponente zur Expression von Merkmalen Chrom: Eine Sammlung mehrerer Gene Individuum: Ein Merkmal, das von einem Chromosom ausgedrückt wird (manchmal als Individuum = Chromosom bezeichnet)
"Anpassungsfähigkeit" ist der Bewertungswert dafür, wie geeignet ein Individuum für die Umwelt ist.
Drei Operationen werden ausgeführt, um diese Anpassungsfähigkeit zu erhöhen. Auswahl (Auswahl): Belassen Sie diejenigen mit hoher Anpassungsfähigkeit (wählen Sie diejenigen mit geringer Anpassungsfähigkeit aus) Crossover: Produziert ein Kind, das das Gen von zwei Elternteilen erbt Mutation: Ändert das Gen eines Individuums mit einer bestimmten Wahrscheinlichkeit.
Crossover ist ein Markenzeichen genetischer Algorithmen.
Wenn alle diese Vorgänge einmal abgeschlossen sind, rückt die Generierung um eins vor.
Das OneMax-Problem besteht darin, eine Liste wie [1,0,0,0,1,0,1,1] zu finden, die die Summe der aus 1s und 0s bestehenden Liste maximiert. Gen: 0 oder 1 Chromologie: [1,0,0,0,1,0,1,1] Anwendbarkeit: Summe der Listen (in diesem Fall [1,0,0,0,1,0,1,1] = 4)
Das Programm besteht aus folgenden Elementen: Parametereinstellungen Funktionen (Anpassungsfähigkeit berechnen, Populationen nach Anpassungsfähigkeit sortieren, auswählen: hoch anpassungsfähige Individuen belassen, kreuzen, mutieren) Hauptverarbeitung (Erzeugung, Auswahl, Überkreuzung, Mutation der ursprünglichen Population)
Fünf sind als Parameter angegeben. Genlänge, Anzahl der Individuen, Anzahl der Generationen, Wahrscheinlichkeit der Mutation, Selektionsrate
import random
import copy
#Parameter
LIST_SIZE = 10 # 0/Listenlänge von 1 (Genlänge)
POPULATION_SIZE = 10 #Bevölkerung Bevölkerung
GENERATION = 25 #Anzahl der Generationen
MUTATE = 0.1 #Wahrscheinlichkeit einer Mutation
SELECT_RATE = 0.5 #Auswahlverhältnis
In diesem Beispiel ist "GENERATION = 25", sodass es in 25 Generationen endet. Im Allgemeinen endet es, wenn sich die Anpassungsfähigkeit nicht ändert. Wenn Sie LIST_SIZE erhöhen, erreichen Sie möglicherweise nicht die optimale Lösung, es sei denn, Sie erhöhen POPULATION_SIZE`` GENERATION. Die Einstellung der Mutationswahrscheinlichkeit, der Selektionsrate usw. ist wichtig, diesmal wird jedoch angemessen entschieden.
#Anpassungsfähigkeit berechnen
def calc_fitness(individual):#Individuum ist ein Chromosom
return sum(individual) #Summe der Chromosomenlistenelemente
#Sortieren Sie die Population nach Anpassungsfähigkeit
def sort_fitness(population):
#Tupple Anpassungsfähigkeit und Einzelpersonen und in Liste speichern
fp = []
for individual in population:
fitness = calc_fitness(individual)#Berechnen Sie die Anpassungsfähigkeit und bringen Sie sie in Fitness.
fp.append((fitness, individual)) #Ordnen Sie Anpassungsfähigkeit und Chromosom in fp an
fp.sort(reverse=True) #Nach Anwendbarkeit sortieren(absteigende Reihenfolge)
sorted_population = [] #Eine Gruppe, die sortierte Personen speichert
for fitness, individual in fp: #Nehmen Sie eine Person heraus und speichern Sie sie in einer Gruppe
sorted_population.append(individual)
return sorted_population #Dabei werden die Anwendbarkeit und die Chromosomen in absteigender Reihenfolge der Anwendbarkeit sortiert gespeichert.
#Wahl
#Lassen Sie hoch anpassungsfähige Personen
def selection(population):
sorted_population = sort_fitness(population)#sort_Die Population enthält sortierte Anwendbarkeit und Chromosomen.
#Anzahl der Personen, die verlassen werden sollen. 0 in der Parametereinstellung.Da es 5 ist, bleiben 5 Individuen bei 10 x 0,5
n = int(POPULATION_SIZE * SELECT_RATE)
return sorted_population[0:n]#Fünf bleiben von Anfang an. 0,1,2,3,4
#Kreuzung
#Kopieren Sie zunächst ind1, um eine neue individuelle ind zu erstellen. Danach wird der zufällig bestimmte Bereich von r1 bis r2 durch das ind2-Gen ersetzt.
def crossover(ind1, ind2):
r1 = random.randint(0, LIST_SIZE - 1)#Bestimmen Sie zufällig die Position von r1
r2 = random.randint(r1 + 1, LIST_SIZE)#Bestimmen Sie zufällig die Position von r2 nach r1.
ind = copy.deepcopy(ind1)#Machen Sie eine Kopie von ind1
ind[r1:r2] = ind2[r1:r2]#Nehmen Sie einen zufällig bestimmten Bereich von r1 bis r2 von Chromosom ind2 und ersetzen Sie ihn durch eine Kopie von ind1 ,.
return ind
#Mutation:設定したMutation確率に従ってMutationさせる
def mutation(ind1):
ind2 = copy.deepcopy(ind1)#Machen Sie ind2 durch Kopieren.
for i in range(LIST_SIZE):
if random.random() < MUTATE:#Machen Sie zufällig einen numerischen Wert, und wenn er geringer als die Mutationsrate ist, tritt eine Mutation auf
ind2[i] = random.randint(0, 1)#Setzen Sie 0 oder 1, wo die Mutation kam
return ind2
#Erstbevölkerung erzeugen
population = [] #Gruppe
for i in range(POPULATION_SIZE):
individual = [] #Chrom
for j in range(LIST_SIZE):
# 0/Addiere 1 mit einer Zufallszahl
individual.append(random.randint(0, 1))
population.append(individual)
for generation in range(GENERATION):
print(str(generation + 1) + u"Generation")
#Wahl
population = selection(population)
#Wiederholen Sie die Kreuzung und Mutation. Erhöhte Anzahl von Individuen durch Kreuzung und Mutation
n = POPULATION_SIZE - len(population)
for i in range(n):
#Wählen Sie zufällig 2 Personen aus der Gruppe aus
#Generieren Sie gekreuzte Personen
r1 = random.randint(0, len(population) - 1)
r2 = random.randint(0, len(population) - 1)
#Kreuzung
individual = \
crossover(population[r1], population[r2])
#Mutation
individual = mutation(individual)
#Zur Gruppe hinzufügen
population.append(individual)
for individual in population:
print(individual)
Dies ist ein Programm, das das One-Max-Problem lösen kann.
1 Generation [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]
Die optimale Lösung wurde in der 14. Generation gefunden. 14 Generationen [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]
In der 20. Generation sind bis zu 6 Lösungen optimal geworden. 20 Generationen [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]
Alle wurden in der 25. Generation zu optimalen Lösungen. 25 Generationen [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]
Hier erfahren Sie, wie Sie das grundlegende OneMax-Problem lösen.
Nächstes Mal werde ich das Problem der reisenden Verkäufer lösen.
Recommended Posts