Was sind genetische Algorithmen?

In den letzten Jahren hat sich viel um künstliche Intelligenz (KI) gedreht. Große Unternehmen wie Google, Apple und Microsoft arbeiten aktiv an diesem Thema. In der Tat ist KI ein Oberbegriff, der viele Ziele, Ansätze, Werkzeuge und Anwendungen umfasst. Genetische Algorithmen (GA) sind nur eines der Werkzeuge für die intelligente Suche nach vielen möglichen Lösungen.

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

GA unterhält eine Population von Chromosomen – eine Menge möglicher Lösungen für ein Problem. Die Idee ist, dass die “Evolution” nach einer Reihe von 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, Gen-Kreuzung und Mutation.

Ähnlich wie bei der natürlichen Selektion ist das zentrale Konzept der GA-Auswahl die Fitness. Die Chromosomen, die fitter sind, haben eine bessere Überlebenschance. 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 Preis und Volumen im Handel, besteht jedes Chromosom logischerweise aus zwei Elementen. Wie die Elemente im Chromosom kodiert sind, ist ein anderes Thema.

Bei der Selektion bilden die Chromosomen Elternpaare für die Vermehrung. Jedes Kind übernimmt Merkmale von seinen Eltern. Im Grunde genommen stellt das Kind eine Rekombination von Merkmalen seiner Eltern dar: Ein Teil der Merkmale stammt von einem Elternteil, ein anderer von einem anderen. Zusätzlich zur Rekombination können einige der Merkmale mutieren.

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

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

Praktische Anwendung

Das Beispiel, das wir uns ansehen werden, kann als die “Hello World” der 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 Satz “to be or not to be” aus zufällig erzeugten Listen von Buchstaben “erraten”.

Da es 26 mögliche Buchstaben für jede der 13 Stellen in der Liste gibt, ist die Wahrscheinlichkeit, dass wir den richtigen Satz auf rein zufällige Weise erhalten, (1/26)^13=4.03038×10-19, das sind etwa zwei Chancen aus einem (Gen & Chong, 1997).

Wir werden das Problem hier etwas weiter fassen, was die Lösung noch schwieriger macht. Gehen wir davon aus, dass wir nicht auf die englische Sprache oder eine bestimmte Phrase beschränkt sind. Wir können es mit einem beliebigen Alphabet oder sogar einer beliebigen Menge von Symbolen zu tun haben. Wir haben keine Kenntnisse über die Sprache. Wir wissen nicht einmal, ob es überhaupt eine Sprache gibt.

Angenommen, unser Gegner hat sich eine beliebige Phrase ausgedacht, einschließlich Leerzeichen. Wir kennen die Länge des Satzes und die Anzahl der Symbole im Alphabet. Das ist das einzige Wissen, das wir haben. Nach jeder Vermutung sagt uns unser Gegner, wie viele Buchstaben vorhanden sind.

Jedes Chromosom ist eine Folge von Indizes der Symbole im Alphabet. Wenn es sich um das englische Alphabet handelt, dann wird “a” durch 0, “b” durch 1, “c” durch 2 und so weiter dargestellt. So wird zum Beispiel das Wort “be” als dargestellt.

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

Genetischer Algorithmus-Kern

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. Im Initialisierungsschritt erzeugen wir eine Anfangspopulation von Phrasen. Die Größe der Population wird durch populationSize bestimmt. Wie die Phrase generiert wird, hängt von der Implementierung des supplier ab.

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

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

1. Durchführen einer Auswahl über die Population auf der Grundlage der Chromosomen-Fitness.
2. Erzeugen einer neuen “Generation” durch die Crossover-Operation.
3. Durchführen einer Rekombination einiger Buchstaben in einigen Phrasen.

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

Auswahl

Wie wir bereits wissen, ist die Auswahl ein Prozess, bei dem Nachfolger für die aktuellen Chromosomen gefunden werden – Chromosomen, die besser für unser Problem geeignet sind. Bei der Auswahl müssen wir sicherstellen, 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; for (int i = 0; i < fitnesses.length; i++) { sum += fitnesses / totalFitness; probabilities = sum; } probabilities = 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 Population wird als konsequente Bereiche auf der numerischen Achse dargestellt. Die gesamte Population 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 Bereich erhält. Dann schauen wir uns zufällig eine Zahl zwischen 0 und 1 an und finden einen Bereich, der diese Zahl einschließt. Offensichtlich haben größere Bereiche eine höhere Chance, 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 repräsentiert.

