Mierenkolonieoptimalisatie

Mierenkolonieoptimalisatie is een probabilistische techniek gebruikt voor het bepalen van een kort (maar niet per se het kortste) pad binnen een graaf. De techniek is gebaseerd op het collectief gedrag van mieren in de natuur en maakt onderdeel uit van zwermintelligentie.

In de natuur zoeken mieren naar voedsel door een willekeurig pad te bewandelen. De mier laat een signaalstof (een feromoon) achter tijdens het wandelen en gebruikt het eerder achtergelaten spoor om de weg terug te vinden naar het nest. Andere mieren zullen het spoor volgen en laten op hun beurt ook het feromoon achter zodat de sterkte van het feromonenspoor toeneemt. De signaalstof vervliegt na verloop van tijd, waardoor het spoor vervaagt als de voedselbron is uitgeput omdat minder mieren het spoor volgen. Een ander gevolg van het verdampen van het spoor is dat een langer pad minder vaak zal worden bewandeld dan een korter pad.

Bij mierenkolonieoptimalisatie worden kunstmatige "mieren" gebruikt met hetzelfde idee: hoe meer mieren een bepaald pad bewandelen, hoe meer feromoon achterblijft op het spoor. Hoe sterker het spoor, hoe groter de kans dat een mier het spoor zal volgen. Door het vervagen van het feromonenspoor zal het spoor op een korter pad uiteindelijk sterker worden dan dat van een langer pad. Omdat er toch altijd mieren zijn die afwijken van het sterkste feromonenspoor, zal een nog korter pad door steeds meer mieren worden gevolgd en zullen langere paden minder vaak worden bewandeld, waardoor een steeds kortere route kan worden gevonden.

Geplaatst op:
23-07-2020

Dit artikel is een beginnetje over informatica. U wordt uitgenodigd om op bewerken te klikken om uw kennis aan dit artikel toe te voegen.