Ameisenkolonieoptimierung mit einem Java-Beispiel

1. Einleitung

Ziel dieser Reihe ist es , die Idee genetischer Algorithmen zu erklären und die bekanntesten Implementierungen aufzuzeigen .

In diesem Tutorial beschreiben wir das Konzept der Ameisenkolonieoptimierung (ACO), gefolgt vom Codebeispiel.

2. Wie funktioniert ACO?

ACO ist ein genetischer Algorithmus, der vom natürlichen Verhalten einer Ameise inspiriert ist. Um den ACO-Algorithmus vollständig zu verstehen, müssen wir uns mit seinen Grundkonzepten vertraut machen:

  • Ameisen verwenden Pheromone, um den kürzesten Weg zwischen Haus und Nahrungsquelle zu finden
  • Pheromone verdunsten schnell
  • Ameisen bevorzugen kürzere Wege mit dichterem Pheromon

Lassen Sie uns ein einfaches Beispiel für ACO zeigen, das im Travelling Salesman Problem verwendet wird. Im folgenden Fall müssen wir den kürzesten Pfad zwischen allen Knoten im Diagramm finden:

Nach natürlichen Verhaltensweisen werden Ameisen während der Erkundung neue Wege beschreiten. Eine stärkere blaue Farbe zeigt die Pfade an, die häufiger verwendet werden als die anderen, während die grüne Farbe den aktuell kürzesten gefundenen Pfad angibt:

Als Ergebnis erreichen wir den kürzesten Weg zwischen allen Knoten:

Das nette GUI-basierte Tool für ACO-Tests finden Sie hier.

3. Java-Implementierung

3.1. ACO-Parameter

Lassen Sie uns die Hauptparameter für den ACO-Algorithmus diskutieren, der in der AntColonyOptimization- Klasse deklariert ist :

private double c = 1.0; private double alpha = 1; private double beta = 5; private double evaporation = 0.5; private double Q = 500; private double antFactor = 0.8; private double randomFactor = 0.01;

Parameter c gibt die ursprüngliche Anzahl der Spuren zu Beginn der Simulation an. Darüber hinaus steuert Alpha die Pheromonbedeutung, während Beta die Entfernungspriorität steuert. Im Allgemeinen sollte der Beta- Parameter größer als Alpha sein, um die besten Ergebnisse zu erzielen.

Als nächstes zeigt die Verdunstungsvariable den Prozentsatz, wie viel das Pheromon in jeder Iteration verdunstet, während Q Informationen über die Gesamtmenge an Pheromon liefert, die jede Ameise auf dem Weg zurücklässt , und antFactor gibt an , wie viele Ameisen wir pro Stadt verwenden werden.

Schließlich müssen wir in unseren Simulationen ein wenig Zufälligkeit haben, und dies wird von randomFactor abgedeckt .

3.2. Ameisen erstellen

Jede Ameise kann eine bestimmte Stadt besuchen, sich an alle besuchten Städte erinnern und die Länge des Pfades verfolgen:

public void visitCity(int currentIndex, int city) { trail[currentIndex + 1] = city; visited[city] = true; } public boolean visited(int i) { return visited[i]; } public double trailLength(double graph[][]) { double length = graph[trail[trailSize - 1]][trail[0]]; for (int i = 0; i < trailSize - 1; i++) { length += graph[trail[i]][trail[i + 1]]; } return length; } 

3.3. Ameisen einrichten

Zu Beginn müssen wir unsere ACO-Code-Implementierung initialisieren, indem wir Trails und Ameisenmatrizen bereitstellen:

graph = generateRandomMatrix(noOfCities); numberOfCities = graph.length; numberOfAnts = (int) (numberOfCities * antFactor); trails = new double[numberOfCities][numberOfCities]; probabilities = new double[numberOfCities]; ants = new Ant[numberOfAnts]; IntStream.range(0, numberOfAnts).forEach(i -> ants.add(new Ant(numberOfCities)));

Als nächstes müssen wir die Ameisenmatrix einrichten , um mit einer zufälligen Stadt zu beginnen:

public void setupAnts() { IntStream.range(0, numberOfAnts) .forEach(i -> { ants.forEach(ant -> { ant.clear(); ant.visitCity(-1, random.nextInt(numberOfCities)); }); }); currentIndex = 0; }

