Ottimizzazione di Ant Colony con un esempio Java

1. Introduzione

Lo scopo di questa serie è spiegare l'idea degli algoritmi genetici e mostrare le implementazioni più conosciute .

In questo tutorial, descriveremo il concetto di ottimizzazione della colonia di formiche (ACO), seguito dall'esempio di codice.

2. Come funziona ACO

ACO è un algoritmo genetico ispirato al comportamento naturale di una formica. Per comprendere appieno l'algoritmo ACO, dobbiamo familiarizzare con i suoi concetti di base:

  • le formiche usano i feromoni per trovare il percorso più breve tra casa e la fonte di cibo
  • i feromoni evaporano rapidamente
  • le formiche preferiscono utilizzare percorsi più brevi con feromoni più densi

Mostriamo un semplice esempio di ACO utilizzato nel problema del venditore ambulante. Nel caso seguente, dobbiamo trovare il percorso più breve tra tutti i nodi nel grafico:

Seguendo comportamenti naturali, le formiche inizieranno a esplorare nuovi percorsi durante l'esplorazione. Il colore blu più intenso indica i percorsi che vengono utilizzati più spesso degli altri, mentre il colore verde indica il percorso più breve attualmente trovato:

Di conseguenza, otterremo il percorso più breve tra tutti i nodi:

Il simpatico strumento basato su GUI per i test ACO può essere trovato qui.

3. Implementazione Java

3.1. Parametri ACO

Discutiamo i parametri principali per l'algoritmo ACO, dichiarato nella classe AntColonyOptimization :

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;

Il parametro c indica il numero originale di tracce, all'inizio della simulazione. Inoltre, alfa controlla l'importanza dei feromoni, mentre beta controlla la priorità della distanza. In generale, il parametro beta dovrebbe essere maggiore di alpha per ottenere i migliori risultati.

Successivamente, la variabile di evaporazione mostra la percentuale di quanto il feromone sta evaporando in ogni iterazione, mentre Q fornisce informazioni sulla quantità totale di feromone lasciato sulla traccia da ciascuna formica e antFactor ci dice quante formiche useremo per città.

Infine, dobbiamo avere un po 'di casualità nelle nostre simulazioni, e questo è coperto da randomFactor .

3.2. Crea formiche

Ogni formica sarà in grado di visitare una città specifica, ricordare tutte le città visitate e tenere traccia della lunghezza del percorso:

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. Imposta le formiche

All'inizio, dobbiamo inizializzare la nostra implementazione del codice ACO fornendo matrici di trail e formiche:

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)));

Successivamente, dobbiamo impostare la matrice delle formiche per iniziare con una città casuale:

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

Per ogni iterazione del ciclo, eseguiremo le seguenti operazioni:

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

3.4. Spostare le formiche

Cominciamo con il metodo moveAnts () . Dobbiamo scegliere la città successiva per tutte le formiche, ricordando che ogni formica cerca di seguire le tracce delle altre formiche:

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

La parte più importante è selezionare correttamente la prossima città da visitare. Dovremmo selezionare la città successiva in base alla logica delle probabilità. Innanzitutto, possiamo verificare se Ant dovrebbe visitare una città a caso:

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

Se non abbiamo selezionato nessuna città casuale, dobbiamo calcolare le probabilità di selezionare la città successiva, ricordando che le formiche preferiscono seguire sentieri più forti e più brevi. Possiamo farlo memorizzando la probabilità di spostarci in ogni città dell'array:

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; } } } 

Dopo aver calcolato le probabilità, possiamo decidere in quale città andare utilizzando:

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

3.5. Aggiorna tracce

In questo passaggio, dovremmo aggiornare le tracce e il feromone sinistro:

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. Aggiorna la soluzione migliore

Questo è l'ultimo passaggio di ogni iterazione. Dobbiamo aggiornare la soluzione migliore per mantenere il riferimento ad essa:

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(); } } }

Dopo tutte le iterazioni, il risultato finale indicherà il percorso migliore trovato da ACO. Tieni presente che aumentando il numero di città diminuisce la probabilità di trovare il percorso più breve.

4. Conclusione

Questo tutorial introduce l'algoritmo di ottimizzazione della colonia di formiche . È possibile apprendere gli algoritmi genetici senza alcuna conoscenza precedente di quest'area, avendo solo abilità di programmazione informatica di base.

Il codice sorgente completo per gli snippet di codice in questo tutorial è disponibile nel progetto GitHub.

Per tutti gli articoli della serie, inclusi altri esempi di algoritmi genetici, controlla i seguenti link:

  • Come progettare un algoritmo genetico in Java
  • Il problema del venditore ambulante in Java
  • Ottimizzazione della colonia di formiche (questo)