Optimisation des colonies de fourmis avec un exemple Java

1. Introduction

Le but de cette série est d' expliquer l'idée d'algorithmes génétiques et de montrer les implémentations les plus connues .

Dans ce tutoriel, nous allons décrire le concept de l'optimisation des colonies de fourmis (ACO), suivi de l'exemple de code.

2. Comment fonctionne ACO

ACO est un algorithme génétique inspiré du comportement naturel d'une fourmi. Pour bien comprendre l'algorithme ACO, nous devons nous familiariser avec ses concepts de base:

  • les fourmis utilisent des phéromones pour trouver le chemin le plus court entre la maison et la source de nourriture
  • les phéromones s'évaporent rapidement
  • les fourmis préfèrent utiliser des chemins plus courts avec des phéromones plus denses

Montrons un exemple simple d'ACO utilisé dans le problème du voyageur de commerce. Dans le cas suivant, nous devons trouver le chemin le plus court entre tous les nœuds du graphique:

En suivant des comportements naturels, les fourmis commenceront à explorer de nouveaux chemins au cours de l'exploration. Une couleur bleue plus forte indique les chemins qui sont utilisés plus souvent que les autres, tandis que la couleur verte indique le chemin le plus court actuellement trouvé:

En conséquence, nous obtiendrons le chemin le plus court entre tous les nœuds:

Le bel outil basé sur l'interface graphique pour les tests ACO peut être trouvé ici.

3. Implémentation Java

3.1. Paramètres ACO

Discutons des principaux paramètres de l'algorithme ACO, déclarés dans la 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;

Le paramètre c indique le nombre d'origine de sentiers, au début de la simulation. De plus, alpha contrôle l'importance des phéromones, tandis que beta contrôle la priorité de distance. En général, le paramètre bêta doit être supérieur à alpha pour obtenir les meilleurs résultats.

Ensuite, la variable d' évaporation indique le pourcentage d'évaporation de la phéromone à chaque itération, tandis que Q fournit des informations sur la quantité totale de phéromone laissée sur la piste par chaque fourmi , et antFactor nous indique combien de fourmis nous utiliserons par ville.

Enfin, nous devons avoir un peu d'aléatoire dans nos simulations, et cela est couvert par randomFactor .

3.2. Créer des fourmis

Chaque fourmi pourra visiter une ville spécifique, se souvenir de toutes les villes visitées et suivre la longueur du sentier:

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. Configurer les fourmis

Au tout début, nous devons initialiser notre implémentation de code ACO en fournissant des matrices de sentiers et de fourmis:

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

Ensuite, nous devons configurer la matrice des fourmis pour commencer avec une ville aléatoire:

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

Pour chaque itération de la boucle, nous effectuerons les opérations suivantes:

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

3.4. Déplacer les fourmis

Commençons par la méthode moveAnts () . Nous devons choisir la prochaine ville pour toutes les fourmis, en nous rappelant que chaque fourmi essaie de suivre les sentiers des autres fourmis:

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

La partie la plus importante est de bien sélectionner la prochaine ville à visiter. Nous devons sélectionner la ville suivante en fonction de la logique de probabilité. Tout d'abord, nous pouvons vérifier si Ant doit visiter une ville au hasard:

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

Si nous n'avons sélectionné aucune ville au hasard, nous devons calculer les probabilités pour sélectionner la ville suivante, en nous rappelant que les fourmis préfèrent suivre des sentiers plus forts et plus courts. Nous pouvons le faire en stockant la probabilité de se déplacer vers chaque ville du tableau:

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

Après avoir calculé les probabilités, nous pouvons décider vers quelle ville aller en utilisant:

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

3.5. Mettre à jour les sentiers

Dans cette étape, nous devons mettre à jour les traces et la phéromone gauche:

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. Mettez à jour la meilleure solution

C'est la dernière étape de chaque itération. Nous devons mettre à jour la meilleure solution afin d'en garder la référence:

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

Après toutes les itérations, le résultat final indiquera le meilleur chemin trouvé par ACO. Veuillez noter qu'en augmentant le nombre de villes, la probabilité de trouver le chemin le plus court diminue.

4. Conclusion

Ce didacticiel présente l'algorithme d'optimisation des colonies de fourmis . Vous pouvez en apprendre davantage sur les algorithmes génétiques sans aucune connaissance préalable de ce domaine, n'ayant que des compétences de base en programmation informatique.

Le code source complet des extraits de code de ce didacticiel est disponible dans le projet GitHub.

Pour tous les articles de la série, y compris d'autres exemples d'algorithmes génétiques, consultez les liens suivants:

  • Comment concevoir un algorithme génétique en Java
  • Le problème du voyageur de commerce à Java
  • Optimisation des colonies de fourmis (ceci)