Regardez une véritable métaheuristique d'optimisation par colonie de fourmis faire évoluer en direct des itinéraires de drones de livraison, avec un authentique renforcement de pistes de phéromones convergeant vers des trajets multi-arrêts plus courts au fil des colonies successives.
Cette simulation met un véritable algorithme d'optimisation par colonie de fourmis (ACO) au travail sur un problème de routage de drone de livraison à arrêts multiples — un drone doit visiter chaque point de livraison exactement une fois et revenir à la base, le problème classique du voyageur de commerce. Plutôt que de scripter un itinéraire, la page maintient une véritable matrice de phéromone τ sur chaque paire de points de livraison. À chaque colonie, chaque fourmi simulée construit une tournée complète en choisissant à répétition son prochain arrêt non visité avec une probabilité proportionnelle à τ(i,j)α · η(i,j)β, où η(i,j) = 1/distance(i,j) est la désirabilité heuristique d'un court trajet. Une fois que chaque fourmi de la colonie a terminé sa tournée, la phéromone s'évapore d'un facteur (1 − ρ) et chaque fourmi dépose une nouvelle phéromone proportionnelle à Q / L sur les arêtes de l'itinéraire qu'elle a construit — de sorte que les itinéraires plus courts renforcent leurs arêtes bien plus fortement que les longs.
Exécutez cela pendant suffisamment de colonies et la carte des pistes s'affine visiblement : les arêtes faibles et rarement utilisées s'estompent jusqu'à disparaître tandis qu'une poignée d'arêtes — celles qui continuent d'apparaître dans les tournées les plus courtes — deviennent plus brillantes, et la longueur du meilleur itinéraire connu (suivie sur le graphique en direct) continue de baisser. Vous pouvez ajuster en direct le nombre de points de livraison, le nombre de fourmis par colonie, et le taux d'évaporation ρ, ainsi que les exposants de poids de phéromone α et de poids de distance β qui contrôlent la force avec laquelle les fourmis font confiance à l'expérience de la colonie par rapport à la distance brute. Rien ici n'est scripté ou pré-calculé — chaque colonie dérive réellement à nouveau ses itinéraires à partir de l'état actuel de phéromone et de décisions aléatoires des fourmis, de sorte que redémarrer avec une nouvelle carte ou des paramètres différents produit une courbe de convergence différente à chaque fois.
Qu'est-ce que l'optimisation par colonie de fourmis et quel problème résout-elle ici ?
L'optimisation par colonie de fourmis (ACO) est une métaheuristique inspirée de la façon dont les fourmis réelles trouvent des chemins courts entre leur nid et la nourriture grâce à des pistes de phéromones. Dans cette simulation, elle résout un problème de routage de livraison à arrêts multiples : un drone doit visiter chaque point de livraison exactement une fois et revenir à la base, ce qui est le problème classique du voyageur de commerce (TSP). Le TSP est NP-difficile, donc au-delà d'une poignée d'arrêts, il est impossible de vérifier tous les ordres possibles. L'ACO exécute à la place de nombreuses fourmis simulées qui construisent des itinéraires candidats de manière probabiliste, renforçant les arêtes qui tendent à apparaître dans les itinéraires courts, de sorte que la population d'itinéraires s'améliore au fil des colonies successives sans jamais prouver l'optimalité.
Comment la règle de probabilité de transition de l'ACO décide-t-elle où va chaque fourmi ensuite ?
À chaque étape, une fourmi se trouvant au point de livraison i choisit son prochain arrêt non visité j avec une probabilité proportionnelle à [τ(i,j)]^α × [η(i,j)]^β, où τ(i,j) est le niveau de phéromone sur l'arête (i,j) et η(i,j) = 1/distance(i,j) est la désirabilité heuristique — les points plus proches paraissent plus attrayants. α contrôle la force avec laquelle la fourmi suit l'expérience accumulée de la colonie (phéromone), tandis que β contrôle la force avec laquelle elle suit la distance purement gloutonne. La fourmi effectue ensuite un tirage aléatoire pondéré (roulette) parmi tous les candidats non visités en utilisant ces scores combinés, de sorte qu'elle choisit généralement — mais pas toujours — une arête prometteuse, ce qui maintient l'exploration de la colonie.
Pourquoi la phéromone s'évapore-t-elle, et que contrôle le taux d'évaporation ρ ?
Après que chaque colonie a terminé ses tournées, toutes les valeurs de phéromone sont multipliées par (1 − ρ) avant l'ajout de nouveaux dépôts. Sans évaporation, la phéromone ne ferait jamais que s'accumuler, et les arêtes ayant eu de la chance tôt domineraient pour toujours — piégeant la recherche dans une solution médiocre. L'évaporation permet aux pistes faibles ou obsolètes de s'estomper afin que la colonie puisse continuer à explorer d'autres itinéraires. Un ρ élevé oublie rapidement l'historique et explore davantage mais converge plus lentement et de façon plus bruitée ; un ρ faible se souvient plus longtemps et converge plus vite mais risque de se verrouiller sur un itinéraire précoce et sous-optimal (convergence prématurée).
Après évaporation, chaque fourmi de la colonie dépose une phéromone de magnitude Q / L sur chaque arête de la tournée qu'elle a construite, où L est la longueur totale de l'itinéraire de cette fourmi et Q est une constante fixe. Comme le dépôt est inversement proportionnel à la longueur, une fourmi ayant trouvé un itinéraire court renforce ses arêtes beaucoup plus fortement qu'une fourmi ayant trouvé un itinéraire long et inefficace. Au fil de nombreuses colonies, ce renforcement différentiel est ce qui transforme une recherche purement aléatoire en une recherche qui concentre la phéromone — et donc le trafic futur des fourmis — sur les arêtes qui apparaissent de manière répétée dans les itinéraires courts.
Fixer α = 0 fait ignorer complètement la phéromone aux fourmis et les fait se comporter comme une heuristique gloutonne de type plus proche voisin, uniquement guidée par η (distance), de sorte qu'aucune mémoire de colonie ne se forme et qu'il y a peu d'amélioration au fil du temps. Fixer β = 0 fait ignorer complètement la distance aux fourmis et suivre uniquement la phéromone, ce qui peut amener toute la colonie à renforcer très rapidement un itinéraire précoce, potentiellement médiocre (stagnation). L'équilibre classique utilise un α modéré (autour de 1) avec un β plus fort (autour de 2 à 5) afin que l'exploration précoce tienne compte de la distance, tandis que la phéromone permet toujours à une bonne structure de se composer au fil des colonies.
Le graphique suit la longueur du meilleur itinéraire trouvé jusqu'à présent, qui par définition ne peut jamais s'aggraver — c'est un minimum courant. Elle plafonne chaque fois qu'aucune fourmi des colonies les plus récentes n'est parvenue à battre l'itinéraire champion actuel, ce qui est attendu : à mesure que la phéromone se concentre sur les bonnes arêtes, la plupart des fourmis convergent vers des tournées similaires et les améliorations véritablement nouvelles se raréfient. De longs plateaux signifient généralement que la colonie s'est installée près d'un optimum local pour les paramètres actuels ; augmenter le taux d'évaporation, le nombre de fourmis, ou l'exposant d'exploration β peut parfois la libérer pour trouver un itinéraire plus court.
Un solveur exact (branch-and-bound, programmation dynamique, ou programmation en nombres entiers) peut garantir le véritable itinéraire le plus court possible, mais son temps d'exécution croît de manière explosive avec le nombre d'arrêts — la programmation dynamique nécessite déjà environ n²·2ⁿ opérations, ce qui devient infaisable bien avant n = 30. L'ACO abandonne la garantie d'optimalité en échange de la scalabilité : il produit de bons itinéraires, souvent quasi optimaux, pour des instances bien plus grandes en une quantité fixe de calcul, ce qui est exactement le compromis que font les véritables systèmes de livraison et de logistique lors du routage de dizaines ou de centaines d'arrêts.