Genetische Algorithmen: Suche und Optimierung durch natürliche Selektion

Was sind genetische Algorithmen?

In den letzten Jahren hat es einen enormen Wirbel um künstliche Intelligenz (KI) gegeben. Große Unternehmen wie Google, Apple und Microsoft arbeiten aktiv an dem Thema. Tatsächlich ist KI ein Dach, das viele Ziele, Ansätze, Tools und Anwendungen abdeckt. Genetische Algorithmen (GA) sind nur eines der Werkzeuge für die intelligente Suche durch viele mögliche Lösungen.

GA ist eine metaheuristische Such- und Optimierungstechnik, die auf Prinzipien der natürlichen Evolution basiert. Es gehört zu einer größeren Klasse evolutionärer Algorithmen.

GA unterhält eine Chromosomenpopulation – eine Reihe potenzieller Lösungen für das Problem. Die Idee dahinter ist, dass die „Evolution“ nach mehreren aufeinanderfolgenden Generationen eine optimale Lösung für das Problem findet – ähnlich wie bei der natürlichen Selektion.

GA ahmt drei evolutionäre Prozesse nach: Selektion, Genkreuzung und Mutation.

Ähnlich wie bei der natürlichen Selektion ist Fitness das zentrale Konzept der GA-Selektion. Die fitteren Chromosomen haben bessere Überlebenschancen. Fitness ist eine Funktion, die die Qualität der durch das Chromosom repräsentierten Lösung misst. Im Wesentlichen repräsentiert jedes Chromosom innerhalb der Population die Eingabeparameter. Wenn Ihr Problem beispielsweise zwei Eingabeparameter enthält, wie z. B. Preis und Volumen beim Handel, besteht jedes Chromosom logischerweise aus zwei Elementen. Wie die Elemente innerhalb des Chromosoms kodiert werden, ist ein anderes Thema.

Bei der Selektion bilden Chromosomen Elternpaare für die Zucht . Jedes Kind übernimmt Eigenschaften von seinen Eltern. Grundsätzlich stellt das Kind eine Rekombination von Merkmalen seiner Eltern dar: Einige der Merkmale stammen von einem Elternteil, andere von einem anderen. Neben der Rekombination können einige der Merkmale mutieren .

Da fittere Chromosomen mehr Kinder produzieren, wird jede nachfolgende Generation eine bessere Fitness haben. Irgendwann wird eine Generation ein Chromosom enthalten, das eine ausreichend gute Lösung für unser Problem darstellt.

GA ist leistungsfähig und breit anwendbar für komplexe Probleme. Es gibt eine große Klasse von Optimierungsproblemen, die durch herkömmliche Optimierungstechniken ziemlich schwer zu lösen sind. Genetische Algorithmen sind effiziente Algorithmen, deren Lösung näherungsweise optimal ist. Zu den bekannten Anwendungen gehören Planung, Transport, Routing, Gruppentechnologien, Layout-Design, Training neuronaler Netze und viele andere.

Dinge in die Praxis umsetzen

Das Beispiel, das wir uns ansehen werden, kann als „Hello World“ von GA betrachtet werden. Dieses Beispiel wurde ursprünglich von J. Freeman in Simulating Neural Networks with Mathematica gegeben. Ich habe es aus Genetic Algorithms and Engineering Design von Mitsuo Gen und Runwei Cheng übernommen.

Das Word-Matching-Problem versucht, einen Ausdruck mit einem genetischen Algorithmus zu entwickeln. Zunächst soll der Algorithmus den „to be or not to be“-Satz aus zufällig generierten Buchstabenlisten „erraten“.

Da es 26 mögliche Buchstaben für jede der 13 Positionen [ohne Leerzeichen] in der Liste gibt, ist die Wahrscheinlichkeit, dass wir den richtigen Ausdruck auf rein zufällige Weise erhalten, (1/26)^13=4,03038×10-19, was ungefähr ist zwei Chancen aus einer [Trillion] (Gen & Chong, 1997).

Wir werden das Problem hier etwas umfassender definieren, was die Lösung noch schwieriger macht. Nehmen wir an, dass wir nicht auf die englische Sprache oder einen bestimmten Satz beschränkt sind. Wir können am Ende mit jedem Alphabet oder sogar mit jedem Satz von Symbolen zu tun haben. Wir haben keine Sprachkenntnisse. Wir wissen nicht einmal, ob es überhaupt eine Sprache gibt.

