Op mieren kun je rekenen

Sociale insecten zoals mieren presteren samen dingen die ze in hun eentje niet eens kunnen verzinnen. Netwerkbouwers hebben wel oren naar dat kunstje....

OP DE rand van zijn met papieren overladen bureau staan twee pinkgrote miertjes van gebogen ijzerdraad. Gekocht van een straathandelaar in Barcelona, de stad waar Marco Dorigo net een paar maanden - zijn langgewenste sabattical - aan zijn nieuwe boek heeft gewerkt.

De van origine Italiaanse expert in kunstmatige intelligentie (Milaan, 1961), tegenwoordig verbonden aan de Vrije Universiteit van Brussel (ULB), heeft spijt dat hij niet meteen een doosvol heeft meegebracht. Dat zou immers een aardig presentje zijn geweest voor de deelnemers aan Ants2002, de tweejaarlijkse conferentie van ingenieurs die menen dat mieren in sommige opzichten beter kunnen rekenen dan mensen, komende week in Brussel.

Dorigo, een elegante veertiger met een bril en een permanent brede glimlach, geldt als een van de grondleggers van het rekenen met mieren. Tien jaar geleden schreef hij, toen nog als een wat onzekere promovendus aan de Technische Universiteit in Milaan, een nadien beroemd geworden artikel. Ontwerpers van netwerken - van internet tot de distributie van goederen - kunnen veel leren van sociale insecten als de mier, was de boodschap. 'Zij laten zien hoe je zonder centrale regie toch tot doeltreffende collectieve prestaties kunt komen', vat hij de boodschap geroutineerd samen.

In zijn artikel liet Dorigo als eerste zien hoe je de spoorzoekerskwaliteiten van mieren kunt gebruiken om het zogeheten handelsreizigersprobleem op te lossen. Dat vermaarde wiskundige vraagstuk is even simpel te formuleren als onmogelijk tot in de puntjes uit te rekenen: wat is de korste weg voor een handelsreiziger om een reeks steden in een gebied éénmaal te bezoeken?

Recht-toe-recht-aan alle mogelijke routes uitmeten, kost bij meer dan een handjevol steden al snel buitensporig veel tijd. Wel zijn er algoritmes - computerrekenmethodes - ontwikkeld die bij benadering in redelijke tijd een vrijwel optimaal antwoord leveren. Zulke algoritmes kiezen doorgaans een route en proberen vervolgens uit welke verandering de grootste besparing in reislengte oplevert. waarna het proces wordt herhaald tot de verbeteringen minimaal worden.

Dorigo kwam met het idee om de landkaart te overspoelen met denkbeeldige mieren en vervolgens maar te zien welke weg ze het liefst kiezen. Daarbij vertrouwde hij op de truc waarmee echte mieren elkaar laten weten wat de kortste route naar het voer is: het achterlaten van geurstoffen.

Mieren, hoorde de Italiaan begin jaren negentig toevallig toen hij op een conferentie over kunstmatige intelligentie in Duitsland was, laten langzaam verdampende geurstoffen of feromonen achter op het pad waar ze lopen. Verder lopen ze letterlijk hun neus achterna: ze volgen het liefst het sterkst geurende spoor.

Dat is genoeg om de kortste weg naar een bepaald doel te vinden, realiseerde Dorigo zich in een flits. Een lange weg naar een doel(en weer terug), waar per minuut minder mieren passeren, geurt immers minder dan een kortere weg naar hetzelfde doel. En dus lopen binnen de kortste keren alle mieren over dezelfde kortste weg, al hebben ze dat geen van alle bedacht.

Terug in Milaan lieten Dorigo's simulaties zien dat mieren met die oersimpele techniek niet alleen de kortste weg om een obstakel vinden dat plots op hun pad valt, maar ook langs een behoorlijk aantal steden in het handelsreizigersprobleem. Niet perfect, maar dat zou ook wat al te gemakkelijk zijn geweest. Maar beter dan verwacht.

'Met nog wat extra ingrepen zijn de mier-algoritmes intussen net zo goed te maken als de andere benaderingen', zegt Dorigo tevreden. Om hem heen, op de zolder van het wat haveloze ULB-lab voor cement-research in een Brusselse buitenwijk, werken intussen twintig mensen aan zijn ideeën.

