Erste Schritte mit genetischen Python-Algorithmen
――Ich werde als Studie über die grundlegenden und einfachen Teile genetischer Algorithmen schreiben. ――Um Ihr Verständnis zu vertiefen, schreiben wir den Code des genetischen Algorithmus in Python und verschieben ihn in Form der Lösung einiger Probleme.
Was ist ein genetischer Algorithmus?
Genetischer Algorithmus in Englisch. Der erste Auftritt wurde 1975 von Professor John H. Holland von der University of Michigan vorgeschlagen.
- [Genetischer Algorithmus-Wikipedia](https://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0)
- [John H. Holland-Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%B8%E3%83%A7%E3%83%B3%E3%83%BBH%E3% 83% BB% E3% 83% 9B% E3% 83% A9% E3% 83% B3% E3% 83% 89)
Bis zu einem gewissen Grad wird eine große Anzahl von Elementen, die als "Gene" und "Chromosomen" mit individuellen Attributen behandelt werden, in jedem Individuum erzeugt, und die nächste Generation wird erzeugt, bis gute Ergebnisse für das Zielproblem erzielt werden, während zufällige Elemente einbezogen werden. Es ist ein Algorithmus, der sich wiederholt.
Wie Darwins Evolutionstheorie (als ob ein Individuum, das gut zum Überleben passt, überlebt), werden glücklicherweise die Elemente, die gut zum Problem passen, der nächsten Generation überlassen, oder die Elemente, die gut passen, sind problematisch. Ich werde es als Antwort verwenden.
Es gibt keine Antwort, bevor der Algorithmus ausgeführt wird, und es handelt sich um eine Berechnung, die nach einer übereinstimmenden Antwort sucht, während zufällige Elemente einbezogen werden. Sie ähnelt möglicherweise ein wenig dem verbesserten Lernen von unbeaufsichtigtem Lernen (der Code selbst ist auch ein wenig ähnlich). Es gibt einige Teile, die implementiert werden, und es gibt verschiedene Dinge im Bereich des verbesserten Lernens.
Was für eine Berechnung
Im Folgenden wird ein Element als Chromosom (Chromosom) bezeichnet.
Generieren Sie zunächst zufällig Chromosomen. Diese Nummer ist beliebig. Je größer die Anzahl, desto mehr Berechnungen für eine Generation, je mehr verschiedene Bedingungen in einer Generation generiert werden und desto mehr Variationen gibt es.
Die Bewertungsfunktion wertet dann jedes Element aus, um zu bestimmen, was mit der nächsten Generation zu tun ist. Diese Auswertungsfunktion gibt einen Wert dafür zurück, wie gut sie zum Problem passt. Beim maschinellen Lernen ist es wie eine Fehlerfunktion.
Der Inhalt der Bewertungsfunktion wird je nach Problem beliebig festgelegt. Biologisch ist es beispielsweise ein Index wie "wie stark es gegen die Kälte ist" oder "wie gut die Augen sind". Beispiel: "Wie hoch ist die Punktzahl für ein bestimmtes Problem in einem realen Problem?"
Bestimmen Sie für die nächste Generation anhand eines Elements der aktuellen Generation als Beispiel, wie die Features durch die folgende Berechnung an zukünftige Generationen weitergegeben werden sollen (verschiedene Anpassungen und Auswahlen auch hier). Ich kann es schaffen).
** Frequenzweiche **
Crossover hinterlässt zwei Chromosomen in der nächsten Generation auf eine Weise, die die Eigenschaften der beiden Chromosomen in zwei Hälften erbt. Die Berechnung ist so, dass zwei Kinder als die nächste Generation behandelt werden, indem die Merkmale von ihren Eltern in zwei Hälften geerbt werden.
** Mutation **
Mutationen hinterlassen bei einigen oder den meisten der nächsten Generation Chromosomen mit völlig ungewöhnlichen Eigenschaften.
Es wird verwendet, um zu verhindern, dass nur ähnliche Chromosomen aufgrund von Kreuzungen usw. verbleiben, und um Fälle wie lokale Lösungen (wie voreingenommene und optimale Antworten, die nicht gegeben werden) zu reduzieren.
** Roulette Rad Auswahl **
Es gibt eine Methode namens Roulette-Auswahl als Auswahlmethode, wenn zwei Chromosomen zum Zeitpunkt des Übergangs zur nächsten Generation ausgewählt werden, z. B. Kreuzung.
Dies ist eine zufällige Auswahl, bei der die Auswahlwahrscheinlichkeit umso höher ist, je höher die Leistung der Bewertungsfunktion ist.
Abhängig von der Leistung der Bewertungsfunktion wird das Gewicht der Wahrscheinlichkeit zum Zeitpunkt der zufälligen Extraktion bestimmt und so weiter.
** Turnierauswahl **
Bei der Turnierauswahl wird nach dem zufälligen Extrahieren einer bestimmten Zahl aus dem gesamten Chromosom (z. B. zufälliges Extrahieren von 100 aus insgesamt 2000 Chromosomen) diejenige mit der höchsten Bewertungsfunktion für die erforderliche Anzahl ausgewählt (z. B. durch Kreuzen). Bei Bedarf wird 2) extrahiert.
** Wann wird die Berechnung beendet? **
Wenn der Zielwert der Bewertungsfunktion bekannt ist, kann die Anzahl der Generationen enorm eingestellt werden, bis der Wert erhalten wird. Wenn beispielsweise bei der Routensuche eine Bedingung wie "Eine Route, die das Ziel innerhalb von Minuten erreichen kann" in Ordnung ist, wird die Berechnung abgeschlossen, wenn diese Bedingung erfüllt ist.
Wenn der Zielwert nicht bekannt ist, wird alternativ die Berechnung gestoppt, wenn eine bestimmte Anzahl von Generationen erreicht ist, und der Attributwert des Chromosoms mit dem maximalen Bewertungsfunktionswert wird verwendet. Auf diese Weise können Sie die Berechnung stoppen, z. B. "Berechnen Sie für 200 Generationen und verwenden Sie die mit den besten Ergebnissen", da Sie die klare Antwort oder den zulässigen Wert nicht im Voraus kennen.
Was sind die Eigenschaften / wann ist es geeignet?
Wie oben erwähnt, beziehen genetische Algorithmen in vielen Berechnungen stark zufällige Elemente ein. Daher ändert sich der Rechenaufwand bis zur Lösung des Problems bei jeder Ausführung.
Darüber hinaus gibt es Fälle, in denen die Lösung sofort gelöst wird, und Fälle, in denen die Antwort für längere Zeit nicht erreicht werden kann. Wenn es einen Algorithmus gibt, der für das Problem geeignet ist, gibt es viele Fälle, in denen der Rechenaufwand bei Verwendung viel geringer ist.
Selbst wenn Sie zu einer Lösung gelangen, die gut aussieht, kann es Fälle geben, in denen dies nicht die optimale Lösung ist.
Andererseits kann es für verschiedene Zwecke verwendet werden, selbst in losen Fällen, in denen der optimale Algorithmus nicht in Betracht gezogen werden kann und Sie explorativ nach Antworten suchen möchten.
Als Beispiel für einen Anwendungsfall, der auf dieser Grundlage geeignet ist,
- Ein Fall, in dem es in Ordnung ist, wenn eine Antwort von ca. 80 Punkten anstelle von 100 Punkten erforderlich ist (optimale Lösung)
- Falls keine kurze Rechenzeit erforderlich ist
- Wenn Sie sich keinen optimaleren Algorithmus vorstellen können
Und so weiter.
Implementierung in Python
Versuchen wir, einige Probleme mit genetischen Algorithmen zu lösen.
Was zu verwenden
- Python 3.8.5 --Pylance (zur Typprüfung)
- Wie andere ähnliche Artikel, die ich in der Vergangenheit geschrieben habe, werde ich mit dem eingebauten Modul schreiben, ohne eine Bibliothek usw. zum Lernen zu verwenden.
Punkte, die man sich merken sollte
Als geeigneten Anwendungsfall erwähnte ich "einen Fall, in dem ich mir keinen optimaleren Algorithmus vorstellen kann", aber die in diesem Artikel erwähnten Probleme sind absichtlich einfache Probleme für das Studium, und es gibt viel mehr optimale Lösungen. Wir werden darauf antworten.
Beachten Sie, dass die Verwendung des besten Algorithmus lange dauern kann, um eine schnelle Berechnung durchzuführen.
Import der benötigten Module
Zunächst importieren wir die eingebauten, die verwendet werden sollen.
from __future__ import annotations
from typing import TypeVar, List, Dict
from random import choices, random, randrange, shuffle
from heapq import nlargest
from abc import ABC, abstractmethod
from copy import deepcopy
from datetime import datetime
--Anmerkungen werden verwendet, da die Typanmerkungen verfügbar sind, die in zukünftigen Python-Versionen übernommen werden.
- Um Typanmerkungen verwenden zu können, importieren wir das, was wir benötigen, aus dem Typisierungspaket. --choices ist eine Funktion, die zufällig eine beliebige Anzahl von iterierbaren auswählt, die im Argument angegeben sind. Es wird verwendet, um die nächste Generation von Personen auszuwählen. Sie können auch die Größe der Wahrscheinlichkeit für jede Person mit dem Gewichtungsargument festlegen. --random ist eine Funktion, die Zufallszahlen im Bereich von 0,0 bis 1,0 erhält. --randrange ist eine Funktion, die zufällig einen Wert aus dem Wertebereich erhält, der erhalten wird, wenn er durch den Bereich angegeben wird (z. B. zufällig einen von 0 bis 9). --shuffle ist eine Funktion, die iterierbare Elemente mischt. --nlargest ist eine Funktion, die n große in der angegebenen Reihenfolge innerhalb des angegebenen iterierbaren Elements abruft. Es wird verwendet, um die Top-Personen in der Turnierauswahl zu extrahieren.
- Um zwei Probleme zu lösen, importieren wir dieses Mal das Paket abc (abstrakte Basisklasse), um die abstrakte Klasse zu verwenden. --Deepcopy ist, wie der Name schon sagt, eine Funktion, die Elemente tief kopiert. Deep Copy wird verwendet, wenn Personen der nächsten Generation erstellt werden.
Definition einer einzelnen abstrakten Klasse
Wie oben erwähnt, werden in diesem Artikel zwei Probleme behandelt. Daher fügen wir für jedes Problem eine einzelne abstrakte Klasse hinzu, die geerbt werden soll.
Durch Hinzufügen von "@ abstractmethod" und eines Dekorators können Sie die geerbte Klasse mit einem Fehler verärgern, es sei denn, Sie überschreiben die Methode mit dem Dekorator.
class Chromosome(ABC):
"""
Eine abstrakte Klasse, die sich mit Chromosomen befasst (ein Element eines genetischen Algorithmus).
"""
@abstractmethod
def get_fitness(self) -> float:
"""
Für die Bewertungsfunktion Y, um die Exzellenz der Chromosomen für das interessierende Problem zu erhalten
Abstrakte Methode.
Returns
-------
fitness : float
Wert der Chromosomenqualität für das interessierende Problem. Je höher das Problem
Es wird ein geeignetes Chromosom.
Es wird auch verwendet, um das Ende eines genetischen Algorithmus zu bestimmen.
"""
...
@classmethod
@abstractmethod
def make_random_instance(cls) -> Chromosome:
"""
Erstellen Sie eine Instanz mit zufälligen Merkmalen (Attributwerte).
Abstrakte Methode.
Returns
-------
instance : Chromosome
Die generierte Instanz.
"""
...
@abstractmethod
def mutate(self) -> None:
"""
Eine abstrakte Verarbeitungsmethode, die (plötzlich) ein Chromosom mutiert.
Es werden zufällig unterschiedliche Werteinstellungen wie Instanzattribute ausgeführt.
"""
...
@abstractmethod
def exec_crossover(self, other: Chromosome) -> List[Chromosome]:
"""
Crossover wird mit Bezug auf eine andere im Argument angegebene Person ausgeführt.
Parameters
----------
other : Chromosome
Eine andere Person, die beim Überqueren verwendet wird.
Returns
-------
result_chromosomes : list of Chromosome
Zwei Individuen (Chromosomen), die nach der Kreuzung erzeugt wurden.
"""
...
def __lt__(self, other: Chromosome) -> bool:
"""
Eine Funktion zum Vergleichen des Wertes der Bewertungsfunktion, die zum Vergleichen zwischen Personen verwendet wird.
Parameters
----------
other : Chromosome
Andere zu vergleichende Personen.
Returns
-------
result_bool : bool
Boolescher Wert, ob die geringere Bedingung erfüllt ist oder nicht.
"""
return self.get_fitness() < other.get_fitness()
Die für den genetischen Algorithmus erforderlichen Schnittstellen für Auswertungsfunktion (get_fitness), Mutation (mutate) und Crossover (exec_crossover) werden bereitgestellt. Es wird nur die Ellipsis-Instanz (...) beschrieben und die anderen werden weggelassen (überschreiben mit dem Vererbungsziel).
Da vor dem Starten des Algorithmus die erste Generation generiert werden muss, haben wir eine Methode namens make_random_instance als Klassenmethode vorbereitet.
Da es notwendig ist, den Wert über dem Wert der Bewertungsfunktion zu extrahieren, wird die Methode von "lt" zum Vergleich definiert, damit der Wert der Bewertungsfunktion für einen kleinen Vergleich verwendet werden kann.
Definition von Klassen genetischer Algorithmen
Wir werden eine Klasse für den genetischen Algorithmus definieren.
C = TypeVar('C', bound=Chromosome)
class GeneticAlgorithm:
SelectionType = int
SELECTION_TYPE_ROULETTE_WHEEL: SelectionType = 1
SELECTION_TYPE_TOURNAMENT: SelectionType = 2
def __init__(
self, initial_population: List[C],
threshold: float,
max_generations: int, mutation_probability: float,
crossover_probability: float,
selection_type: SelectionType) -> None:
"""
Eine Klasse, die sich mit genetischen Algorithmen befasst.
Parameters
----------
initial_population : list of Chromosome
Population der ersten Generation (chromosomale Gruppe).
threshold : float
Ein Schwellenwert zur Bestimmung der Problemlösung. Personen, die diesen Wert überschreiten
Die Berechnung endet, wenn sie auftritt.
max_generations : int
Maximale Anzahl von Generationen, die im Algorithmus ausgeführt werden sollen.
mutation_probability : float
Mutationswahrscheinlichkeit (0.0～1.0）。
crossover_probability : float
Übergangswahrscheinlichkeit (0.0～1.0）。
selection_type : int
Auswahlmethode. Geben Sie einen der folgenden konstanten Werte an.
- SELECTION_TYPE_ROULETTE_WHEEL
- SELECTION_TYPE_TOURNAMENT
"""
self._population: List[Chromosome] = initial_population
self._threshold: float = threshold
self._max_generations: int = max_generations
self._mutation_probability: float = mutation_probability
self._crossover_probability: float = crossover_probability
self._selection_type: int = selection_type
Die Stelle "C = TypeVar (" C ", gebunden = Chromosom)" definiert den Typ als generisch (Chromosom C).
Wenn es sich um eine Unterklasse von Chromosomen usw. handelt, wird es bei der Typprüfung von Pylance (bestimmt als Unterklasse ≠ Chromosomenklasse) abgefangen, also verwende ich es.
Das gebundene Argument ist ein Argument, das eine Einschränkung wie "OK, wenn es sich um ein Chromosom oder eine Unterklasse von Chromosom handelt" angibt.
In Bezug auf den Konstruktor "erste Population", die vom Algorithmus benötigt wird, "Schwelle der Bewertungsfunktion, die zur Beurteilung des Stopps des Algorithmus verwendet wird", "Obergrenze der Anzahl der Generationen", "Mutationswahrscheinlichkeit", "Überkreuzungswahrscheinlichkeit", "Auswahlmethode wie Roulette-Auswahl" Angegeben.
Zusätzlich wird die Konstante der Auswahlmethode definiert (SELECTION_TYPE_ROULETTE_WHEEL: SelectionType = 1 usw.).
Implementierung der Roulette-Auswahl
Wir werden der GeneticAlgorithm-Klasse eine Roulette-Auswahlverarbeitung hinzufügen.
def _exec_roulette_wheel_selection(self) -> List[Chromosome]:
"""
Wählen Sie Roulette und zwei Personen (Chromosomen) aus, die für die Kreuzung usw. verwendet werden sollen.
erhalten.
Returns
-------
selected_chromosomes : list of Chromosome
Eine Liste mit den beiden ausgewählten Personen (Chromosomen). Der Auswahlprozess ist eine Bewertungsfunktion
Es wird zufällig mit dem durch (Fitnessmethode) festgelegten Gewicht extrahiert.
Notes
-----
Es kann nicht für Probleme verwendet werden, bei denen der Ergebniswert der Bewertungsfunktion negativ ist.
"""
weights: List[float] = [
chromosome.get_fitness() for chromosome in self._population]
selected_chromosomes: List[Chromosome] = choices(
self._population, weights=weights, k=2)
return selected_chromosomes
Bei der Roulette-Auswahl werden Personen zufällig ausgewählt, aber das Gewicht wird so eingestellt, dass derjenige mit dem höheren Wert, der durch die Bewertungsfunktion erhalten wird, Priorität hat.
Stellen Sie sich in Bezug auf dieses Gewicht das folgende Roulette vor, vorausgesetzt, es gibt fünf Personen von A bis E.
Der Wert der Bewertungsfunktion jedes Einzelnen ist der Bereich auf dem Roulette. Personen mit einer kleinen Fläche (Personen mit einer geringen Bewertung durch die Bewertungsfunktion) können ebenfalls ausgewählt werden, aber die Wahrscheinlichkeit ist gering.
Umsetzung der Turnierauswahl
In ähnlicher Weise werden wir der GeneticAlgorithm-Klasse eine Turnierauswahl hinzufügen. Ob Roulette-Auswahl oder Turnierauswahl verwendet wird, hängt von der Auswahltyp-Spezifikation im Konstruktor ab.
def _exec_tournament_selection(self) -> List[Chromosome]:
"""
Zwei Personen für Turnierauswahl und Kreuzung
Holen Sie sich (Chromosom).
Returns
-------
selected_chromosomes : list of Chromosome
Eine Liste mit den beiden ausgewählten Personen (Chromosomen). Turnier
Die beiden obersten Personen werden aus der Anzahl der Fälle extrahiert, die im Argument für angegeben sind
Einstellen.
"""
participants_num: int = len(self._population) // 2
participants: List[Chromosome] = choices(self._population, k=participants_num)
selected_chromosomes: List[Chromosome] = nlargest(n=2, iterable=participants)
return selected_chromosomes
Bei der Turnierauswahl wird zuerst die im Turnier verwendete Population extrahiert. Dieses Mal wird die Hälfte der Bevölkerung durch harte Codierung ausgewählt.
Da der Rückgabewert 2 Personen beträgt, werden die beiden obersten Personen durch die größte Funktion extrahiert. Da die Elemente in der Liste innerhalb dieser Funktion verglichen werden müssen, muss die Methode "lt" in der Chromosomenklasse festgelegt werden.
Implementierung der Übergangsverarbeitung zur nächsten Generation
Jetzt fügen wir der GeneticAlgorithm-Klasse eine Verarbeitung hinzu, um von der aktuellen zur nächsten Generation zu wechseln.
Was zu tun ist
- [1] Extrahieren Sie zwei Personen gemäß der Auswahlmethode (Roulette-Auswahl usw.) (benannte Eltern).
- [2] Ändern Sie die beiden Personen, die gemäß der im Konstruktor angegebenen Überkreuzungswahrscheinlichkeit und Mutationswahrscheinlichkeit extrahiert wurden (wenn die Überkreuzung nicht mit Zufallszahl und Wahrscheinlichkeit auftritt, setzen Sie die übergeordnete Person so, wie sie ist, auf die nächste Generation ).
- [3]. Fügen Sie die beiden vorbereiteten Personen zur Liste der Personen der nächsten Generation hinzu.
- [4] Wiederholen Sie [1] - [3], bis die Liste der Personen der nächsten Generation mit der Liste der Personen der aktuellen Generation übereinstimmt.
Es wird der Prozess sein.
def _to_next_generation(self) -> None:
"""
Generierte das Individuum der nächsten Generation (Chromosom) und generierte den Attributwert der Population
Ersetzen Sie durch die Bevölkerung der nächsten Generation.
"""
new_population: List[Chromosome] = []
#Der Vergleich der Anzahl der Fälle ist nicht gleich, wenn man bedenkt, dass die Anzahl der Fälle der ursprünglichen Bevölkerung ungerade ist.
#Die Beurteilung erfolgt aufgrund geringerer Bedingungen.
while len(new_population) < len(self._population):
parents: List[Chromosome] = self._get_parents_by_selection_type()
next_generation_chromosomes: List[Chromosome] = \
self._get_next_generation_chromosomes(parents=parents)
new_population.extend(next_generation_chromosomes)
#Aufgrund der Bequemlichkeit, die Liste der nächsten Generation um zwei zu erhöhen, ist die Anzahl der Fälle größer als die ursprüngliche Liste
#Wenn es viele gibt, entfernen Sie sie aus der Liste und stimmen Sie die Anzahl der Elemente in der Liste mit der ursprünglichen Liste ab.
if len(new_population) > len(self._population):
del new_population[0]
self._population = new_population
def _get_next_generation_chromosomes(
self, parents: List[Chromosome]) -> List[Chromosome]:
"""
Behandle als die nächste Generation aus der berechneten Liste von zwei Elternteilen
Holen Sie sich eine Liste von zwei Populationen.
Überqueren oder mutieren mit einer bestimmten Wahrscheinlichkeit, wenn die Wahrscheinlichkeit nicht erfüllt ist, ist der Wert des Arguments
Es wird so wie es ist als nächste Generation eingestellt.
Parameters
----------
parents : list of Chromosome
Liste von zwei Personen des berechneten Elternteils
Returns
-------
next_generation_chromosomes : list of Chromosome
Eine Liste mit zwei Personen, die als nächste Generation festgelegt wurden.
"""
random_val: float = random()
next_generation_chromosomes: List[Chromosome] = parents
if random_val < self._crossover_probability:
next_generation_chromosomes = parents[0].exec_crossover(
other=parents[1])
random_val = random()
if random_val < self._mutation_probability:
for chromosome in next_generation_chromosomes:
chromosome.mutate()
return next_generation_chromosomes
def _get_parents_by_selection_type(self) -> List[Chromosome]:
"""
Erhalten Sie eine Liste von zwei Eltern (Chromosomen) gemäß der Auswahlmethode.
Returns
-------
parents : list of Chromosome
Eine Liste der beiden Individuen (Chromosomen) des erworbenen Elternteils.
Raises
------
ValueError
Wenn eine nicht unterstützte Auswahlmethode angegeben wird.
"""
if self._selection_type == self.SELECTION_TYPE_ROULETTE_WHEEL:
parents: List[Chromosome] = self._exec_roulette_wheel_selection()
elif self._selection_type == self.SELECTION_TYPE_TOURNAMENT:
parents = self._exec_tournament_selection()
else:
raise ValueError(
'Eine nicht unterstützte Auswahlmethode wird angegeben: %s'
% self._selection_type)
return parents
Implementierung der Verarbeitung zum Ausführen des Algorithmus
Ich werde einen Prozess schreiben, der den Übergang zur nächsten Generation wiederholt, bis der Wert der Bewertungsfunktion den Schwellenwert überschreitet (≈ eine Person, die den Zielwert erreicht, wird geboren) oder die Obergrenze der Anzahl der Generationen überschreitet.
In Bezug auf maschinelles Lernen ist es wie Code zum Lernen. Es ist wie in der Epoche, die Generationen maschinelles Lernen nennen. Die beste Person für jede Generation wird von der Druckfunktion als Information ausgegeben.
Das beste Individuum entspricht jedoch "dem besten Individuum aller Generationen". Bitte beachten Sie, dass es sich nicht um einen Wert pro Epoche wie maschinelles Lernen handelt.
def run_algorithm(self) -> Chromosome:
"""
Eine Instanz eines Individuums (Chromosom), die einen genetischen Algorithmus ausführt und zur Ausführung führt
Bekommen.
Returns
-------
betst_chromosome : Chromosome
Individuelles Ergebnis der Algorithmusausführung. Personen, die den Schwellenwert in der Bewertungsfunktion überschreiten
Oder wenn der Schwellenwert nicht überschritten wird, wurde die angegebene Anzahl von Generationen erreicht.
Die Person mit dem höchsten Bewertungsfunktionswert zu diesem Zeitpunkt wird eingestellt.
"""
best_chromosome: Chromosome = \
deepcopy(self._get_best_chromosome_from_population())
for generation_idx in range(self._max_generations):
print(
datetime.now(),
f'Anzahl der Generationen: {generation_idx}'
f'Beste individuelle Informationen: {best_chromosome}'
)
if best_chromosome.get_fitness() >= self._threshold:
return best_chromosome
self._to_next_generation()
currrent_generation_best_chromosome: Chromosome = \
self._get_best_chromosome_from_population()
current_gen_best_fitness: float = \
currrent_generation_best_chromosome.get_fitness()
if best_chromosome.get_fitness() < current_gen_best_fitness:
best_chromosome = deepcopy(currrent_generation_best_chromosome)
return best_chromosome
def _get_best_chromosome_from_population(self) -> Chromosome:
"""
Wählen Sie aus der Liste der Populationen das Individuum (Chromosom) mit dem höchsten Wert für die Bewertungsfunktion aus.
erhalten.
Returns
-------
best_chromosome : Chromosome
Die Person mit dem höchsten Bewertungsfunktionswert in der Liste.
"""
best_chromosome: Chromosome = self._population[0]
for chromosome in self._population:
if best_chromosome.get_fitness() < chromosome.get_fitness():
best_chromosome = chromosome
return best_chromosome
Fügen Sie ein einfaches Formelproblem zum Überprüfen des Vorgangs hinzu und versuchen Sie es.
Lassen Sie uns ein einfaches Problem erstellen und den Algorithmus ausführen, um die Implementierung des genetischen Algorithmus zu bestätigen.
Verwenden Sie das Problem, x und y zu finden, damit die Werte in den folgenden Formeln maximiert werden.
6x - x^2 + 4y - y^2
Die Antwort ist 13, wenn x = 3 und y = 2, was das Maximum ist.
Um die Operation zu überprüfen, ist es, wie oben erwähnt, nicht erforderlich, den genetischen Algorithmus zu verwenden (vielmehr ist dies hinsichtlich der Berechnungszeit nicht vorzuziehen).
Erben Sie die Chromosomenklasse, eine abstrakte Klasse, die im Voraus erstellt wurde.
class SimpleEquationProblem(Chromosome):
def __init__(self, x: int, y: int) -> None:
"""
Die folgende einfache Formel zur Überprüfung der Funktionsweise des genetischen Algorithmus
6x - x^2 + 4 * y - y^2
Eine Klasse, die sich mit dem Problem befasst, die Werte von x und y zu finden, die den Wert von maximieren.
(Die richtige Antwort lautet x= 3, y = 2）
Parameters
----------
x : int
Der Anfangswert von x.
y : int
Der Anfangswert von y.
"""
self.x = x
self.y = y
Wir werden Bewertungsfunktionen hinzufügen. Je größer der Wert der Bewertungsfunktion ist, desto besser wird sie vom genetischen Algorithmus beurteilt. Dieses Mal besteht das Problem jedoch darin, einfach die größeren Werte x und y zu finden, also $ 6 x - x ^ 2 + 4y - y ^ Verwenden Sie den berechneten Wert von 2 $.
def get_fitness(self) -> float:
"""
6x mit aktuellen x- und y-Werten- x^2 + 4 * y - y^Vom Berechnungsergebnis von Gleichung 2
Eine Methode, die als Bewertungsfunktion zum Abrufen des Werts verwendet wird.
Returns
-------
fitness : int
Der Wert des Berechnungsergebnisses der Formel.
"""
x: int = self.x
y: int = self.y
return 6 * x - x ** 2 + 4 * y - y ** 2
Die Klassenmethode make_random_instance, die während der ersten Populationsgenerierung verwendet wird, sollte x und y auf zufällige Werte zwischen 0 und 99 setzen.
@classmethod
def make_random_instance(cls) -> SimpleEquationProblem:
"""
Von der SimpleEquationProblem-Klasse mit einem zufälligen Anfangswert
Erstellen Sie eine Instanz.
Returns
-------
problem : SimpleEquationProblem
Die generierte Instanz. x und y sind zufällig im Bereich von 0 bis 99
Der Wert wird eingestellt.
"""
x: int = randrange(100)
y: int = randrange(100)
problem = SimpleEquationProblem(x=x, y=y)
return problem
Für die Variation haben wir berechnet, ob der Wert von x oder y um 1 addiert oder subtrahiert werden soll.
def mutate(self) -> None:
"""
Mutant (plötzlich) ein Individuum (abhängig von der Zufallszahl, dem Wert von x oder y
1 Zunahme / Abnahme).
"""
value: int = choices([1, -1], k=1)[0]
if random() > 0.5:
self.x += value
return
self.y += value
Ich werde die Frequenzweiche auf die gleiche Weise schreiben. Crossover erbt die Eigenschaften der beiden Personen in zwei Hälften und gibt zwei Personen der nächsten Generation zurück.
def exec_crossover(
self, other: SimpleEquationProblem
) -> List[SimpleEquationProblem]:
"""
Crossover wird mit Bezug auf eine andere im Argument angegebene Person ausgeführt.
Parameters
----------
other : SimpleEquationProblem
Eine andere Person, die beim Überqueren verwendet wird.
Returns
-------
result_chromosomes : list of SimpleEquationProblem
Eine Liste mit den beiden Personen, die nach dem Crossover generiert wurden. Eltern werden
Es ist ein Individuum, das von jedem Individuum die Hälfte der Werte von x und y erbt.
"""
child_1: SimpleEquationProblem = deepcopy(self)
child_2: SimpleEquationProblem = deepcopy(other)
child_1.y = other.y
child_2.x = self.x
result_chromosomes: List[SimpleEquationProblem] = [
child_1, child_2,
]
return result_chromosomes
Da wir bei der Ausführung des Algorithmus die besten Einzelinformationen für jede Generation ausgeben möchten, schreiben Sie die Verarbeitung dafür in die Methode __str__.
def __str__(self) -> str:
"""
Gibt die Zeichenfolge der einzelnen Informationen zurück.
Returns
-------
info : str
Zeichenkette einzelner Informationen.
"""
x: int = self.x
y: int = self.y
fitness: float = self.get_fitness()
info: str = f'x = {x}, y = {y}, fitness = {fitness}'
return info
Verschieben wir das Problem der SimpleEquationProblem-Klasse
Ich werde es tatsächlich bewegen.
if __name__ == '__main__':
simple_equation_initial_population: List[SimpleEquationProblem] = \
[SimpleEquationProblem.make_random_instance() for _ in range(30)]
ga: GeneticAlgorithm = GeneticAlgorithm(
initial_population=simple_equation_initial_population,
threshold=13,
max_generations=100,
mutation_probability=0.2,
crossover_probability=0.3,
selection_type=GeneticAlgorithm.SELECTION_TYPE_TOURNAMENT)
_ = ga.run_algorithm()
Wir haben 30 Personen, 100 maximale Generationen, 20% Mutationswahrscheinlichkeit, 30% Crossover-Wahrscheinlichkeit und Turnierauswahlmethode ausgewählt. Da jede Nummer fest ist, gibt es keinen besonderen Grund, sie auszuwählen (Auswahl nach Atmosphäre).
Wenn der Wert der Bewertungsfunktion jedoch wie unten gezeigt negativ sein kann, kann die Roulette-Auswahl nicht ausgewählt werden (aus Gründen wie dem Gewicht), sodass die Turnierauswahl angegeben wird.
** Roulette-Auswahl ** ... Diese Methode ist die Auswahlmethode, die verwendet wurde, als Holland sie zum ersten Mal vorschlug, und sie ist die bekannteste Auswahlmethode. Es wird jedoch davon ausgegangen, dass die Anpassungsfähigkeit keine negative Zahl annimmt. [Genetischer Algorithmus-Wikipedia](https://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0 #% E3% 83% AB% E3% 83% BC% E3% 83% AC% E3% 83% 83 % E3% 83% 88% E9% 81% B8% E6% 8A% 9E)
Auch diesmal weiß ich, dass die Antwort für den Maximalwert 13 ist, also habe ich 13 als Schwellenwert angegeben.
Bei der Ausführung ist die Ausgabe wie folgt. Wie im Abschnitt zur Erklärung des Algorithmus zu Beginn erläutert, weist der genetische Algorithmus eine starke Zufälligkeit auf, sodass er sofort enden kann oder eine große Anzahl von Generationen erfordert und sich das Ergebnis bei jeder Ausführung ändert.
2020-10-31 19:24:39.948226 Anzahl der Generationen:0 Beste individuelle Informationen: x = 14, y = 6, fitness = -124
2020-10-31 19:24:39.960250 Anzahl der Generationen:1 Beste individuelle Informationen: x = 14, y = 5, fitness = -117
2020-10-31 19:24:39.961220 Anzahl der Generationen:2 Beste individuelle Informationen: x = 13, y = 5, fitness = -96
2020-10-31 19:24:39.962218 Anzahl der Generationen:3 Beste individuelle Informationen: x = 13, y = 4, fitness = -91
2020-10-31 19:24:39.975251 Anzahl der Generationen:4 Beste individuelle Informationen: x = 12, y = 4, fitness = -72
2020-10-31 19:24:39.982250 Anzahl der Generationen:5 Beste individuelle Informationen: x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.982250 Anzahl der Generationen:6 Beste individuelle Informationen: x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.996219 Anzahl der Generationen:7 Beste individuelle Informationen: x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.997251 Anzahl der Generationen:8 Beste individuelle Informationen: x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.998224 Anzahl der Generationen:9 Beste individuelle Informationen: x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.999254 Anzahl der Generationen:10 Beste individuelle Informationen: x = 11, y = 2, fitness = -51
2020-10-31 19:24:40.000221 Anzahl der Generationen:11 Beste individuelle Informationen: x = 9, y = 2, fitness = -23
2020-10-31 19:24:40.001250 Anzahl der Generationen:12 Beste individuelle Informationen: x = 9, y = 2, fitness = -23
2020-10-31 19:24:40.001250 Anzahl der Generationen:13 Beste individuelle Informationen: x = 9, y = 2, fitness = -23
2020-10-31 19:24:40.002251 Anzahl der Generationen:14 Beste individuelle Informationen: x = 8, y = 2, fitness = -12
2020-10-31 19:24:40.003250 Anzahl der Generationen:15 Beste individuelle Informationen: x = 8, y = 2, fitness = -12
2020-10-31 19:24:40.004217 Anzahl der Generationen:16 Beste individuelle Informationen: x = 6, y = 2, fitness = 4
2020-10-31 19:24:40.005251 Anzahl der Generationen:17 Beste individuelle Informationen: x = 6, y = 2, fitness = 4
2020-10-31 19:24:40.006252 Anzahl der Generationen:18 Beste individuelle Informationen: x = 5, y = 3, fitness = 8
2020-10-31 19:24:40.006252 Anzahl der Generationen:19 Beste individuelle Informationen: x = 5, y = 2, fitness = 9
2020-10-31 19:24:40.007219 Anzahl der Generationen:20 Beste individuelle Informationen: x = 4, y = 2, fitness = 12
2020-10-31 19:24:40.008219 Anzahl der Generationen:21 Beste individuelle Informationen: x = 3, y = 2, fitness = 13
Dieses Mal ist die Antwort von x = 3 und y = 2 für die 22. Generation erforderlich, und es kann bestätigt werden, dass der Wert der Bewertungsfunktion 13 beträgt (dieser Bereich ähnelt dem Lernen von Deep Learning). ..
Versuchen Sie, das Problem der maskierten Berechnung von SEND + MORE = MONEY zu lösen
Ich habe bestätigt, dass es mit einem einfachen Problem funktioniert, also werde ich versuchen, ein anderes Problem mit einem etwas komplizierteren zu lösen.
Wir werden uns mit dem SEND + MORE = MONEY-Problem befassen, das eine der sogenannten Kryptorithmetiken ist.
Was ist das Problem SEND + MORE = MONEY?
Es ist ein Problem, das die folgende Berechnung ermöglicht. Wörter wie SENDEN und GELD haben keine besondere Bedeutung.
Sie können jedem Buchstaben eine Zahl von 0 bis 9 zuweisen. Weisen Sie beispielsweise S 3, 5 E usw. zu (einige Muster enthalten 0 nicht als Option, in diesem Artikel wird jedoch 0 als Option eingefügt).
Sie können jedoch nicht die gleiche Nummer einem anderen Buchstaben zuweisen (Sie können S nicht auf 8 setzen und E kann auch 8 zuweisen).
4-stelliger S-Wert, 3-stelliger E-Wert, 2-stelliger N-Wert, 1-stelliger D-SEND-Wert, 4-stelliger M-Wert, 3-stelliger O-Wert, 2-stelliger R-Wert, 1-stelliger Wert Eine Kombination, bei der die Summe der MEHR Werte, die aus E bestehen, genau mit dem Wert von GELD übereinstimmt, der aus 5 Ziffern M, 4 Ziffern O, 3 Ziffern N, 2 Ziffern E und 1 Ziffern Y besteht. Das Problem ist zu fragen.
Wenn die Zeichen gleich sind, sind die zuzuweisenden Nummern gleich. Mit anderen Worten, wenn Sie M von MEHR 8 zuweisen, müssen Sie M von GELD auf 8 setzen.
SEND + MORE = Klasse für GELDproblem hinzufügen
Wie bei der SimpleEquationProblem-Klasse werden Klassen hinzugefügt, die von der Chromosome-Klasse erben. Der Ablauf entspricht fast dem von SimpleEquationProblem.
LetterDict = Dict[str, int]
class SendMoreMoneyProblem(Chromosome):
LETTERS: List[str] = ['S', 'E', 'N', 'D', 'M', 'O', 'R', 'Y']
def __init__(self, letters_dict: LetterDict) -> None:
"""
SEND + MORE =Das maskierte Berechnungsproblem von MONEY mit einem genetischen Algorithmus
Klasse zu lösen.
Parameters
----------
letters_dict : LetterDict
Jedes der acht im Problem verwendeten Zeichen (Schlüssel) und der zugewiesene numerische Wert (Wert)
Ein Wörterbuch, in dem die Anfangswerte von gespeichert sind.
"""
self.letters_dict: LetterDict = letters_dict
Dieses Mal verwenden wir ein Wörterbuch, das das Zielzeichen für den Schlüssel und die dem Wert zugewiesene Nummer enthält. Daher haben wir einen Typalias namens LetterDict definiert.
Wir werden der SendMoreMoneyProblem-Klasse Methoden für die Auswertungsfunktion hinzufügen. Die Bewertungsfunktion wird erstellt, indem die Anzahl der Ziffern für jedes Zeichen wie SEND, MORE und MONEY addiert wird und die Differenz zwischen dem MONEY-Wert und dem Gesamtwert von SEND + MORE berechnet wird.
def get_fitness(self) -> float:
"""
SENDEN Sie nach dem numerischen Wert, der jedem aktuellen Zeichen zugewiesen ist+Mit MEHR Nummern
Eine Methode für die Bewertungsfunktion basierend auf der Differenz zwischen den numerischen Werten von GELD.
Notes
-----
Weil der Wert der Bewertungsfunktion des genetischen Algorithmus hoch bewertet wird
Der Wert wird so eingestellt, dass der Wert umso niedriger ist, je größer der Fehler ist.
Wird zurückgegeben.
Returns
-------
fitness : int
SEND +Bewertungswert basierend auf der Differenz zwischen dem MORE-Wert und dem MONEY-Wert.
Je kleiner die Differenz ist, desto größer ist der eingestellte Wert.
"""
send_val: int = self._get_send_val()
more_val: int = self._get_more_val()
money_val: int = self._get_money_val()
difference: int = abs(money_val - (send_val + more_val))
return 1 / (difference + 1)
def _get_send_val(self) -> int:
"""
Ermitteln Sie den Wert von SEND anhand des numerischen Werts jedes aktuell zugewiesenen Zeichens.
Returns
-------
send_val : int
Der Wert von SEND durch den numerischen Wert jedes aktuell zugewiesenen Zeichens.
"""
s: int = self.letters_dict['S']
e: int = self.letters_dict['E']
n: int = self.letters_dict['N']
d: int = self.letters_dict['D']
send_val: int = s * 1000 + e * 100 + n * 10 + d
return send_val
def _get_more_val(self) -> int:
"""
Ermitteln Sie den Wert von MORE anhand des numerischen Werts jedes aktuell zugewiesenen Zeichens.
Parameters
----------
more_val : int
Der Wert von MORE durch den numerischen Wert jedes aktuell zugewiesenen Zeichens
"""
m: int = self.letters_dict['M']
o: int = self.letters_dict['O']
r: int = self.letters_dict['R']
e: int = self.letters_dict['E']
more_val: int = m * 1000 + o * 100 + r * 10 + e
return more_val
def _get_money_val(self):
"""
Ermitteln Sie den Wert von GELD anhand des numerischen Werts jedes aktuell zugewiesenen Zeichens.
Returns
-------
money_val : int
Der Wert von GELD basiert auf dem numerischen Wert jedes aktuell zugewiesenen Zeichens.
"""
m: int = self.letters_dict['M']
o: int = self.letters_dict['O']
n: int = self.letters_dict['N']
e: int = self.letters_dict['E']
y: int = self.letters_dict['Y']
money_val = m * 10000 + o * 1000 + n * 100 + e * 10 + y
return money_val
Je größer der Wert im genetischen Algorithmus ist, desto besser, aber je kleiner die Differenz, desto besser. Daher wird der Rückgabewert auf "1 / (Differenz + 1)" gesetzt. Je größer die Differenz, desto kleiner der Wert.
Der Teil "+ 1" ist ein Wert, der verhindert, dass eine 0-Division auftritt. Da die minimale Differenz 0 ist, können wir sehen, dass der maximale Wert der Bewertungsfunktion "1/1" ist, was 1 ist (also ist der Schwellenwert bei der Ausführung des Algorithmus 1).
Wir werden Klassenmethoden für die Instanziierung definieren. Dies ist nicht schwierig, indem Sie einfach jedes Zeichen so zuweisen, dass es nicht die Zahlen 0-9 abdeckt.
@classmethod
def make_random_instance(cls) -> SendMoreMoneyProblem:
"""
Von der SendMoreMoneyProblem-Klasse mit einem zufälligen Anfangswert
Erstellen Sie eine Instanz.
Returns
-------
problem : SendMoreMoneyProblem
Die generierte Instanz. Jedes Zeichen hat einen Bereich von 0-9
Die Werte werden so eingestellt, dass sich die Zahlen nicht überschneiden.
"""
num_list: List[int] = list(range(10))
shuffle(num_list)
num_list = num_list[:len(cls.LETTERS)]
letters_dict: LetterDict = {
char: num for (char, num) in zip(cls.LETTERS, num_list)}
problem: SendMoreMoneyProblem = SendMoreMoneyProblem(
letters_dict=letters_dict)
return problem
Ich werde die Verarbeitung der Mutation schreiben. Der Inhalt der Variation ist so einfach wie das Ändern in eine andere Zahl, um nicht ein zufällig ausgewähltes Zeichen abzudecken.
def mutate(self) -> None:
"""
Stummschalten einer Person (plötzlich) (zufällig ein bestimmter Zeichenwert zugewiesen)
Durch eine nicht vorhandene Nummer ersetzen.
"""
target_char: str = choices(self.LETTERS, k=1)[0]
not_assigned_num: int = self._get_not_assigned_num()
self.letters_dict[target_char] = not_assigned_num
def _get_not_assigned_num(self) -> int:
"""
Ruft die Nummer ab, die nicht jedem Zeichen zugewiesen ist.
Returns
-------
not_assigned_num : int
Eine Nummer, die nicht jedem Zeichen zugewiesen ist. Während es 8 Zeichen gibt,
Da es 10 Nummern von 0 bis 9 gibt, gibt es 2 nicht zugewiesene Nummern,
Einer von ihnen ist eingestellt.
"""
values: list = list(self.letters_dict.values())
not_assigned_num: int = -1
for num in range(10):
if num in values:
continue
not_assigned_num = num
break
return not_assigned_num
Als nächstes werde ich die Verarbeitung der Kreuzung schreiben. Ich habe mich gefragt, was ich mit dem Crossover-Prozess machen soll, aber ich habe die folgenden Inhalte erstellt.
- [1] Kopieren Sie die übergeordnete Person.
- [2] Bei jeder der beiden untergeordneten Personen kann jeweils die Hälfte (jeweils 4 Zeichen von SEND und MORY) die numerischen Werte verschiedener Eltern erben (aufgrund der Verdoppelung numerischer Werte stimmen jedoch die Zuordnung von Zeichen und numerischen Werten überein. TU es nicht).
- [3] Wenn Sie nicht übernehmen können (wenn Eltern häufig doppelte Nummern verwenden), weisen Sie nicht zugewiesene Nummern zu.
def exec_crossover(
self,
other: SendMoreMoneyProblem) -> List[SendMoreMoneyProblem]:
"""
Crossover wird mit Bezug auf eine andere im Argument angegebene Person ausgeführt.
Parameters
----------
other : SendMoreMoneyProblem
Eine andere Person, die beim Überqueren verwendet wird.
Returns
-------
result_chromosomes : list of SendMoreMoneyProblem
"""
child_1: SendMoreMoneyProblem = deepcopy(self)
child_2: SendMoreMoneyProblem = deepcopy(other)
for char in ('S', 'E', 'N', 'D'):
child_2.letters_dict[char] = self.\
_get_not_assigned_num_from_parent(
child=child_2,
parent=self,
)
for char in ('M', 'O', 'R', 'Y'):
child_1.letters_dict[char] = \
self._get_not_assigned_num_from_parent(
child=child_1,
parent=other,
)
result_chromosomes = [child_1, child_2]
return result_chromosomes
def _get_not_assigned_num_from_parent(
self, child: SendMoreMoneyProblem,
parent: SendMoreMoneyProblem) -> int:
"""
Notes
-----
Parameters
----------
child : SendMoreMoneyProblem
Ruft die für das übergeordnete Element festgelegte Nummer ab, die für das untergeordnete Element noch nicht festgelegt wurde. Abhängig von der Kombination der übergeordneten und untergeordneten Werte gibt es Fälle, in denen kein auswählbarer Wert gefunden werden kann. In diesem Fall wird ein nicht zugewiesener Wert von 0 bis 9 festgelegt. Einzelkind.
parent : SendMoreMoneyProblem
Elterliche Person.
Returns
-------
not_assigned_num : int
Berechnete, nicht zugewiesene Nummer.
"""
not_assigned_num: int = -1
for parent_num in parent.letters_dict.values():
child_nums: list = list(child.letters_dict.values())
if parent_num in child_nums:
continue
not_assigned_num = parent_num
if not_assigned_num == -1:
not_assigned_num = self._get_not_assigned_num()
return not_assigned_num
Schließlich sollten für die Ausgabe von Informationen für jede Generation die einzelnen Informationen durch die Methode str zurückgegeben werden.
def __str__(self) -> str:
"""
Gibt die Zeichenfolge der einzelnen Informationen zurück.
Returns
-------
info : str
Zeichenkette einzelner Informationen.
"""
send_val: int = self._get_send_val()
more_val: int = self._get_more_val()
money_val: int = self._get_money_val()
difference: int = abs(money_val - (send_val + more_val))
info: str = (
f"\nS = {self.letters_dict['S']}"
f" E = {self.letters_dict['E']}"
f" N = {self.letters_dict['N']}"
f" D = {self.letters_dict['D']}"
f"\nM = {self.letters_dict['M']}"
f" O = {self.letters_dict['O']}"
f" R = {self.letters_dict['R']}"
f" Y = {self.letters_dict['Y']}"
f'\nSEND = {send_val}'
f' MORE = {more_val}'
f' MONEY = {money_val}'
f' difference : {difference}'
'\n--------------------------------'
)
return info
Wenn es durch die Druckfunktion usw. geleitet wird, wird es im folgenden Format ausgegeben.
2020-10-31 20:51:15.345000 Generationen:5 Beste individuelle Informationen:
S = 4 E = 6 N = 1 D = 9
M = 0 O = 5 R = 3 Y = 2
SEND = 4619 MORE = 536 MONEY = 5162 difference : 7
Versuchen Sie, Probleme in der SendMoreMoneyProblem-Klasse zu verschieben
Lassen Sie uns einen genetischen Algorithmus ausführen, um ein Problem in der SendMoreMoneyProblem-Klasse zu lösen.
if __name__ == '__main__':
send_more_money_initial_population: List[SendMoreMoneyProblem] = \
[SendMoreMoneyProblem.make_random_instance() for _ in range(1000)]
ga = GeneticAlgorithm(
initial_population=send_more_money_initial_population,
threshold=1.0,
max_generations=1000,
mutation_probability=0.7,
crossover_probability=0.2,
selection_type=GeneticAlgorithm.SELECTION_TYPE_ROULETTE_WHEEL)
_ = ga.run_algorithm()
Dieses Mal ist es ein komplizierteres Problem als SimpleEquationProblem, daher haben wir die Anzahl der Personen auf 1000 erhöht (die Berechnungszeit wird entsprechend länger sein).
Der Schwellenwert beträgt 1,0, wenn der Fehler 0 wird, wie im Abschnitt zur Bewertungsfunktion erwähnt. Da es Fälle geben kann, in denen das Problem nicht gelöst werden kann, wurde die maximale Anzahl von Generationen auf 1000 erhöht.
Da der Wert der Bewertungsfunktion diesmal nicht negativ wird, kann die Roulette-Auswahl verwendet werden. Daher ist es eine gute Idee, die Roulette-Auswahl anzugeben.
Als ich es verschob, wurde der Fehler in der 25. Generation wie unten gezeigt 0.
2020-10-31 20:51:33.663973 Anzahl der Generationen:24 Beste individuelle Informationen:
S = 5 E = 7 N = 3 D = 1
M = 0 O = 6 R = 4 Y = 8
SEND = 5731 MORE = 647 MONEY = 6378 difference : 0
--------------------------------
Die Lösung wurde als $ 5731 + 647 = 6378 $ gefunden. Da diese Kombination für eine andere Kombination gilt, kann das Ausführungsergebnis eine andere Kombination sein. Obwohl die Antwort diesmal in einer relativ frühen Generation gesucht wurde, gibt es Fälle, in denen mehr Generationen benötigt werden, da dies von zufälligen Ergebnissen abhängt, und umgekehrt kann die Antwort sofort in der dritten Generation gefunden werden.
Ganzer Code
from __future__ import annotations
from typing import TypeVar, List, Dict
from random import choices, random, randrange, shuffle
from heapq import nlargest
from abc import ABC, abstractmethod
from copy import deepcopy
from datetime import datetime
class Chromosome(ABC):
"""
Eine abstrakte Klasse, die sich mit Chromosomen befasst (ein Element eines genetischen Algorithmus).
"""
@abstractmethod
def get_fitness(self) -> float:
"""
Für die Bewertungsfunktion Y, um die Exzellenz der Chromosomen für das interessierende Problem zu erhalten
Abstrakte Methode.
Returns
-------
fitness : float
Wert der Chromosomenqualität für das interessierende Problem. Je höher das Problem
Es wird ein geeignetes Chromosom.
Es wird auch verwendet, um das Ende eines genetischen Algorithmus zu bestimmen.
"""
...
@classmethod
@abstractmethod
def make_random_instance(cls) -> Chromosome:
"""
Erstellen Sie eine Instanz mit zufälligen Merkmalen (Attributwerte).
Abstrakte Methode.
Returns
-------
instance : Chromosome
Die generierte Instanz.
"""
...
@abstractmethod
def mutate(self) -> None:
"""
Eine abstrakte Verarbeitungsmethode, die (plötzlich) ein Chromosom mutiert.
Es werden zufällig unterschiedliche Werteinstellungen wie Instanzattribute ausgeführt.
"""
...
@abstractmethod
def exec_crossover(self, other: Chromosome) -> List[Chromosome]:
"""
Crossover wird mit Bezug auf eine andere im Argument angegebene Person ausgeführt.
Parameters
----------
other : Chromosome
Eine andere Person, die beim Überqueren verwendet wird.
Returns
-------
result_chromosomes : list of Chromosome
Zwei Individuen (Chromosomen), die nach der Kreuzung erzeugt wurden.
"""
...
def __lt__(self, other: Chromosome) -> bool:
"""
Eine Funktion zum Vergleichen des Wertes der Bewertungsfunktion, die zum Vergleichen zwischen Personen verwendet wird.
Parameters
----------
other : Chromosome
Andere zu vergleichende Personen.
Returns
-------
result_bool : bool
Boolescher Wert, ob die geringere Bedingung erfüllt ist oder nicht.
"""
return self.get_fitness() < other.get_fitness()
C = TypeVar('C', bound=Chromosome)
class GeneticAlgorithm:
SelectionType = int
SELECTION_TYPE_ROULETTE_WHEEL: SelectionType = 1
SELECTION_TYPE_TOURNAMENT: SelectionType = 2
def __init__(
self, initial_population: List[C],
threshold: float,
max_generations: int, mutation_probability: float,
crossover_probability: float,
selection_type: SelectionType) -> None:
"""
Eine Klasse, die sich mit genetischen Algorithmen befasst.
Parameters
----------
initial_population : list of Chromosome
Population der ersten Generation (chromosomale Gruppe).
threshold : float
Ein Schwellenwert zur Bestimmung der Problemlösung. Personen, die diesen Wert überschreiten
Die Berechnung endet, wenn sie auftritt.
max_generations : int
Maximale Anzahl von Generationen, die im Algorithmus ausgeführt werden sollen.
mutation_probability : float
Mutationswahrscheinlichkeit (0.0～1.0）。
crossover_probability : float
Übergangswahrscheinlichkeit (0.0～1.0）。
selection_type : int
Auswahlmethode. Geben Sie einen der folgenden konstanten Werte an.
- SELECTION_TYPE_ROULETTE_WHEEL
- SELECTION_TYPE_TOURNAMENT
"""
self._population: List[Chromosome] = initial_population
self._threshold: float = threshold
self._max_generations: int = max_generations
self._mutation_probability: float = mutation_probability
self._crossover_probability: float = crossover_probability
self._selection_type: int = selection_type
def _exec_roulette_wheel_selection(self) -> List[Chromosome]:
"""
Wählen Sie Roulette und zwei Personen (Chromosomen) aus, die für die Kreuzung usw. verwendet werden sollen.
erhalten.
Returns
-------
selected_chromosomes : list of Chromosome
Eine Liste mit den beiden ausgewählten Personen (Chromosomen). Der Auswahlprozess ist eine Bewertungsfunktion
Es wird zufällig mit dem durch (Fitnessmethode) festgelegten Gewicht extrahiert.
Notes
-----
Es kann nicht für Probleme verwendet werden, bei denen der Ergebniswert der Bewertungsfunktion negativ ist.
"""
weights: List[float] = [
chromosome.get_fitness() for chromosome in self._population]
selected_chromosomes: List[Chromosome] = choices(
self._population, weights=weights, k=2)
return selected_chromosomes
def _exec_tournament_selection(self) -> List[Chromosome]:
"""
Zwei Personen für Turnierauswahl und Kreuzung
Holen Sie sich (Chromosom).
Returns
-------
selected_chromosomes : list of Chromosome
Eine Liste mit den beiden ausgewählten Personen (Chromosomen). Turnier
Die beiden obersten Personen werden aus der Anzahl der Fälle extrahiert, die im Argument für angegeben sind
Einstellen.
"""
participants_num: int = len(self._population) // 2
participants: List[Chromosome] = choices(self._population, k=participants_num)
selected_chromosomes: List[Chromosome] = nlargest(n=2, iterable=participants)
return selected_chromosomes
def _to_next_generation(self) -> None:
"""
Generierte das Individuum der nächsten Generation (Chromosom) und generierte den Attributwert der Population
Ersetzen Sie durch die Bevölkerung der nächsten Generation.
"""
new_population: List[Chromosome] = []
#Der Vergleich der Anzahl der Fälle ist nicht gleich, wenn man bedenkt, dass die Anzahl der Fälle der ursprünglichen Bevölkerung ungerade ist.
#Die Beurteilung erfolgt aufgrund geringerer Bedingungen.
while len(new_population) < len(self._population):
parents: List[Chromosome] = self._get_parents_by_selection_type()
next_generation_chromosomes: List[Chromosome] = \
self._get_next_generation_chromosomes(parents=parents)
new_population.extend(next_generation_chromosomes)
#Aufgrund der Bequemlichkeit, die Liste der nächsten Generation um zwei zu erhöhen, ist die Anzahl der Fälle größer als die ursprüngliche Liste
#Wenn es viele gibt, entfernen Sie sie aus der Liste und stimmen Sie die Anzahl der Elemente in der Liste mit der ursprünglichen Liste ab.
if len(new_population) > len(self._population):
del new_population[0]
self._population = new_population
def _get_next_generation_chromosomes(
self, parents: List[Chromosome]) -> List[Chromosome]:
"""
Behandle als die nächste Generation aus der berechneten Liste von zwei Elternteilen
Holen Sie sich eine Liste von zwei Populationen.
Überqueren oder mutieren mit einer bestimmten Wahrscheinlichkeit, wenn die Wahrscheinlichkeit nicht erfüllt ist, ist der Wert des Arguments
Es wird so wie es ist als nächste Generation eingestellt.
Parameters
----------
parents : list of Chromosome
Liste von zwei Personen des berechneten Elternteils
Returns
-------
next_generation_chromosomes : list of Chromosome
Eine Liste mit zwei Personen, die als nächste Generation festgelegt wurden.
"""
random_val: float = random()
next_generation_chromosomes: List[Chromosome] = parents
if random_val < self._crossover_probability:
next_generation_chromosomes = parents[0].exec_crossover(
other=parents[1])
random_val = random()
if random_val < self._mutation_probability:
for chromosome in next_generation_chromosomes:
chromosome.mutate()
return next_generation_chromosomes
def _get_parents_by_selection_type(self) -> List[Chromosome]:
"""
Erhalten Sie eine Liste von zwei Eltern (Chromosomen) gemäß der Auswahlmethode.
Returns
-------
parents : list of Chromosome
Eine Liste der beiden Individuen (Chromosomen) des erworbenen Elternteils.
Raises
------
ValueError
Wenn eine nicht unterstützte Auswahlmethode angegeben wird.
"""
if self._selection_type == self.SELECTION_TYPE_ROULETTE_WHEEL:
parents: List[Chromosome] = self._exec_roulette_wheel_selection()
elif self._selection_type == self.SELECTION_TYPE_TOURNAMENT:
parents = self._exec_tournament_selection()
else:
raise ValueError(
'Eine nicht unterstützte Auswahlmethode wird angegeben: %s'
% self._selection_type)
return parents
def run_algorithm(self) -> Chromosome:
"""
Eine Instanz eines Individuums (Chromosom), die einen genetischen Algorithmus ausführt und zur Ausführung führt
Bekommen.
Returns
-------
betst_chromosome : Chromosome
Individuelles Ergebnis der Algorithmusausführung. Personen, die den Schwellenwert in der Bewertungsfunktion überschreiten
Oder wenn der Schwellenwert nicht überschritten wird, wurde die angegebene Anzahl von Generationen erreicht.
Die Person mit dem höchsten Bewertungsfunktionswert zu diesem Zeitpunkt wird eingestellt.
"""
best_chromosome: Chromosome = \
deepcopy(self._get_best_chromosome_from_population())
for generation_idx in range(self._max_generations):
print(
datetime.now(),
f'Anzahl der Generationen: {generation_idx}'
f'Beste individuelle Informationen: {best_chromosome}'
)
if best_chromosome.get_fitness() >= self._threshold:
return best_chromosome
self._to_next_generation()
currrent_generation_best_chromosome: Chromosome = \
self._get_best_chromosome_from_population()
current_gen_best_fitness: float = \
currrent_generation_best_chromosome.get_fitness()
if best_chromosome.get_fitness() < current_gen_best_fitness:
best_chromosome = deepcopy(currrent_generation_best_chromosome)
return best_chromosome
def _get_best_chromosome_from_population(self) -> Chromosome:
"""
Wählen Sie aus der Liste der Populationen das Individuum (Chromosom) mit dem höchsten Wert für die Bewertungsfunktion aus.
erhalten.
Returns
-------
best_chromosome : Chromosome
Die Person mit dem höchsten Bewertungsfunktionswert in der Liste.
"""
best_chromosome: Chromosome = self._population[0]
for chromosome in self._population:
if best_chromosome.get_fitness() < chromosome.get_fitness():
best_chromosome = chromosome
return best_chromosome
class SimpleEquationProblem(Chromosome):
def __init__(self, x: int, y: int) -> None:
"""
Die folgende einfache Formel zur Überprüfung der Funktionsweise des genetischen Algorithmus
6x - x^2 + 4 * y - y^2
Eine Klasse, die sich mit dem Problem befasst, die Werte von x und y zu finden, die den Wert von maximieren.
(Die richtige Antwort lautet x= 3, y = 2）
Parameters
----------
x : int
Der Anfangswert von x.
y : int
Der Anfangswert von y.
"""
self.x = x
self.y = y
def get_fitness(self) -> float:
"""
6x mit aktuellen x- und y-Werten- x^2 + 4 * y - y^Vom Berechnungsergebnis von Gleichung 2
Eine Methode, die als Bewertungsfunktion zum Abrufen des Werts verwendet wird.
Returns
-------
fitness : int
Der Wert des Berechnungsergebnisses der Formel.
"""
x: int = self.x
y: int = self.y
return 6 * x - x ** 2 + 4 * y - y ** 2
@classmethod
def make_random_instance(cls) -> SimpleEquationProblem:
"""
Von der SimpleEquationProblem-Klasse mit einem zufälligen Anfangswert
Erstellen Sie eine Instanz.
Returns
-------
problem : SimpleEquationProblem
Die generierte Instanz. x und y sind zufällig im Bereich von 0 bis 99
Der Wert wird eingestellt.
"""
x: int = randrange(100)
y: int = randrange(100)
problem = SimpleEquationProblem(x=x, y=y)
return problem
def mutate(self) -> None:
"""
Mutant (plötzlich) ein Individuum (abhängig von der Zufallszahl, dem Wert von x oder y
1 Zunahme / Abnahme).
"""
value: int = choices([1, -1], k=1)[0]
if random() > 0.5:
self.x += value
return
self.y += value
def exec_crossover(
self, other: SimpleEquationProblem
) -> List[SimpleEquationProblem]:
"""
Crossover wird mit Bezug auf eine andere im Argument angegebene Person ausgeführt.
Parameters
----------
other : SimpleEquationProblem
Eine andere Person, die beim Überqueren verwendet wird.
Returns
-------
result_chromosomes : list of SimpleEquationProblem
Eine Liste mit den beiden Personen, die nach dem Crossover generiert wurden. Eltern werden
Es ist ein Individuum, das von jedem Individuum die Hälfte der Werte von x und y erbt.
"""
child_1: SimpleEquationProblem = deepcopy(self)
child_2: SimpleEquationProblem = deepcopy(other)
child_1.y = other.y
child_2.x = self.x
result_chromosomes: List[SimpleEquationProblem] = [
child_1, child_2,
]
return result_chromosomes
def __str__(self) -> str:
"""
Gibt die Zeichenfolge der einzelnen Informationen zurück.
Returns
-------
info : str
Zeichenkette einzelner Informationen.
"""
x: int = self.x
y: int = self.y
fitness: float = self.get_fitness()
info: str = f'x = {x}, y = {y}, fitness = {fitness}'
return info
LetterDict = Dict[str, int]
class SendMoreMoneyProblem(Chromosome):
LETTERS: List[str] = ['S', 'E', 'N', 'D', 'M', 'O', 'R', 'Y']
def __init__(self, letters_dict: LetterDict) -> None:
"""
SEND + MORE =Das maskierte Berechnungsproblem von MONEY mit einem genetischen Algorithmus
Klasse zu lösen.
Parameters
----------
letters_dict : LetterDict
Jedes der acht im Problem verwendeten Zeichen (Schlüssel) und der zugewiesene numerische Wert (Wert)
Ein Wörterbuch, in dem die Anfangswerte von gespeichert sind.
"""
self.letters_dict: LetterDict = letters_dict
def get_fitness(self) -> float:
"""
SENDEN Sie nach dem numerischen Wert, der jedem aktuellen Zeichen zugewiesen ist+Mit MEHR Nummern
Eine Methode für die Bewertungsfunktion basierend auf der Differenz zwischen den numerischen Werten von GELD.
Notes
-----
Weil der Wert der Bewertungsfunktion des genetischen Algorithmus hoch bewertet wird
Der Wert wird so eingestellt, dass der Wert umso niedriger ist, je größer der Fehler ist.
Wird zurückgegeben.
Returns
-------
fitness : int
SEND +Bewertungswert basierend auf der Differenz zwischen dem MORE-Wert und dem MONEY-Wert.
Je kleiner die Differenz ist, desto größer ist der eingestellte Wert.
"""
send_val: int = self._get_send_val()
more_val: int = self._get_more_val()
money_val: int = self._get_money_val()
difference: int = abs(money_val - (send_val + more_val))
return 1 / (difference + 1)
def _get_send_val(self) -> int:
"""
Ermitteln Sie den Wert von SEND anhand des numerischen Werts jedes aktuell zugewiesenen Zeichens.
Returns
-------
send_val : int
Der Wert von SEND durch den numerischen Wert jedes aktuell zugewiesenen Zeichens.
"""
s: int = self.letters_dict['S']
e: int = self.letters_dict['E']
n: int = self.letters_dict['N']
d: int = self.letters_dict['D']
send_val: int = s * 1000 + e * 100 + n * 10 + d
return send_val
def _get_more_val(self) -> int:
"""
Ermitteln Sie den Wert von MORE anhand des numerischen Werts jedes aktuell zugewiesenen Zeichens.
Parameters
----------
more_val : int
Der Wert von MORE durch den numerischen Wert jedes aktuell zugewiesenen Zeichens
"""
m: int = self.letters_dict['M']
o: int = self.letters_dict['O']
r: int = self.letters_dict['R']
e: int = self.letters_dict['E']
more_val: int = m * 1000 + o * 100 + r * 10 + e
return more_val
def _get_money_val(self):
"""
Ermitteln Sie den Wert von GELD anhand des numerischen Werts jedes aktuell zugewiesenen Zeichens.
Returns
-------
money_val : int
Der Wert von GELD basiert auf dem numerischen Wert jedes aktuell zugewiesenen Zeichens.
"""
m: int = self.letters_dict['M']
o: int = self.letters_dict['O']
n: int = self.letters_dict['N']
e: int = self.letters_dict['E']
y: int = self.letters_dict['Y']
money_val = m * 10000 + o * 1000 + n * 100 + e * 10 + y
return money_val
@classmethod
def make_random_instance(cls) -> SendMoreMoneyProblem:
"""
Von der SendMoreMoneyProblem-Klasse mit einem zufälligen Anfangswert
Erstellen Sie eine Instanz.
Returns
-------
problem : SendMoreMoneyProblem
Die generierte Instanz. Jedes Zeichen hat einen Bereich von 0-9
Die Werte werden so eingestellt, dass sich die Zahlen nicht überschneiden.
"""
num_list: List[int] = list(range(10))
shuffle(num_list)
num_list = num_list[:len(cls.LETTERS)]
letters_dict: LetterDict = {
char: num for (char, num) in zip(cls.LETTERS, num_list)}
problem: SendMoreMoneyProblem = SendMoreMoneyProblem(
letters_dict=letters_dict)
return problem
def mutate(self) -> None:
"""
Stummschalten einer Person (plötzlich) (zufällig ein bestimmter Zeichenwert zugewiesen)
Durch eine nicht vorhandene Nummer ersetzen.
"""
target_char: str = choices(self.LETTERS, k=1)[0]
not_assigned_num: int = self._get_not_assigned_num()
self.letters_dict[target_char] = not_assigned_num
def _get_not_assigned_num(self) -> int:
"""
Ruft die Nummer ab, die nicht jedem Zeichen zugewiesen ist.
Returns
-------
not_assigned_num : int
Eine Nummer, die nicht jedem Zeichen zugewiesen ist. Während es 8 Zeichen gibt,
Da es 10 Nummern von 0 bis 9 gibt, gibt es 2 nicht zugewiesene Nummern,
Einer von ihnen ist eingestellt.
"""
values: list = list(self.letters_dict.values())
not_assigned_num: int = -1
for num in range(10):
if num in values:
continue
not_assigned_num = num
break
return not_assigned_num
def exec_crossover(
self,
other: SendMoreMoneyProblem) -> List[SendMoreMoneyProblem]:
"""
Crossover wird mit Bezug auf eine andere im Argument angegebene Person ausgeführt.
Parameters
----------
other : SendMoreMoneyProblem
Eine andere Person, die beim Überqueren verwendet wird.
Returns
-------
result_chromosomes : list of SendMoreMoneyProblem
Eine Liste mit den beiden Personen, die nach dem Crossover generiert wurden.
"""
child_1: SendMoreMoneyProblem = deepcopy(self)
child_2: SendMoreMoneyProblem = deepcopy(other)
for char in ('S', 'E', 'N', 'D'):
child_2.letters_dict[char] = self.\
_get_not_assigned_num_from_parent(
child=child_2,
parent=self,
)
for char in ('M', 'O', 'R', 'Y'):
child_1.letters_dict[char] = \
self._get_not_assigned_num_from_parent(
child=child_1,
parent=other,
)
result_chromosomes = [child_1, child_2]
return result_chromosomes
def _get_not_assigned_num_from_parent(
self, child: SendMoreMoneyProblem,
parent: SendMoreMoneyProblem) -> int:
"""
Unter den für das Elternteil festgelegten Nummern befinden sich die Nummern, die für das Kind noch nicht festgelegt wurden
erhalten.
Notes
-----
Fälle, in denen auswählbare Werte abhängig von der Kombination der übergeordneten und untergeordneten Werte nicht gefunden werden können
In diesem Fall ist die nicht zugewiesene Zahl unter den Werten von 0 bis 9
Einstellen.
Parameters
----------
child : SendMoreMoneyProblem
Einzelkind.
parent : SendMoreMoneyProblem
Elterliche Person.
Returns
-------
not_assigned_num : int
Berechnete, nicht zugewiesene Nummer.
"""
not_assigned_num: int = -1
for parent_num in parent.letters_dict.values():
child_nums: list = list(child.letters_dict.values())
if parent_num in child_nums:
continue
not_assigned_num = parent_num
if not_assigned_num == -1:
not_assigned_num = self._get_not_assigned_num()
return not_assigned_num
def __str__(self) -> str:
"""
Gibt die Zeichenfolge der einzelnen Informationen zurück.
Returns
-------
info : str
Zeichenkette einzelner Informationen.
"""
send_val: int = self._get_send_val()
more_val: int = self._get_more_val()
money_val: int = self._get_money_val()
difference: int = abs(money_val - (send_val + more_val))
info: str = (
f"\nS = {self.letters_dict['S']}"
f" E = {self.letters_dict['E']}"
f" N = {self.letters_dict['N']}"
f" D = {self.letters_dict['D']}"
f"\nM = {self.letters_dict['M']}"
f" O = {self.letters_dict['O']}"
f" R = {self.letters_dict['R']}"
f" Y = {self.letters_dict['Y']}"
f'\nSEND = {send_val}'
f' MORE = {more_val}'
f' MONEY = {money_val}'
f' difference : {difference}'
'\n--------------------------------'
)
return info
if __name__ == '__main__':
simple_equation_initial_population: List[SimpleEquationProblem] = \
[SimpleEquationProblem.make_random_instance() for _ in range(30)]
ga: GeneticAlgorithm = GeneticAlgorithm(
initial_population=simple_equation_initial_population,
threshold=13,
max_generations=100,
mutation_probability=0.2,
crossover_probability=0.3,
selection_type=GeneticAlgorithm.SELECTION_TYPE_TOURNAMENT)
_ = ga.run_algorithm()
send_more_money_initial_population: List[SendMoreMoneyProblem] = \
[SendMoreMoneyProblem.make_random_instance() for _ in range(1000)]
ga = GeneticAlgorithm(
initial_population=send_more_money_initial_population,
threshold=1.0,
max_generations=1000,
mutation_probability=0.7,
crossover_probability=0.2,
selection_type=GeneticAlgorithm.SELECTION_TYPE_ROULETTE_WHEEL)
_ = ga.run_algorithm()
Referenzseite / Referenzzusammenfassung
- Classic Computer Science Problems in Python
- [Genetischer Algorithmus-Wikipedia](https://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0)
- [John H. Holland-Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%B8%E3%83%A7%E3%83%B3%E3%83%BBH%E3% 83% BB% E3% 83% 9B% E3% 83% A9% E3% 83% B3% E3% 83% 89)
- Darwin Evolutionstheorie. Diejenigen, die überleben, sind nicht "Menschen, die sich ändern können", sondern "Menschen, die Glück haben"
- [Nicht maskierte Berechnung] SENDEN + MEHR = GELD Ich werde ausführlich erklären, wie das Problem gelöst werden kann!
Recommended Posts