Nehmen wir an, unser Gegner hat an eine willkürliche Phrase gedacht, einschließlich Leerzeichen. Wir kennen die Länge der Phrase und die Anzahl der Symbole im Alphabet. Das ist das einzige Wissen, das wir haben. Nach jedem Tipp sagt uns unser Gegner, wie viele Buchstaben vorhanden sind.

Jedes Chromosom ist eine Folge von Indizes der Symbole im Alphabet. Wenn wir über das englische Alphabet sprechen, dann wird 'a' durch 0 dargestellt, 'b' durch 1, 'c' durch 2 und so weiter. So wird beispielsweise das Wort „sein“ als [4, 1] dargestellt.

Wir werden alle Schritte anhand von Java-Codeausschnitten demonstrieren, aber Java-Kenntnisse sind nicht erforderlich, um jeden Schritt zu verstehen.

Kern des genetischen Algorithmus

Wir können mit einer allgemeinen Implementierung des genetischen Algorithmus beginnen:

 public void find() { // Initialization List<T> population = Stream.generate(supplier) .limit(populationSize) .collect(toList()); // Iteration while (!termination.test(population)) { // Selection population = selection(population); // Crossover crossover(population); // Mutation mutation(population); } }

Dies ist der einfache Satz von Schritten, aus denen jeder GA mehr oder weniger besteht. Beim Initialisierungsschritt generieren wir eine Anfangspopulation von Phrasen. Die Größe der Population wird durch populationSize bestimmt. Wie der Ausdruck generiert wird, hängt von der Implementierung des supplier ab.

Innerhalb des Iterationsschritts entwickeln wir die Population weiter, bis die Beendigungsbedingungen innerhalb des Tests der while -Schleife erfüllt sind. Die Beendigungsbedingungen können sowohl die Anzahl der Generationen als auch die exakte Übereinstimmung einer der Phrasen in der Population umfassen. Die termination kapselt eine exakte Implementierung.

Innerhalb jeder Iteration führen wir die typischen GA-Schritte durch:

1. Führen Sie eine Auswahl über die Population basierend auf der Chromosomenfitness durch.
2. Produzieren Sie eine neue „Generation“ über den Crossover-Betrieb.
3. Führen Sie eine Neukombination einiger Buchstaben in einigen Sätzen durch.

Der Kern des Algorithmus ist sehr einfach und domänenunabhängig. Es wird für alle Probleme gleich sein. Was Sie tun müssen, ist die Implementierung genetischer Operatoren. Als nächstes werden wir uns jeden der zuvor erwähnten GA-Operatoren genau ansehen.

Auswahl

Wie wir bereits wissen, ist die Selektion ein Prozess, bei dem Nachfolger für die aktuellen Chromosomen gefunden werden – die Chromosomen, die für unser Problem besser geeignet sind. Bei der Selektion müssen wir darauf achten, dass die Chromosomen mit besserer Fitness eine bessere Überlebenschance haben.

 private List<T> selection(List<T> population) { final double[] fitnesses = population.stream() .mapToDouble(fitness) .toArray(); final double totalFitness = DoubleStream.of(fitnesses).sum(); double sum = 0; final double[] probabilities = new double[fitnesses.length]; for (int i = 0; i < fitnesses.length; i++) { sum += fitnesses[i] / totalFitness; probabilities[i] = sum; } probabilities[probabilities.length - 1] = 1; return range(0, probabilities.length).mapToObj(i -> { int index = binarySearch(probabilities, random()); if (index < 0) { index = -(index + 1); } return population.get(index); }).collect(toList()); }

Die Idee hinter dieser Implementierung ist die folgende: Die Bevölkerung wird als konsequente Bereiche auf der numerischen Achse dargestellt. Die Gesamtpopulation liegt zwischen 0 und 1.

Der Anteil des Bereichs, den ein Chromosom einnimmt, ist proportional zu seiner Fitness. Dies führt dazu, dass ein fitteres Chromosom einen größeren Brocken bekommt. Dann werfen wir einen zufälligen Blick auf eine Zahl zwischen 0 und 1 und finden einen Bereich, der die Zahl enthält. Offensichtlich haben größere Bereiche eine höhere Wahrscheinlichkeit, ausgewählt zu werden, und daher haben fittere Chromosomen eine bessere Überlebenschance.

Da wir keine Details über die Fitnessfunktion kennen, müssen wir die Fitnesswerte normalisieren. Die Fitnessfunktion wird durch fitness dargestellt, die ein Chromosom in ein beliebiges Double umwandelt, das die Fitness des Chromosoms darstellt.

Im Code finden wir Fitnessraten für alle Chromosomen in der Population und wir finden auch die Gesamtfitness. Innerhalb der for -Schleife führen wir eine kumulative Summe über Wahrscheinlichkeiten durch, die um die Gesamtfitness herunterskaliert wurden. Mathematisch sollte dies dazu führen, dass die letzte Variable den Wert 1 hat. Aufgrund der Ungenauigkeit von Gleitkommazahlen können wir dies nicht garantieren, also setzen wir sie sicherheitshalber auf 1.

Schließlich generieren wir für eine Anzahl von Malen, die der Anzahl der eingegebenen Chromosomen entspricht, eine Zufallszahl, finden einen Bereich, der die Zahl enthält, und wählen dann das entsprechende Chromosom aus. Wie Sie vielleicht bemerkt haben, kann dasselbe Chromosom mehrmals ausgewählt werden.

Überkreuzung

Jetzt müssen wir die Chromosomen „züchten“.

 private void crossover(List<T> population) { final int[] indexes = range(0, population.size()) .filter(i-> random() < crossoverProbability) .toArray(); shuffle(Arrays.asList(indexes)); for (int i = 0; i < indexes.length / 2; i++) { final int index1 = indexes[2 * i]; final int index2 = indexes[2 * i + 1]; final T value1 = population.get(index1); final T value2 = population.get(index2); population.set(index1, crossover.apply(value1, value2)); population.set(index2, crossover.apply(value2, value1)); } }

Mit der vordefinierten Wahrscheinlichkeit crossoverProbability wählen wir Eltern für die Zucht aus. Die ausgewählten Eltern werden gemischt, sodass beliebige Kombinationen möglich sind. Wir nehmen Elternpaare und wenden den crossover Operator an. Wir wenden den Operator zweimal für jedes Paar an, weil wir die Größe der Population gleich halten müssen. Die Kinder ersetzen ihre Eltern in der Bevölkerung.

Mutation

Schließlich führen wir eine Rekombination der Merkmale durch.

 private void mutation(List<T> population) { for (int i = 0; i < population.size(); i++) { if (random() < mutationProbability) { population.set(i, mutation.apply(population.get(i))); } } }

Mit der vordefinierten Wahrscheinlichkeit mutationProbability führen wir eine „Mutation“ an den Chromosomen durch. Die Mutation selbst wird durch mutation definiert.

Problemspezifische Algorithmuskonfiguration

Sehen wir uns nun an, welche Art von problemspezifischen Parametern wir für unsere generische Implementierung bereitstellen müssen.

 private BiFunction<T, T, T> crossover; private double crossoverProbability; private ToDoubleFunction<T> fitness; private Function<T, T> mutation; private double mutationProbability; private int populationSize = 100; private Supplier<T> supplier; private Predicate<Collection<T>> termination;

Die Parameter sind jeweils:

1. Crossover-Operator
2. Übergangswahrscheinlichkeit
3. Fitnessfunktion
4. Mutationsoperator
5. Mutationswahrscheinlichkeit
6. Größe der Bevölkerung
7. Chromosomenlieferant für die Anfangspopulation
8. Terminierungsfunktion

Hier ist die Konfiguration für unser Problem:

 new GeneticAlgorithm<char[]>() .setCrossover(this::crossover) .setCrossoverProbability(0.25) .setFitness(this::fitness) .setMutation(this::mutation) .setMutationProbability(0.05) .setPopulationSize(100) .setSupplier(() -> supplier(expected.length)) .setTermination(this::termination) .find()

Crossover-Operator und Wahrscheinlichkeit

 private char[] crossover(char[] value1, char[] value2) { final int i = (int) round(random() * value1.length); final char[] result = new char(value1.length); System.arraycopy(value1, 0, result, 0, i); System.arraycopy(value2, i, result, i, value2.length - i); return result; }

Die Crossover-Wahrscheinlichkeit beträgt 0,25, also erwarten wir, dass im Durchschnitt 25 Prozent der Chromosomen für Crossover ausgewählt werden. Wir führen ein einfaches Verfahren für das Crossover eines Chromosomenpaares durch. Wir erzeugen eine Zufallszahl n aus dem Bereich [0..length] , wobei length die Länge eines Chromosoms ist. Jetzt paaren wir das ausgewählte Paar, indem wir die ersten n Zeichen von einem Chromosom und die restlichen Zeichen danach von dem zweiten nehmen.

Fitnessfunktion

 private double fitness(char[] value) { return range(0, value.length) .filter(i -> value[i] == expected[i]) .count(); }

Die Fitnessfunktion zählt einfach die Anzahl der Übereinstimmungen zwischen der Zielphrase und dem gegebenen Chromosom.

Mutationsoperator und Wahrscheinlichkeit

 private char[] mutation(char[] value) { final char[] result = Arrays.copyOf(value, value.length); for (int i = 0; i < 2; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); int location = (int) round(random() * (value.length - 1)); result[location] = ALPHABET[letter]; } return result; }

