Bekijk hoe een echte Mierenkolonie-optimalisatie-metaheuristiek live bezorgdrone-routes ontwikkelt, met echte feromoonspoorversterking die convergeert naar kortere multi-stop-routes over opeenvolgende kolonies.
Deze simulatie zet een echt Mierenkolonie-optimalisatie (ACO)-algoritme aan het werk op een multi-stop-bezorgdroneroutingprobleem — een drone moet elk bezorgpunt precies één keer bezoeken en terugkeren naar de basis, het klassieke handelsreizigersprobleem. In plaats van een route te scripten, houdt de pagina een echte feromoonmatrix τ bij over elk paar bezorgpunten. Elke kolonie bouwt elke gesimuleerde mier een volledige tour door herhaaldelijk de volgende onbezochte stop te kiezen met een kans evenredig aan τ(i,j)α · η(i,j)β, waarbij η(i,j) = 1/afstand(i,j) de heuristische aantrekkelijkheid van een korte sprong is. Zodra elke mier in de kolonie zijn tour heeft voltooid, verdampt het feromoon met een factor (1 − ρ) en zet elke mier nieuw feromoon af evenredig aan Q / L op de randen van de route die hij bouwde — zodat kortere routes hun randen veel sterker versterken dan lange.
Laat dit voor genoeg kolonies lopen en de spoorkaart wordt zichtbaar scherper: zwakke, zelden gebruikte randen vervagen tot niets, terwijl een handvol randen — degene die steeds weer voorkomen in de kortste tours — helderder worden, en de best bekende routelengte (bijgehouden op de live grafiek) blijft dalen. Je kunt live het aantal bezorgpunten, het aantal mieren per kolonie en de verdampingssnelheid ρ aanpassen, samen met de exponenten feromoongewicht α en afstandsgewicht β die bepalen hoe sterk mieren koloniekennis vertrouwen ten opzichte van pure afstand. Niets hier is gescript of vooraf ingebakken — elke kolonie leidt echt zijn routes opnieuw af uit de huidige feromoonstatus en willekeurige mierbeslissingen, dus het herstarten met een nieuwe kaart of andere parameters levert elke keer een andere convergentiecurve op.
Wat is Mierenkolonie-optimalisatie en welk probleem lost het hier op?
Mierenkolonie-optimalisatie (ACO) is een metaheuristiek geïnspireerd door hoe echte mieren korte paden vinden tussen hun nest en voedsel met behulp van feromoonsporen. In deze simulatie lost het een multi-stop-bezorgroutingprobleem op: een drone moet elk bezorgpunt precies één keer bezoeken en terugkeren naar de basis, het klassieke handelsreizigersprobleem (TSP). TSP is NP-hard, dus voor meer dan een handvol stops is het onpraktisch om elke mogelijke volgorde te controleren. ACO laat in plaats daarvan veel gesimuleerde mieren kandidaatroutes probabilistisch bouwen, waarbij randen die vaak in korte routes voorkomen worden versterkt, zodat de populatie routes over opeenvolgende kolonies beter wordt zonder ooit optimaliteit te bewijzen.
Hoe bepaalt de ACO-overgangskansregel waar elke mier vervolgens naartoe gaat?
Bij elke stap kiest een mier die bij bezorgpunt i staat de volgende onbezochte stop j met een kans evenredig aan [τ(i,j)]^α × [η(i,j)]^β, waarbij τ(i,j) het feromoonniveau op rand (i,j) is en η(i,j) = 1/afstand(i,j) de heuristische aantrekkelijkheid is — dichterbij gelegen punten ogen aantrekkelijker. α bepaalt hoe sterk de mier opgebouwde koloniekennis (feromoon) volgt, terwijl β bepaalt hoe sterk die pure hebzuchtige afstand volgt. De mier maakt vervolgens een gewogen willekeurige (roulettewiel) trekking onder alle onbezochte kandidaten met behulp van deze gecombineerde scores, zodat hij meestal — maar niet altijd — een veelbelovende rand kiest, wat de kolonie blijft laten verkennen.
Waarom verdampt feromoon, en wat regelt de verdampingssnelheid ρ?
Nadat elke kolonie zijn tours voltooit, worden alle feromoonwaarden vermenigvuldigd met (1 − ρ) voordat nieuwe afzettingen worden toegevoegd. Zonder verdamping zou feromoon zich alleen maar opstapelen, en zouden welke randen vroeg geluk hadden voor altijd domineren — waardoor de zoektocht vastloopt in een middelmatige oplossing. Verdamping laat zwakke of verouderde sporen vervagen zodat de kolonie alternatieve routes kan blijven verkennen. Een hoge ρ vergeet geschiedenis snel en verkent meer maar convergeert langzamer en ruisiger; een lage ρ onthoudt langer en convergeert sneller maar riskeert vast te lopen op een vroege, suboptimale route (voortijdige convergentie).
Na verdamping zet elke mier in de kolonie feromoon af met grootte Q / L op elke rand van de tour die hij bouwde, waarbij L de totale routelengte van die mier is en Q een vaste constante. Omdat de afzetting omgekeerd evenredig is met de lengte, versterkt een mier die een korte route vond zijn randen veel sterker dan een mier die een lange, inefficiënte route vond. Over veel kolonies is dit differentiële versterkingseffect wat een puur willekeurige zoektocht omzet in een die feromoon — en dus toekomstig mierenverkeer — concentreert op de randen die herhaaldelijk voorkomen in korte routes.
Het instellen van α = 0 zorgt ervoor dat mieren feromoon volledig negeren en zich gedragen als een hebzuchtige nearest-neighbour-achtige heuristiek gedreven alleen door η (afstand), zodat er geen koloniekennis ontstaat en er weinig verbetering optreedt in de tijd. Het instellen van β = 0 zorgt ervoor dat mieren afstand volledig negeren en alleen feromoon volgen, wat ervoor kan zorgen dat de hele kolonie zeer snel één vroege, mogelijk slechte, route versterkt (stagnatie). De klassieke balans gebruikt een gematigde α (rond 1) met een sterkere β (rond 2-5) zodat vroege verkenning afstandsbewust is, terwijl feromoon toch goede structuur laat opbouwen over kolonies heen.
De grafiek volgt de tot nu toe gevonden beste routelengte, die per definitie nooit slechter kan worden — het is een lopend minimum. Het stagneert wanneer geen enkele mier in de meest recente kolonies erin is geslaagd de huidige kampioensroute te verslaan, wat te verwachten is: naarmate feromoon zich concentreert op goede randen, convergeren de meeste mieren naar vergelijkbare tours en worden echt nieuwe verbeteringen zeldzamer. Lange stagnaties betekenen meestal dat de kolonie is beland bij een lokaal optimum voor de huidige parameters; het verhogen van de verdampingssnelheid, het aantal mieren, of de verkenningsexponent β kan het soms losschudden om een kortere route te vinden.
Een exacte oplosser (branch-and-bound, dynamisch programmeren, of integer programmeren) kan de werkelijk kortst mogelijke route garanderen, maar zijn looptijd groeit explosief met het aantal stops — dynamisch programmeren heeft al ongeveer n²·2ⁿ bewerkingen nodig, wat onhaalbaar wordt ruim voor n = 30. ACO geeft de optimaliteitsgarantie op in ruil voor schaalbaarheid: het produceert goede, vaak bijna-optimale, routes voor veel grotere instanties in een vaste hoeveelheid rekentijd, precies de afweging die echte bezorg- en logistieksystemen maken bij het routeren van tientallen of honderden stops.