Im Code finden wir die 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 die Wahrscheinlichkeiten durch, die durch die Gesamtfitness skaliert werden. Mathematisch gesehen sollte dies dazu führen, dass die endgültige Variable den Wert 1 hat. Aufgrund der Ungenauigkeit der Fließkommazahlen können wir das nicht garantieren, also setzen wir sie sicherheitshalber auf 1.

Schließlich erzeugen wir eine Zufallszahl für eine Anzahl, die der Anzahl der Eingabechromosomen entspricht, finden einen Bereich, der die Zahl enthält, und wählen dann das entsprechende Chromosom. Wie Sie vielleicht bemerken, kann dasselbe Chromosom mehrmals ausgewählt werden.

Crossover

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; final int index2 = indexes; 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 die Eltern für die Zucht aus. Die ausgewählten Eltern werden gemischt, so dass beliebige Kombinationen möglich sind. Wir nehmen Paare von Eltern und wenden den Operator crossover an. Wir wenden den Operator zweimal für jedes Paar an, da wir die Größe der Population gleich halten müssen. Die Kinder ersetzen ihre Eltern in der Population.

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 einer vordefinierten Wahrscheinlichkeit mutationProbability führen wir eine “Mutation” an den Chromosomen durch. Die Mutation selbst wird durch mutation definiert.

Problemspezifische Algorithmuskonfiguration

Werfen wir nun einen Blick auf die problemspezifischen Parameter, die wir unserer generischen Implementierung zur Verfügung stellen 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 entsprechenden Parameter sind:

1. Crossover-Operator
2. Crossover-Wahrscheinlichkeit
3. Fitness-Funktion
4. Mutations-Operator
5. Mutations-Wahrscheinlichkeit
6. Größe der Population
7. Chromosomen-Lieferant für die Anfangspopulation
8. Terminations-Funktion

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 Wahrscheinlichkeit des Crossovers ist 0.25, so dass wir erwarten, dass im Durchschnitt 25 Prozent der Chromosomen für die Kreuzung ausgewählt werden. Wir führen ein einfaches Verfahren für den Crossover eines Chromosomenpaares durch. Wir erzeugen eine Zufallszahl n aus dem Bereich , wobei length die Länge eines Chromosoms ist. Nun paaren wir das ausgewählte Paar, indem wir die ersten n Zeichen von einem Chromosom und die verbleibenden Zeichen danach vom zweiten Chromosom nehmen.

Fitnessfunktion

private double fitness(char value) { return range(0, value.length) .filter(i -> value == expected) .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 = ALPHABET; } return result;}

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

Lieferant

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 = ALPHABET; } return result;}

Der Lieferant erzeugt 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 Beendigungsfunktion zählt die Anzahl der Aufrufe und gibt true zurück, wenn es entweder eine exakte Übereinstimmung gibt oder wenn die Anzahl der Generierungen 3.000 erreicht.

Ausführung

Jetzt können wir unseren Algorithmus testen. Wenn Sie ihn mehrere Male ausführen, werden Sie feststellen, dass nicht alle Durchläufe erfolgreich sind. Jedes Mal ist die Anzahl der Iterationen anders. Das liegt an der probabilistischen Natur des Algorithmus. Der Algorithmus kann in mehreren Punkten verbessert werden. Sie können mit den Kreuzungs- und Mutationswahrscheinlichkeiten spielen.

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

Eine höhere Anzahl beschleunigt den Algorithmus, macht die Lösung aber auch instabil. Geeignete Chromosomen bleiben nicht nur erhalten, sondern werden auch von den genetischen Operatoren beeinflusst. Daher werden sie ihre “guten” Gene verlieren.

Es ist wichtig, ein gutes Gleichgewicht zu finden. Wenn man die Anzahl der Iterationen erhöht, hat der Algorithmus mehr Möglichkeiten, eine Lösung zu finden, aber andererseits braucht er mehr Zeit. Sie können auch verschiedene Methoden der Kreuzung und Mutation anwenden. Eine gute Auswahl dieser Operatoren wird die Qualität der Lösung drastisch verbessern.

Wir haben hier nur die Spitze des Eisbergs behandelt. 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 Kodierung realer 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 einen GA aufstellen, den wir zur Lösung des Problems verwenden können.

Eines der interessantesten Probleme ist das Lehren künstlicher neuronaler Netze. Als optimierbare Parameter können wir die Synapsenstärken festlegen und als Fitness-Metrik den Prozentsatz der Eingaben, für die unser neuronales Netz die richtige Antwort gegeben hat. Danach können wir uns zurücklehnen und zulassen, dass sich unser neuronales Netz zu der idealen Lösung entwickelt, die wir uns wünschen. Oder zumindest so lange, bis wir etwas erhalten, das gut genug ist, denn die Evolution braucht Zeit.