Die Mutationsoperation wird unabhängig auf jedem Chromosom durchgeführt. Die Mutationswahrscheinlichkeit beträgt 0,05, also erwarten wir, dass im Durchschnitt fünf Prozent der Bevölkerung mutiert sein werden. Wir mutieren, indem wir eine zufällige Buchstabenposition auswählen und ihren Wert durch einen zufälligen Buchstaben aus dem Alphabet ersetzen. Wir machen es zweimal für jedes mutierte Chromosom.

Anbieter

 private char[] supplier(int length) { final char[] result = new char(length); for (int i = 0; i < length; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); result[i] = ALPHABET[letter]; } return result; }

Der Lieferant generiert zufällige Phrasen, indem er zufällige Buchstaben aus dem Alphabet nimmt. Jede Phrase hat eine konstante vordefinierte Länge.

Beendigungsfunktion

 private boolean termination(Collection<char[]> chars) { count++; final Optional<char[]> result = chars.stream() .filter(value -> round(fitness(value)) == expected.length) .findAny(); if (result.isPresent()) { System.out.println("Count: " + count); System.out.println(result.get()); return true; } final boolean terminated = count == 3000; if (terminated) { chars.forEach(System.out::println); } return terminated; }

Die Terminierungsfunktion zählt die Anzahl der Aufrufe und gibt „ true “ zurück, wenn es entweder eine genaue Übereinstimmung gibt oder wenn die Generierungszählung 3.000 erreicht.

