sociale insecten, zoals mieren, bijen en wespen, werken op zo’n gecoördineerde wijze samen dat hun kolonies als ‘superorganismen’ worden bestempeld, waaraan een soort ‘collectieve intelligentie’ kan worden toegedicht. een nieuw boek van de vermaarde biologen edward o. wilson en bert hölldobler zet die theorie kracht bij. de robuuste en flexibele manier waarop sociale-insectenkolonies allerlei problemen oplossen inspireert steeds meer belangrijke toepassingen in de computer- en ingenieurswetenschappen.
De collectieve intelligentie van sociale-insectenkolonies
Wie ooit mieren van nabij heeft geobserveerd, zal het niet zijn ontgaan dat elke werkster zonder ook maar de minste supervisie perfect schijnt te weten wat haar te doen staat. Zonder enige moeite ook vinden mieren de kortste weg naar voedselbronnen, bouwen ze ondergrondse nesten met een complexe architectuur en verdelen ze onderling de arbeid optimaal in functie van de noden van de kolonie. Een beter gesmeerde samenleving kan men zich moeilijk indenken. Meer dan honderd jaar geleden beschreef de Amerikaanse entomoloog William Morton Wheeler sociale-insectenkolonies dan ook als ‘superorganismen’ – als diergroepen die een samenhang en integriteit vertonen vergelijkbaar met een individueel organisme. Zo zag hij de rol van de werksters als analoog aan die van ons lichaamsweefsel, de rol van de soldaten als analoog aan ons immuunsysteem en de rol van koninginnen en mannetjes, die op het einde van het seizoen worden geproduceerd, vergeleek hij met onze geslachtscellen.
Ondertussen is het concept van het superorganisme binnen wetenschappelijke kringen opnieuw gemeengoed geworden, getuige hiervan het nieuwe boek van de beroemde biologen Edward O. Wilson en Bert Hölldobler, The Superorganism. The Beauty, Elegance, and Strangeness of Insect Societies. Wilson, de intussen tachtigjarige medegrondlegger van de sociobiologie, begon op zijn achtste met het bestuderen van insecten en is er nooit mee opgehouden. Vooral sociale insecten als mieren, bijen en termieten genoten zijn intense belangstelling. In 1990 publiceerde hij samen met Hölldobler The Ants, waarvoor ze de prestigieuze Pulitzerprijs in de wacht sleepten. Hierin figureerden mierenkolonies voor het eerst expliciet als superorganismen – complexe samenlevingen gebaseerd op subtiele communicatie, altruïstische samenwerking en een doorgedreven arbeidsverdeling. Achttien jaar later werpen ze zich opnieuw op hetzelfde thema – vanuit dezelfde idee, maar onderbouwd met nieuw en beter onderzoek.
Mieren communiceren hoofdzakelijk via het gebruik van feromonen
Het boek legt overtuigend uit hoe mieren hoofdzakelijk via het gebruik van chemische stoffen – feromonen – met elkaar communiceren en hoe ze op die manier feilloos de weg vinden naar de lekkerste hapjes, gezamenlijk complexe nesten bouwen of met miljoenen tegelijk op rooftocht gaan. Zonder marsleider, maar in volmaakte discipline en zonder ooit in de file te hoeven staan. Parasolmieren vormen wellicht het ultieme superorganisme. Deze beestjes leven in gigantische ondergrondse nesten, soms ter grootte van een huis, en ontdekten de landbouw 50 miljoen jaar eerder dan de mens. Ze verbouwen namelijk een symbiotische schimmel op een substraat van gesneden bladeren, die de werksters onophoudelijk af- en aanbrengen. Bovendien houden de werksters deze schimmeltuin parasietvrij door gebruik te maken van specifieke antibiotica, afgescheiden door bacteriën op hun lichaam. Markant genoeg slagen ze hierin zonder daarbij resistente kiemen in de hand te werken. De medische wetenschap heeft nog iets te leren van de sociale insecten.
Dat sociale insecten in weerwil van een zeer beperkte individuele intelligentie toch zeer complexe problemen kunnen oplossen, is eind jaren 1980 ook steeds meer ingenieurs en computerwetenschappers gaan fascineren. Ze merkten op dat de ‘collectieve intelligentie’ van de sociale insecten nooit een globaal masterplan schijnt te vereisen, maar in de plaats daarvan gebaseerd is op puur lokale interacties en het gebruik van een stel eenvoudige regels. Men noemt zo’n gedrag ook wel zelforganiserend. Neem bijvoorbeeld de manier waarop mieren binnen de kortste tijd de snelste weg naar een voedselbron kunnen vinden. Een klassiek experiment van Jean-Louis Deneubourg in de jaren 1980 met de Argentijnse plaagmier toonde aan dat twee eenvoudige regeltjes voldoende zijn om dit te bewerkstelligen: een geurspoor neerleggen bij het zoeken naar voedsel en een voorkeur hebben voor die sporen die het sterkst geuren. De logica is eenvoudig. Stel bijvoorbeeld dat twee mieren op weg zijn naar een voedselbron en daarbij een geurspoor van feromoon neerleggen. In eerste instantie is er geen feromoon op de paden en is de kans dat de mieren het langste pad of het kortste pad kiezen gelijk. De mier die het kortste pad heeft gekozen, zal echter sneller terug zijn bij het nest, waardoor er dubbel zoveel feromoon op dit pad ligt vergeleken met het langste pad. Hierdoor is de kans dat een volgende mier het kortere pad kiest dubbel zo groot, waardoor nog meer mieren dit pad zullen kiezen, zodat uiteindelijk (bijna) alle mieren het kortste pad zullen volgen. Dit systeem is niet alleen efficiënt, maar ook robuust en flexibel. Het is bijvoorbeeld absoluut geen probleem als enkele mieren zouden doodvallen of er zich veranderingen zouden voordoen in de omgeving, bijvoorbeeld als een obstakel op het geurspoor zou terechtkomen of nieuwe voedselbronnen zouden opduiken.
Begin jaren 1990 realiseerde Marco Dorigo zich dat die manier van communiceren ook van nut kon zijn voor het oplossen van combinatorische optimalisatieproblemen, zoals bijvoorbeeld het handelsreizigerprobleem. In dit wiskundige probleem moet je de kortste weg vinden tussen een gegeven aantal steden, terwijl je elke stad maar één keer mag bezoeken en je uiteindelijk terug moet aankomen in de stad vanwaar je vertrokken bent. Het is een klassiek probleem dat bekend staat als NP-moeilijk, een term die erop duidt dat de tijd die nodig is om de optimale oplossing te vinden, exponentieel groeit met de omvang van het probleem, namelijk het aantal steden. De berekening loopt dan ook al gauw stuk op de beschikbare rekenkracht van de computer als je systematisch alle mogelijkheden zou trachten af te lopen.
Dorigo, nu hoogleraar aan de Université Libre de Bruxelles, maar toen nog aan het werk als doctoraatsstudent in Milaan, loste het probleem op dezelfde manier op zoals mieren dit zouden doen. In plaats van alle mogelijke routes te berekenen, liet zijn computerprogramma een team van virtuele mieren los, die vervolgens zelf hun weg moesten zoeken doorheen het probleem. De software imiteerde de eenvoudige gedragsregels van mieren via het gebruik van feromonen: de virtuele mieren lieten denkbeeldige geursporen achter op hun pad, werden uitgerust met een geheugen zodat ze alleen liepen naar plaatsen waar ze nog niet geweest waren en volgden het liefst die routes die het sterkst geurden. Kortere routes werden frequenter bewandeld door meerdere mieren, waardoor het geurspoor op de goede routes differentieel versterkt werd, en de mieren in staat waren het handelsreizigerprobleem in een mum van tijd op te lossen. De tijd die nodig was om tot een oplossing te komen, bleek zelfs veel korter te zijn dan mogelijk was met alle andere toen beschikbare algoritmen. Dorigo stuurde zijn revolutionaire idee naar een gereputeerd vakblad voor ingenieurs, maar zijn artikel bleef daar meer dan vijf jaar liggen. Toen het uiteindelijk werd gepubliceerd, ging de bal echter aan het rollen en onderhand is de bewuste studie meer dan drieduizend keer geciteerd en wordt ze beschouwd als één van de belangrijkste papers van de laatste twintig jaar binnen de computerwetenschappen.
Mierenalgoritmen werden oorspronkelijk uitgedacht als een benaderende oplossing voor het handelsreizigerprobleem
De mierenalgoritmen werden oorspronkelijk uitgedacht als een benaderende oplossing voor het handelsreizigerprobleem, maar dezelfde methodologie – Ant Colony Optimization (ACO) – wordt nu ook met succes toegepast op een hele resem van andere NP-moeilijke optimalisatieproblemen binnen de domeinen van dataverkeer, logistiek en distributie. Voor het handelsreizigerprobleem kan men via klassieke methoden met een zeer krachtige computer binnen een redelijke termijn de optimale oplossing voor maximaal een twintigduizend steden bepalen. Voor andere NP-moeilijke problemen, zoals het Quadratic Assignment Problem, beginnen met klassieke methoden de problemen al bij vijftig items. Bij dat probleem moet je een gegeven aantal items (bijvoorbeeld fabrieken) in een even groot aantal locaties plaatsen. Tussen de fabrieken vindt een uitwisseling plaats, maar de hoeveelheid goederen die uitgewisseld wordt varieert. Waar plaats je dan het best welke fabrieken opdat je de materialen over een zo kort mogelijke afstand moet vervoeren? Nog lastiger is het Vehicle Routing Problem, waarbij je een reeks klanten op de meest efficiënte manier dient te bedienen met een vloot van voertuigen. Elke knoop stelt dan bijvoorbeeld een klant voor die op de bus wacht. Eén knoop is het busdepot, waar een aantal bussen klaar staan om te vertrekken. Het is de bedoeling de routes van de bussen zo uit te stippelen dat de totale afgelegde reisafstand minimaal is, dat elke bus maar zoveel passagiers ophaalt als zijn maximum capaciteit toelaat, dat er zo weinig mogelijk bussen nodig zijn, dat de lengte van de route van elke bus onder een gegeven maximum blijft én dat alle bussen op het einde van hun route terug in het depot aankomen. Een uiterst moeilijk probleem, maar voor ACO een fluitje van een cent.
Ondertussen is ACO ook big business geworden. Het Zwitserse bedrijf AntOptima commercialiseerde een aantal van de mierenalgoritmen om er logistieke problemen mee op te lossen. De mierensoftware wordt intussen gebruikt door een heel aantal bedrijven, waaronder de Italiaanse oliemaatschappij Agip en de Zwitserse distributieketen Migros. In de Verenigde Staten gebruikt Air Liquide ACO om vloeibare gassen, aangekocht bij een honderdtal leveranciers, af te leveren bij zesduizend klanten via pijpleidingen, treinen en vrachtwagens. Een immens complexe taak, die via ACO nu veel efficiënter kan gebeuren en het bedrijf een enorme besparing opleverde. Elke dag loopt het programma vier uur lang op zoek naar de beste oplossing, en elke morgen om zes uur stipt ligt het optimale dienstschema netjes klaar. Ook in Sky Harbor International Airport in Phoenix wordt het luchtverkeer en de vertreklocaties van alle vliegtuigen efficiënt gemanaged door een team van virtuele mieren.
Met de regelmaat van een klok vinden de mierenalgoritmen nieuwe toepassingen. Zo kan men via een uitbreiding van ACO, Ant Colony Routing (ACR), datapakketten in netwerken veel efficiënter doorsturen dan voordien mogelijk was. Die methoden worden in Engeland en Frankrijk nu reeds gebruikt door telecombedrijven om telefoongesprekken sneller door te kunnen schakelen. Samenwerking tussen biologen, ingenieurs en informatici zou ongetwijfeld nog tot verdere optimalisatie van sommige van de algoritmen kunnen leiden. Zo ontdekte Johan Billen dat sommige mieren gebruikmaken van twee spoorferomonen, één dat snel verdampt en één dat traag verdampt, mogelijk als adaptie op een specifiek dynamisch variërend voedselaanbod. Andere onderzoeksgroepen in Engeland hebben dan weer ontdekt dat mieren ook beschikken over afstotende feromonen om ‘no-go’-zones mee te markeren. Zulke nieuwe inzichten bieden uitgebreid voer voor verder onderzoek naar andere en betere ACO-algoritmen voor specifieke toepassingen.
Ook de spectaculaire computergeanimeerde gevechten in de verfilming van The Lord of the Rings berusten op de principes van ‘swarm intelligence’
Naast ACO zijn er nog veel meer algoritmen die geïnspireerd zijn door mieren of andere sociale insecten. Particle Swarm Optimisation (PSO) bijvoorbeeld probeert optimalisatieproblemen op te lossen via communicatie tussen naburige individuen die allen deel uitmaken van een zwerm. Men spreekt hier ook wel van ‘swarm intelligence’ (SI). Ondanks het feit dat het hier om een zeer recente technologie gaat, zijn er reeds honderden toepassingen, gaande van het componeren van muziek en het trainen van neurale netwerken tot het ontcijferen van genregulatienetwerken op basis van DNA-chip (microarray) gegevens. Ook de spectaculaire computergeanimeerde gevechten in de verfilming van The Lord of the Rings berusten op de principes van swarm intelligence. Een van de belangrijkste toepassingen van SI ligt echter in het besturen van een groot aantal modulaire robots die samen gecoördineerd en zonder enige centrale controle een complexe taak moeten uitvoeren, zoals een reddingsoperatie of een missie in de ruimte. Sociale insecten zijn opnieuw uitermate goed in het oplossen van zulke coördinatieproblemen. Denken we maar aan wevermieren die dikwijls levende bruggen vormen om bladeren bij elkaar te plooien bij de constructie van hun nest. Robots even intelligent en harmonieus te laten samenwerken blijkt echter allesbehalve eenvoudig. De NASA is evenwel overtuigd van het potentieel van dit soort technologie en heeft een aantal proefprojecten lopen om te onderzoeken of men robotteams kan laten samenwerken bij de uitvoering van bepaalde taken, zoals het dragen van een metalen balk. De NASA hoopt dat in de toekomst zulke robotteams misschien kunnen worden ingezet voor de exploratie van naburige planeten. Marco Dorigo op zijn beurt heeft een Europees initiatief lopen om een ‘swarmanoid’ te creëren, een groep van robots met complementaire rollen die samenwerken: ‘foot-bots’ om dingen te transporteren op de grond, ‘hand-bots’ die op muren kunnen klimmen en objecten kunnen manipuleren en ‘eye-bots’ die kunnen rondvliegen en informatie over de omgeving inwinnen en doorsturen naar de andere robots. Het systeem is nog niet operationeel, maar eerdere prototypes van teams van ‘swarm bots’ slaagden er wel al in om op spectaculair gecoördineerde wijze allerlei types moeilijk terrein te doorkruisen. Voor robotici was dit een grote doorbraak. Mieren echter doen het al 150 miljoen jaar lang en zonder enige moeite.
Bert Hölldobler en Edward O.Wilson, The Superorganism: The Beauty, Elegance, and Strangeness of Insect Societies. (New York: W.W. Norton & Company, 2008).
Tom Wenseleers is als evolutiebioloog verbonden aan de KU Leuven.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License