Für jede Iteration der Schleife führen wir die folgenden Operationen aus:

IntStream.range(0, maxIterations).forEach(i -> { moveAnts(); updateTrails(); updateBest(); });

3.4. Ameisen bewegen

Beginnen wir mit der moveAnts () -Methode. Wir müssen die nächste Stadt für alle Ameisen auswählen und uns daran erinnern, dass jede Ameise versucht, den Spuren anderer Ameisen zu folgen:

public void moveAnts() { IntStream.range(currentIndex, numberOfCities - 1).forEach(i -> { ants.forEach(ant -> { ant.visitCity(currentIndex, selectNextCity(ant)); }); currentIndex++; }); }

Der wichtigste Teil ist die richtige Auswahl der nächsten zu besuchenden Stadt. Wir sollten die nächste Stadt basierend auf der Wahrscheinlichkeitslogik auswählen. Zuerst können wir prüfen, ob Ant eine zufällige Stadt besuchen soll:

int t = random.nextInt(numberOfCities - currentIndex); if (random.nextDouble()  i == t && !ant.visited(i)) .findFirst(); if (cityIndex.isPresent()) { return cityIndex.getAsInt(); } }

Wenn wir keine zufällige Stadt ausgewählt haben, müssen wir die Wahrscheinlichkeiten berechnen, um die nächste Stadt auszuwählen. Dabei müssen wir uns daran erinnern, dass Ameisen es vorziehen, stärkeren und kürzeren Pfaden zu folgen. Wir können dies tun, indem wir die Wahrscheinlichkeit speichern, in jede Stadt im Array zu ziehen:

public void calculateProbabilities(Ant ant) { int i = ant.trail[currentIndex]; double pheromone = 0.0; for (int l = 0; l < numberOfCities; l++) { if (!ant.visited(l)){ pheromone += Math.pow(trails[i][l], alpha) * Math.pow(1.0 / graph[i][l], beta); } } for (int j = 0; j < numberOfCities; j++) { if (ant.visited(j)) { probabilities[j] = 0.0; } else { double numerator = Math.pow(trails[i][j], alpha) * Math.pow(1.0 / graph[i][j], beta); probabilities[j] = numerator / pheromone; } } } 

Nachdem wir die Wahrscheinlichkeiten berechnet haben, können wir entscheiden, in welche Stadt wir gehen möchten, indem wir Folgendes verwenden:

double r = random.nextDouble(); double total = 0; for (int i = 0; i = r) { return i; } }

3.5. Trails aktualisieren

In diesem Schritt sollten wir die Trails und das linke Pheromon aktualisieren:

public void updateTrails() { for (int i = 0; i < numberOfCities; i++) { for (int j = 0; j < numberOfCities; j++) { trails[i][j] *= evaporation; } } for (Ant a : ants) { double contribution = Q / a.trailLength(graph); for (int i = 0; i < numberOfCities - 1; i++) { trails[a.trail[i]][a.trail[i + 1]] += contribution; } trails[a.trail[numberOfCities - 1]][a.trail[0]] += contribution; } }

3.6. Aktualisieren Sie die beste Lösung

Dies ist der letzte Schritt jeder Iteration. Wir müssen die beste Lösung aktualisieren, um den Verweis darauf beizubehalten:

private void updateBest() { if (bestTourOrder == null) { bestTourOrder = ants[0].trail; bestTourLength = ants[0].trailLength(graph); } for (Ant a : ants) { if (a.trailLength(graph) < bestTourLength) { bestTourLength = a.trailLength(graph); bestTourOrder = a.trail.clone(); } } }

Nach allen Iterationen zeigt das Endergebnis den besten von ACO gefundenen Pfad an. Bitte beachten Sie, dass durch Erhöhen der Anzahl der Städte die Wahrscheinlichkeit, den kürzesten Weg zu finden, abnimmt.

4. Fazit

In diesem Tutorial wird der Algorithmus zur Optimierung der Ameisenkolonie vorgestellt . 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.

Alle Artikel der Reihe, einschließlich anderer Beispiele für genetische Algorithmen, finden Sie unter den folgenden Links:

  • So entwerfen Sie einen genetischen Algorithmus in Java
  • Das Problem des Handlungsreisenden in Java
  • Ameisenkolonie-Optimierung (dies)