Ausführung

Jetzt sind wir bereit, unseren Algorithmus zu testen. Wenn Sie es mehrmals ausführen, werden Sie feststellen, dass nicht alle Läufe erfolgreich sind. Die Anzahl der Iterationen ist jedes Mal anders. Das liegt an der probabilistischen Natur des Algorithmus. Der Algorithmus hat mehrere Punkte, an denen er verbessert werden kann. Sie können mit Crossover- und Mutationswahrscheinlichkeiten spielen.

Eine Verringerung der Zahl führt zu einer stabilen, aber langsamen Lösung. Eine kleinere Anzahl von Chromosomen wird von genetischen Operatoren beeinflusst und daher sind mehr Iterationen für die Lösung erforderlich.

Das Erhöhen der Zahlen beschleunigt den Algorithmus, macht die Lösung jedoch auch instabil. Gesunde Chromosomen bleiben nicht nur erhalten, sondern werden auch von den genetischen Operatoren beeinflusst. Daher verlieren sie ihre „guten“ Gene.

Es ist wichtig, eine gute Balance zu finden. Eine Erhöhung der Anzahl der Iterationen gibt dem Algorithmus mehr Möglichkeiten, eine Lösung zu finden, nimmt aber andererseits mehr Zeit in Anspruch. Sie können auch verschiedene Crossover- und Mutationsmethoden anwenden. Eine gute Auswahl dieser Operatoren wird die Qualität der Lösung drastisch verbessern.

Was als nächstes?

Wir haben hier nur die Spitze des Eisbergs abgedeckt. Wir haben ein Beispiel genommen, das nur eine Eingabe hat, und die Eingabe kann leicht als Chromosom dargestellt werden. Die genetischen Operatoren sind schlicht und einfach.

Es ist sehr interessant, ein reales Problem zu nehmen und den genetischen Algorithmus darauf anzuwenden. Sie werden verschiedene Ansätze zur Codierung echter Eingabedaten sowie verschiedene Crossover- und Mutationsimplementierungen entdecken.

Wenn ein Problem durch eine Reihe von Parametern ausgedrückt werden kann, die wir erraten müssen, um eine Metrik zu optimieren, können wir schnell ein GA erstellen, mit dem wir es lösen können.

Eines der interessantesten Probleme ist das Unterrichten künstlicher neuronaler Netze. Wir können die optimierbaren Parameter auf Synapsenstärken setzen und die Fitnessmetrik auf den Prozentsatz der Eingaben, für die unser neuronales Netzwerk die richtige Antwort gegeben hat. Danach können wir uns zurücklehnen und unser neuronales Netzwerk zu der idealen Lösung entwickeln lassen, die wir uns wünschen. Oder zumindest bis wir etwas Gutes bekommen, denn Evolution braucht Zeit.