Die Zielgruppe für diesen Artikel ist
・ Ich weiß über künstliche Intelligenz Bescheid, aber ich verstehe es nicht. ・ Ist künstliche Intelligenz überhaupt nicht so wertvoll? ・ Ich dachte, ich würde es tun, aber nachdem ich die Formel gesehen hatte, verdorrte ich und hörte auf ・ Ich möchte künstliche Intelligenz betreiben, weiß aber nicht, was ich tun soll ・ Künstliche Intelligenzquellen sind zu verschwenderisch zum Lesen
Es richtet sich an Menschen wie.
Der genetische Algorithmus ist als Teil der künstlichen Intelligenz definiert. Aus meiner Sicht scheint es, als würde ich einen Dichotomie-Algorithmus schreiben. Da der genetische Algorithmus auch ein Algorithmus ist, ist er leicht zu implementieren, wenn Sie das Konzept verstehen.
Dieser Artikel ist praktisch und richtet sich nicht an Personen, die mit genetischen Algorithmen überhaupt nicht vertraut sind. Aber mach dir keine Sorgen. Es ist in Ordnung, wenn Sie alle unten stehenden Gottesfolien lesen und sie verstehen. (Diese Folie ist eine äußerst effiziente Methode, um genetische Algorithmen auf göttlicher Ebene zu erlernen. Verkaufen Sie sie als Buch.) Beginnen Sie mit dem genetischen Algorithmus!
Wie viel Sie verstehen sollten, ist in Ordnung, wenn Sie Folgendes grob verstehen können Außerdem sind die Wörter, die Sie nicht verstehen, grundsätzlich auf der Folie geschrieben.
1 Bestimmen Sie den Code, der die Lösung ausdrückt 2 Erstellen Sie N zufällige aktuelle Gen-Individuen 3 Variable Generation zur Speicherung der Genpopulation der nächsten Generation 4 Bewertungsberechnung des aktuellen Gens mit der Bewertungsfunktion 5 Wählen Sie zwei Gene aus der aktuellen Generation aus 6 Kreuzen Sie die ausgewählten Gene, um Nachkommen zu generieren 7 Machen Sie Mutationen in den generierten Nachkommen 8 Wiederholen Sie 5-6 bis zu N Personen der nächsten Generation 9 Übertragen Sie die Gruppe der nächsten Generation auf die aktuelle Generation und wiederholen Sie den Vorgang, bis sie konvergiert 10 Geben Sie das am höchsten bewertete Gen aus
Dann werde ich sofort eintreten
In diesem Artikel werden wir das OneMax-Problem mithilfe eines genetischen Algorithmus (GA) lösen. Auch dieses Mal werden wir keine externe Bibliothek für GA verwenden. Sie verwenden keine Bibliothek, wenn Sie eine Dichotomie durchführen, oder? Der zu verwendende Import wird unten gezeigt
・ Dezimal, um Berechnungsfehler so weit wie möglich zu vermeiden Zufällig, um einen zufälligen Wert zu erhalten -Klasse, die Geninformationen und den Bewertungswert des Gens zur einfachen Berechnung speichert. Genetischer Algorithmus (Machen Sie es sich zuerst selbst)
Der genetische Algorithmus wurde erstellt, weil der Erstautor dieses Artikels Java-ähnliche Codierung mag. (Alternative Methode ist OK)
list = [0,1,0,0,0,1,0,0,0,1,0,1,1,0,1] Zufällig angeordnete Sequenzen wie durch Evolutionsberechnung (GA) list = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] Es ist ein Problem, alle Array-Werte nahe 1 zu bringen.
Das Ziel ist es, die gleichen Ergebnisse wie unten zu erzielen. 1 ist die optimale Lösung. Der Minimalwert und der Maximalwertmittelwert der Bewertungswerte in verschiedenen Generationen werden ausgegeben.
-----Ergebnisse der 1. Generation-----
Min:0.36
Max:0.63
Avg:0.4999
-----Ergebnisse der 2. Generation-----
Min:0.46
Max:0.65
Avg:0.5653
-----Ergebnisse der 3. Generation-----
Min:0.54
Max:0.67
Avg:0.6098
-----Ergebnisse der 4. Generation-----
...
...
-----Ergebnisse der 39. Generation-----
Min:0.84
Max:0.93
Avg:0.9247
-----Ergebnisse der 40. Generation-----
Min:0.85
Max:0.94
Avg:0.9256
Das beste Individuum ist[1, 1, 0, 1, 1, 1, 0, 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, 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, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Details zu jedem Algorithmus
Code: Binärcodierung Darstellung eines Gens mit 0 und 1
Wahl: Eliteismus Wählen Sie die am besten geeignete Person aus
Kreuzung: Zweipunktkreuzung Wählen Sie zwei zufällige Punkte als Teil des Gens aus. Ersetzen Sie die Gene dazwischen
Mutation: Ersatz Ersetzen Sie Gene durch entgegengesetzte Zahlen 0,1% ~ 1% höchstens einige% Lokale Konvergenz, wenn zu gering. Wenn es zu hoch ist, konvergiert es nicht.
Generation: Steady-State-Modell Ersetzen Sie die erzeugten Nachkommen durch weniger zutreffende Personen.
Genlänge: 100 Population von Personen mit Genen: 100 Elite-Nummer für die optimale Lösung zu diesem Zeitpunkt: 20 Anzahl der Nachkommen, die durch die Kreuzung der Eliten hervorgebracht wurden: 40 Aufschlüsselung zum Zeitpunkt des Generationswechsels: Elite-Gen 20. Nachkommengen 40. Aktuelle Gene außer Elite 40. Insgesamt 100 Individuelle Mutationsrate: 1% Genmutation: 1% (Mutationsrate für ein Gen) Anzahl der Generationswechsel: 40
Die Art der Abstraktion ist verrückter oder inkonsistenter Code auf dem Weg. Bitte beachten Sie.
GeneticAlgorithm.py Erstellen Sie zunächst GeneticAlgorithm.py und erstellen Sie genomClass.
GeneticAlgorithm.py
class genom:
genom_list = None
evaluation = None
def __init__(self, genom_list, evaluation):
self.genom_list = genom_list
self.evaluation = evaluation
def getGenom(self):
return self.genom_list
def getEvaluation(self):
return self.evaluation
def setGenom(self, genom_list):
self.genom_list = genom_list
def setEvaluation(self, evaluation):
self.evaluation = evaluation
Diese Klasse wird als Instanzvariable zum Speichern genetischer Informationen und Bewertungswerte verwendet. Weisen Sie mit set einen Wert zu und erhalten Sie mit get einen Wert.
main.py
Verschiedene Konstanten
main.py
#Länge der genetischen Information
GENOM_LENGTH = 100
#Die Größe der Genpopulation
MAX_GENOM_LIST = 100
#Anzahl der Genselektionen
SELECT_GENOM = 20
#Individuelle Mutationswahrscheinlichkeit@0 im Code auf GitHub.1 von 10%Es ist geworden
INDIVIDUAL_MUTATION = 0.01
#Wahrscheinlichkeit einer Genmutation@0 im Code auf GitHub.1 von 10%Es ist geworden
GENOM_MUTATION = 0.01
#Anzahl der zu wiederholenden Generationen
MAX_GENERATION = 40
Die ausführliche Erklärung innerhalb der Funktion ist im Kommentar beschrieben.
create_genom Generieren Sie zufällig die Anzahl der durch das Argument angegebenen Gene und geben Sie sie mit genomClass zurück evaluation Extrahieren Sie genetische Informationen aus einem Individuum und bewerten Sie sie select Gibt eine bestimmte Anzahl von Elitepopulationen zurück, die durch das Argument der Bevölkerung angegeben wurden crossover Holen Sie sich zwei Personen aus dem Argument und geben Sie die beiden daraus generierten Nachkommen in einem Array zurück next_generation_gene_create Ich werde Generationen wechseln. Erstellen Sie aus der aktuellen Bevölkerung, Elite-Bevölkerung, Nachkommen-Bevölkerung mutation Die Mutationsverarbeitung wird basierend auf der aus dem Argument erhaltenen Wahrscheinlichkeit durchgeführt.
def create_genom(length):
main.py
def create_genom(length):
"""
Die zufällige Geninformation der durch das Argument angegebenen Ziffer wird generiert und in der gespeicherten genomClass zurückgegeben.
:param length:Länge der genetischen Information
:return:Generierte Population genomClass
"""
genome_list = []
for i in range(length):
genome_list.append(random.randint(0, 1))
return ga.genom(genome_list, 0)
def evaluation(ga):
main.py
def evaluation(ga):
"""Bewertungsfunktion. Wenn diesmal alle Gene 1 sind, ist dies die optimale Lösung
0, wenn die Gesamtzahl mit dem Gen übereinstimmt.00~1.Bei 00 auswerten
:param ga:Genomklasse zu bewerten
:return:Gibt die ausgewertete genomClass zurück
"""
genom_total = sum(ga.getGenom())
return Decimal(genom_total) / Decimal(len(ga.getGenom()))
def select(ga, elite):
main.py
def select(ga, elite_length):
"""Es ist eine Auswahlfunktion. Treffen Sie eine Elite-Auswahl
Nach dem Sortieren in absteigender Reihenfolge der Bewertung über einem bestimmten Niveau
:param ga:Ein Array von genomClass, um eine Auswahl zu treffen
:param elite_length:Anzahl der zu wählenden Eliten
:return:Gibt eine bestimmte Elite, genomClass, zurück, die ausgewählt wurde
"""
#Sortieren Sie die Bewertungen der Bevölkerung der aktuellen Generation in absteigender Reihenfolge
sort_result = sorted(ga, reverse=True, key=lambda u: u.evaluation)
#Bestimmte Spitzen extrahieren
result = [sort_result.pop(0) for i in range(elite_length)]
return result
def crossover(ga_one, ga_second):
main.py
def crossover(ga_one, ga_second):
"""Es ist eine Kreuzfunktion. Führen Sie eine Zweipunktkreuzung durch.
:param ga:Array von genomClass zum Überqueren
:param ga_one:Erste Person
:param ga_second:Zweite Person
:return:Gibt eine Liste mit zwei Nachkommen von genomClass zurück
"""
#Generieren Sie eine Liste zum Speichern von Nachkommen
genom_list = []
#Stellen Sie die beiden zu ersetzenden Punkte ein →[10:25]→ Von 10 bis 25
cross_one = random.randint(0, GENOM_LENGTH)
cross_second = random.randint(cross_one, GENOM_LENGTH)
#Nehmen Sie das Gen heraus
one = ga_one.getGenom()
second = ga_second.getGenom()
#Kreuz
progeny_one = one[:cross_one] + second[cross_one:cross_second] + one[cross_second:]
progeny_second = second[:cross_one] + one[cross_one:cross_second] + second[cross_second:]
#Erstellen Sie eine genomClass-Instanz und speichern Sie ihre Nachkommen in einer Liste
genom_list.append(ga.genom(progeny_one, 0))
genom_list.append(ga.genom(progeny_second, 0))
return genom_list
def next_generation_gene_create(ga, ga_elite, ga_progeny):
main.py
def next_generation_gene_create(ga, ga_elite, ga_progeny):
"""
Führen Sie die Generierungswechselverarbeitung durch
:param ga:Bevölkerung der aktuellen Generation
:param ga_elite:Elitegruppe der aktuellen Generation
:param ga_progeny:Nachkommengruppe der aktuellen Generation
:return:Bevölkerung der nächsten Generation
"""
#Sortieren Sie die Bewertungen der Bevölkerung der aktuellen Generation in aufsteigender Reihenfolge
next_generation_geno = sorted(ga, reverse=False, key=lambda u: u.evaluation)
#Entfernen Sie die Summe der hinzuzufügenden Elite- und Nachkommengruppe
for i in range(0, len(ga_elite) + len(ga_progeny)):
next_generation_geno.pop(0)
#Fügen Sie der nächsten Generation Elite- und Nachkommengruppen hinzu
next_generation_geno.extend(ga_elite)
next_generation_geno.extend(ga_progeny)
return next_generation_geno
def mutation(ga, individual_mutation, genom_mutation):
main.py
def mutation(ga, individual_mutation, genom_mutation):
"""Es ist eine Mutationsfunktion.
:param ga:Genomklasse zu mutieren
:param individual_mutation:Mutationswahrscheinlichkeit zur Fixierung
:param genom_mutation:Mutationswahrscheinlichkeit für jedes Gen.
:return:Gibt eine mutierte genomClass zurück"""
ga_list = []
for i in ga:
#Eine Mutation tritt mit einer bestimmten Wahrscheinlichkeit für ein Individuum auf
if individual_mutation > (random.randint(0, 100) / Decimal(100)):
genom_list = []
for i_ in i.getGenom():
#Mutationen treten für jede einzelne genetische Information auf
if genom_mutation > (random.randint(0, 100) / Decimal(100)):
genom_list.append(random.randint(0, 1))
else:
genom_list.append(i_)
i.setGenom(genom_list)
ga_list.append(i)
else:
ga_list.append(i)
return ga_list
if name == 'main':
main.py
if __name__ == '__main__':
#Erzeugt die erste Bevölkerung der aktuellen Generation.
current_generation_individual_group = []
for i in range(MAX_GENOM_LIST):
current_generation_individual_group.append(create_genom(GENOM_LENGTH))
for count_ in range(1, MAX_GENERATION + 1):
#Bewerten Sie die Gene der Population der aktuellen Generation und weisen Sie sie genomClass zu
for i in range(MAX_GENOM_LIST):
evaluation_result = evaluation(current_generation_individual_group[i])
current_generation_individual_group[i].setEvaluation(evaluation_result)
#Wählen Sie eine Elite-Person
elite_genes = select(current_generation_individual_group,SELECT_GENOM)
#Überqueren Sie Elite-Gene und speichern Sie sie in der Liste
progeny_gene = []
for i in range(0, SELECT_GENOM):
progeny_gene.extend(crossover(elite_genes[i - 1], elite_genes[i]))
#Erstellen Sie die Bevölkerung der nächsten Generation aus der aktuellen Generation, der Elite und der Nachkommenbevölkerung
next_generation_individual_group = next_generation_gene_create(current_generation_individual_group,
elite_genes, progeny_gene)
#Mutation aller Individuen in der Bevölkerung der nächsten Generation.
next_generation_individual_group = mutation(next_generation_individual_group,INDIVIDUAL_MUTATION,GENOM_MUTATION)
#Die evolutionäre Berechnung einer Generation ist abgeschlossen. Fahren Sie mit der Bewertung fort
#Ordnen Sie die Anwendbarkeit jedes Einzelnen.
fits = [i.getEvaluation() for i in current_generation_individual_group]
#Evolutionsergebnisse bewerten
min_ = min(fits)
max_ = max(fits)
avg_ = sum(fits) / Decimal(len(fits))
#Gibt die Evolutionsergebnisse der aktuellen Generation aus
print "-----Nein.{}Generationsergebnisse-----".format(count_)
print " Min:{}".format(min_)
print " Max:{}".format(max_)
print " Avg:{}".format(avg_)
#Tauschen Sie die aktuelle Generation gegen die nächste Generation aus
current_generation_individual_group = next_generation_individual_group
#Endergebnis Ausgabe
print "Das beste Individuum ist{}".format(elite_genes[0].getGenom())
-----Ergebnisse der 1. Generation-----
Min:0.36
Max:0.63
Avg:0.4999
-----Ergebnisse der 2. Generation-----
Min:0.46
Max:0.65
Avg:0.5653
-----Ergebnisse der 3. Generation-----
Min:0.54
Max:0.67
Avg:0.6098
-----Ergebnisse der 4. Generation-----
...
...
-----Ergebnisse der 39. Generation-----
Min:0.84
Max:0.93
Avg:0.9247
-----Ergebnisse der 40. Generation-----
Min:0.85
Max:0.94
Avg:0.9256
Das beste Individuum ist[1, 1, 0, 1, 1, 1, 0, 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, 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, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Die maximale Anwendbarkeit des ersten Individuums beträgt 0,63, aber die Lösung kann am Ende auf 0,94 angefahren werden. Kurz gesagt, ich konnte die Anzahl der Einsen von 63/100 zunächst auf 94/100 bringen. Wenn Sie es mehrmals ausführen, können Sie zu 100 wechseln
Sie können das Obige kopieren und einfügen, aber es ist ein Ärger, also bringen Sie es von Git. Klonen Sie von GitHub und führen Sie es aus.
$ git clone https://github.com/Azunyan1111/OneMax.git
>>Cloning into 'OneMax'...
>>remote: Counting objects: 5, done.
>>remote: Compressing objects: 100% (4/4), done.
>>remote: Total 5 (delta 0), reused 5 (delta 0), pack-reused 0
>>Unpacking objects: 100% (5/5), done.
$ pwd
>>/Users/admin/Desktop
$ cd OneMax/
$ pwd
>>/Users/admin/Desktop/OneMax
$ ls
>>GeneticAlgorithm.py README.md main.py
$ python main.py
Die Verarbeitung beginnt mit der Ausführung von main.py.
Einführung in die Python-Web-Scraping-Praxis Sammlung von Python-Web-Scraping-Techniken "Es gibt keinen Wert, der nicht abgerufen werden kann" JavaScript-Unterstützung [10.000 Anfragen pro Sekunde !?] Explosives Web-Scraping beginnend mit der Sprache Go [Golang]
Recommended Posts