Entwerfen Sie einen genetischen Algorithmus in Java

1. Einleitung

Ziel dieser Reihe ist es , die Idee genetischer Algorithmen zu erklären .

Genetische Algorithmen wurden entwickelt, um Probleme mit denselben Prozessen wie in der Natur zu lösen. Sie verwenden eine Kombination aus Selektion, Rekombination und Mutation, um eine Lösung für ein Problem zu entwickeln.

Beginnen wir mit der Erläuterung des Konzepts dieser Algorithmen am einfachsten Beispiel eines binären genetischen Algorithmus.

2. Wie genetische Algorithmen funktionieren

Genetische Algorithmen sind Teil des evolutionären Rechnens , einem schnell wachsenden Bereich der künstlichen Intelligenz.

Ein Algorithmus beginnt mit einer Reihe von Lösungen (dargestellt durch Individuen ), die als Population bezeichnet werden . Lösungen aus einer Population werden genommen und verwendet, um eine neue Population zu bilden , da die Möglichkeit besteht, dass die neue Population besser ist als die alte.

Personen, die ausgewählt werden, um neue Lösungen zu bilden ( Nachkommen ), werden entsprechend ihrer Fitness ausgewählt - je geeigneter sie sind, desto größer sind die Chancen, dass sie sich reproduzieren.

3. Binärer genetischer Algorithmus

Schauen wir uns den grundlegenden Prozess für einen einfachen genetischen Algorithmus an.

3.1. Initialisierung

Im Initialisierungsschritt generieren wir eine zufällige Population , die als erste Lösung dient . Zunächst müssen wir entscheiden, wie groß die Bevölkerung sein wird und welche endgültige Lösung wir erwarten:

SimpleGeneticAlgorithm.runAlgorithm(50, "1011000100000100010000100000100111001000000100000100000000001111");

Im obigen Beispiel beträgt die Populationsgröße 50, und die richtige Lösung wird durch die binäre Bitfolge dargestellt, die wir jederzeit ändern können.

Im nächsten Schritt werden wir unsere gewünschte Lösung speichern und eine zufällige Population erstellen :

setSolution(solution); Population myPop = new Population(populationSize, true);

Jetzt können wir die Hauptschleife des Programms ausführen.

3.2. Fitness-Check

In der Hauptschleife des Programms werden wir jedes Individuum anhand der Fitnessfunktion bewerten (in einfachen Worten, je besser das Individuum ist, desto höher ist der Wert der Fitnessfunktion, die es erhält):

while (myPop.getFittest().getFitness() < getMaxFitness()) { System.out.println( "Generation: " + generationCount + " Correct genes found: " + myPop.getFittest().getFitness()); myPop = evolvePopulation(myPop); generationCount++; }

Beginnen wir mit der Erklärung, wie wir das geeignetste Individuum bekommen :

public int getFitness(Individual individual) { int fitness = 0; for (int i = 0; i < individual.getDefaultGeneLength() && i < solution.length; i++) { if (individual.getSingleGene(i) == solution[i]) { fitness++; } } return fitness; }

Wie wir beobachten können, vergleichen wir zwei einzelne Objekte Stück für Stück. Wenn wir keine perfekte Lösung finden können, müssen wir mit dem nächsten Schritt fortfahren, der eine Entwicklung der Bevölkerung darstellt .

3.3. Nachwuchs

In diesem Schritt müssen wir eine neue Population erstellen . Zuerst müssen wir wählen zwei Eltern Einzelne von einem Objekte Bevölkerung, entsprechend ihrer Fitness. Bitte beachten Sie, dass es vorteilhaft ist, dem besten Individuum der aktuellen Generation zu erlauben, unverändert auf das nächste zu übertragen. Diese Strategie nennt man Elitismus:

if (elitism) { newPopulation.getIndividuals().add(0, pop.getFittest()); elitismOffset = 1; } else { elitismOffset = 0; }

Um zwei besten auszuwählen Einzelne Objekte werden wir anwenden Turnierauswahlstrategie :

