Mieren inspireren nieuw en sneller algoritme voor het bijsturen van dynamische schema’s
Het is 31 augustus en een leraar moet plots om de een of andere reden zijn uren compleet omgooien. Kun je tegen de eerste schooldag nog een sluitend lessenrooster in elkaar puzzelen? Voor dergelijke problemen heeft Koenraad Mertens (Afdeling Informatica van de K.U.Leuven) in het kader van zijn doctoraatsstudie het DynCOAA-algoritme ontwikkeld. Hij baseerde zich daarvoor op het gedrag van mieren.
Dynamic Constraint Optimisation Problems
Dergelijke problemen kunnen zich voordoen als er een schema wordt opgesteld: een lessenrooster, een uurregeling voor het openbaar vervoer, de planning van postroutes in een stad. Een kleine wijziging – iemand die ziek wordt, een halte die wordt toegevoegd – stuurt dat schema in de war. Er is dus een probleem dat snel moet worden opgelost.
Algoritmen
Schema’s worden opgesteld aan de hand van algoritmen. Een algoritme is een opeenvolging van handelingen die van een begin- naar een eindtoestand leiden. Bijvoorbeeld: een bus vertrekt uit een stelplaats, pikt aan de haltes passagiers op en keert terug. Als planner moet je bepalen hoeveel en welke bussen je nodig hebt om alle haltes te bedienen volgens een zekere uurregeling, zodanig dat iedereen vervoerd kan worden en tegelijk het aantal kilometers dat de bussen afleggen zo klein mogelijk blijft. Als een chauffeur ziek wordt of er een tijdelijke halte wordt ingelegd, moet dat heel snel inpasbaar zijn zonder dat het totale systeem erdoor verstoord wordt. Traditionele algoritmen gaan alle mogelijke combinaties één voor één na, op zoek naar een rijtje van ideale oplossingen. Dat vraagt soms heel wat tijd.
Mieren
In het gekrioel van mieren zit een systeem dat gebaseerd is op geursignalen en dat zich snel aanpast aan verstoringen. Stel dat er tien mogelijke paden zijn van het nest naar een voedselbron. Mieren laten geurstoffen achter op die paden en het beste pad zal na verloop van tijd door meer en meer mieren gevolgd worden en dus sterker gaan ruiken. Als er een takje over dat pad valt, zullen de mieren heel snel een goede omweg zoeken en die ook weer gaan markeren. Elk individu draagt zo bij tot een gezamenlijke oplossing waar het grote geheel van de kolonie beter van wordt.
Mierenalgoritmen
Recentelijk zijn computerwetenschappers mieren gaan bestuderen om te zien of die manier van probleemoplossen algoritmen sneller kan maken. Software volgens ‘mierenalgoritmen’ gaat geen ellenlange lijsten van mogelijke oplossingen meer opstellen en die daarna onderling vergelijken, maar stuurt als het ware virtuele mieren uit die hun weg zoeken door de punten van een bepaald schema. Zo onstaat een pad doorheen dat schema, dat uiteindelijk als best mogelijke oplossing naar voren komt. Als het schema verstoord wordt, kunnen de virtuele mieren losgelaten worden om snel een nieuwe oplossing te ontdekken.
DynCOAA
Voor het oplossen van Dynamic Constraint Optimisation Problems waren nog geen mierenalgoritmen ontworpen; het ging vooral om statische toestanden in plaats van dynamische. Koenraad Mertens heeft dat nu wel gedaan, specifiek voor schema’s die bijna voortdurend snel aangepast moeten worden aan kleine wijzigingen, maar waarvan het totaalconcept niet echt verandert, zoals lessenroosters of de lay-out van een fabriekshal. Dat zogenaamde DynCOAA-algoritme blijkt wel degelijk beter en sneller te presteren dan de traditionele algoritmen.