Maar tien jaar geleden duurde het even voor de ingenieurwereld begreep waar de jonge Italiaan uit Milaan het eigenlijk over had. Dorigo: 'Ik herinner me dat een in mijn ogen antieke hoogleraar bij me kwam om te benadrukken dat wij ingenieurs zijn en geen biologen.'

Zijn revolutionaire artikel bleef vervolgens maar liggen bij de redactie van het Amerikaanse ingenieurstijdschrift IEEE Transactions on Cybernetics. Pas in 1996, na talloze revisies en eindeloze discussie over details, werd het afgedrukt. Ingediend 15 november 1991, staat er onder, dat wel. En een klassieker in het vakgebied, sinds de publicatie.

'Ik had niks met mieren', zegt Dorigo een week voor de conferentie die hij zal voorzitten. 'En eigenlijk nog steeds niet. Ik lig net als elke pappa wel eens met mijn kinderen op het terras om te kijken wat ze allemaal doen. Maar meer weet ik er ook niet van.'

Mieren, zegt hij, zijn voor een ingenieur in de eerste plaats een inspiratiebron, plus een handige metafoor om ingewikkelde dingen aan de buitenwacht uit te leggen. Voor inzicht in het gedrag van echte mieren kan hij altijd een entomoloog bellen. Sterker, inmiddels is er een solide wisselwerking ontstaan tussen ingenieurs en biologen. Beiden simuleren op de computer wat er gebeurt als een massa ongecompliceerde individuen samenwerkt.

'Alleen de intenties zijn anders. Biologen proberen daarmee uit te vinden wat de basisprincipes zijn waarmee een mierenkolonie functioneert zonder dat alles van boven wordt bestuurd. Wij ingenieurs proberen juist te bedenken wat je allemaal met zo'n systeem zou kunnen doen', zegt Dorigo.

Dat is veel, zo is de laatste vijf jaar wel gebleken. Niet in de laatste plaats omdat netwerken in die tijd een allesbepalende rol kregen. Internet en telecommunicatie werden cruciale economische sectoren. Maar ook in de transportsector is het optimaal verdelen van goederenstromen eveneens cruciaal. Unilever deed studies met mier-algoritmes om de werkvloer van fabrieken in te delen.

De Italiaanse oliemaatschappij AGIP gebruikt een miersysteem bij het opstellen van afleverschema's aan haar klanten.

Het grootste voordeel van decentraal georganiseerde communicatienetwerken zonder centrale regisseur is hun flexibiliteit en robuustheid: raakt er ergens iets verstopt of defect, dan vindt het geheel vanzelf een min of meer efficiënte omweg. De militaire voorlopers van het internet, Darpanet en Arpanet, waren zelfs ontworpen om zo onkwetsbaar te zijn voor plaatselijke aanvallen.

Mier-algoritmes blijken een effectief gereedschap bij het opzetten en beheren van zulke netwerken, zegt bijvoorbeeld de Nederlandse ingenieur ir. Ruud Schoonderwoerd. Midden jaren negentig paste hij als Delftse afstudeerder voor de firma Hewlett Packard in Engeland als eerste de technieken toe op telefoonnetten. De vraag was daar hoe je brokjes van een telefoongesprek (packets) efficiënt over een druk gebruikt netwerk loodst. Een extra gecompliceerd probleem, omdat de situatie voortdurend verandert.

Schoonderwoerd liet speciale softwarepakketjes (mieren) over het net heen en weer dwalen. Bij elk knooppunt dat ze passeerden in het net meldden ze in welke richting het druk was en waar rustiger. 'Pionieren met simpele simulaties, maar het werkte echt beter dan het centraal aansturen van het net', weet hij nog. British Telecom, MCI-Worldcom en ook het Nederlandse KPN deden daarna soortgelijke experimenten.

Schoonderwoerd doet tegenwoordig in managementadvies. Zijn vroegere begeleider dr. Leon Rothkrantz in Delft hanteert als een van de weinige Nederlanders stelselmatig mier-algoritmes, zowel voor telecommunicatie als logistiek. Hij toonde afgelopen donderdag en vrijdag op het Nederlandse ICT-Kenniscongres 2002 in Den Haag nog een programma dat in real-time routeadvies geeft aan automobilisten. Gesimuleerde mieren blijken beter een uitweg uit het verstopte wegennet te vinden dan automobilisten die denken dat ze weten wat ze doen.