private Individual tournamentSelection(Population pop) { Population tournament = new Population(tournamentSize, false); for (int i = 0; i < tournamentSize; i++) { int randomId = (int) (Math.random() * pop.getIndividuals().size()); tournament.getIndividuals().add(i, pop.getIndividual(randomId)); } Individual fittest = tournament.getFittest(); return fittest; }

Der Gewinner jedes Turniers (derjenige mit der besten Fitness) wird für die nächste Stufe ausgewählt, nämlich Crossover :

private Individual crossover(Individual indiv1, Individual indiv2) { Individual newSol = new Individual(); for (int i = 0; i < newSol.getDefaultGeneLength(); i++) { if (Math.random() <= uniformRate) { newSol.setSingleGene(i, indiv1.getSingleGene(i)); } else { newSol.setSingleGene(i, indiv2.getSingleGene(i)); } } return newSol; }

In der Frequenzweiche tauschen wir Bits von jedem ausgewählten Individuum an einer zufällig ausgewählten Stelle aus. Der gesamte Prozess läuft in der folgenden Schleife ab:

for (int i = elitismOffset; i < pop.getIndividuals().size(); i++) { Individual indiv1 = tournamentSelection(pop); Individual indiv2 = tournamentSelection(pop); Individual newIndiv = crossover(indiv1, indiv2); newPopulation.getIndividuals().add(i, newIndiv); }

Wie wir sehen können, setzen wir nach dem Übergang neue Nachkommen in eine neue Population ein . Dieser Schritt wird als Akzeptanz bezeichnet.

Schließlich können wir eine Mutation durchführen . Mutation wird verwendet, um die genetische Vielfalt von einer Generation einer Population zur nächsten aufrechtzuerhalten . Wir nutzten die Bitinvertierung Art der Mutation, wo Zufallsbits einfach invertiert werden:

private void mutate(Individual indiv) { for (int i = 0; i < indiv.getDefaultGeneLength(); i++) { if (Math.random() <= mutationRate) { byte gene = (byte) Math.round(Math.random()); indiv.setSingleGene(i, gene); } } }

Alle Arten der Mutation und der Frequenzweiche werden in diesem Tutorial ausführlich beschrieben.

Wir wiederholen dann die Schritte aus den Unterabschnitten 3.2 und 3.3, bis wir eine Beendigungsbedingung erreichen, beispielsweise die beste Lösung.

4. Tipps und Tricks

Um einen effizienten genetischen Algorithmus zu implementieren , müssen wir eine Reihe von Parametern optimieren. Dieser Abschnitt sollte Ihnen einige grundlegende Empfehlungen geben, wie Sie mit den wichtigsten Parametern beginnen können:

  • Crossover-Rate - sie sollte hoch sein, etwa 80% -95%
  • Mutationsrate - sie sollte sehr niedrig sein, etwa 0,5% -1% .
  • Bevölkerungsgröße - Eine gute Bevölkerungsgröße liegt bei etwa 20 bis 30 , bei einigen Problemen sind jedoch die Größen 50 bis 100 besser
  • Auswahl - Die grundlegende Auswahl der Roulette-Räder kann mit dem Konzept des Elitismus verwendet werden
  • Crossover- und Mutationstyp - dies hängt von der Codierung und dem Problem ab

Bitte beachten Sie, dass Empfehlungen für die Optimierung häufig Ergebnisse empirischer Studien zu genetischen Algorithmen sind und je nach den vorgeschlagenen Problemen variieren können.

5. Schlussfolgerung

Dieses Tutorial führt in die Grundlagen genetischer Algorithmen ein . Sie können ohne Vorkenntnisse in diesem Bereich etwas über genetische Algorithmen lernen und verfügen nur über grundlegende Computerprogrammierkenntnisse.

Der vollständige Quellcode für die Codefragmente in diesem Lernprogramm ist im GitHub-Projekt verfügbar.

Bitte beachten Sie auch, dass wir Lombok verwenden, um Getter und Setter zu generieren. In diesem Artikel können Sie überprüfen, wie Sie es in Ihrer IDE richtig konfigurieren.

Weitere Beispiele für genetische Algorithmen finden Sie in allen Artikeln unserer Reihe:

  • Wie entwerfe ich einen genetischen Algorithmus? (dieses)
  • Das Problem des Handlungsreisenden in Java