William Veerbeek
OP ZOEK NAAR EEN NIEUW PARADIGMA
decentralisatie als leidraad voor een andere onderzoeksmethodiek
Businessgoeroes die dwepen met afbeeldingen van vissenscholen, stedebouwkundigen die zich blindstarten op termieten, bureaucraten die meedoen aan een workshop zwermgedrag. Het lijkt erop dat gedecentraliseerde systemen een vaste plaats hebben veroverd in de nieuwe wereld. Netwerksteden, netwerkeconomieën, netwerkmaatschappijen zijn in relatief korte tijd volledig ingeburgerde termen geworden. Het netwerkmodel lijkt het model te zijn geworden voor de beschrijving van talloze processen en fenomenen. De val van het World Trade Center lijkt dan ook een gebeurtenis uit een vroegere, modernistische wereld waarin macht nog verzameld werd op één plek en via een uitgekiende hiërarchische structuur werd gedistribueerd. Het aloude credo “verdeel en heers” lijkt een nieuwe betekenis te hebben aangenomen. Ook in de wetenschappelijke wereld heeft er een ware revolutie plaatsgevonden. Nieuwe onderzoeksgebieden met klinkende namen als Dynamic Systems Theory, Game Theory, Complexity Theory, Catatrophy Theory en Self Organizing Systems, hebben met elkaar gemeen dat ze trachten op een andere manier naar processen te kijken. Niet langer bemoeien bijv. natuurkundigen zich enkel met hun eigen vakgebied, maar slaan zij hun vleugels uit naar sociologie, economie en andere takken van traditionele alfa wetenschapen. Deze kruisbestuiving vindt plaats op allerlei terreinen. Ecologen ontwikkelen economische modellen, sociologen zitten in denktanks voor militaire strategievorming. Wat is er aan de hand? Ligt de traditionele wetenschap op apegapen of zijn er fundamentele problemen aan de orde gekomen waarin zij niet meer kan voorzien? Het antwoord is hierop is niet eenduidig. In verschillende takken van wetenschap liggen sinds lange tijd problemen die met traditionele middelen onvoldoende kunnen worden beschreven, laat staan opgelost. Voor bijv. vloeistofmechanica (turbulentie), is nog steeds geen goed theoretisch model voorhanden. Het weer van overmorgen blijft een mysterie. Paniekgedrag een onmogelijk te beschrijven conditie. Deze processen worden allemaal gekarakteriseerd door een complex macrogedrag en door grote hoeveelheden deeltjes die onderling interacteren. Traditionele methodieken die deze processen beschrijven vanuit een top-down benadering bijten zich stuk op de grote onvoorspelbaarheid van het vertoonde gedrag. Redding kwam uit onverwachte hoek: de biologie. Deze tak van wetenschap werkte sinds de jaren 70 m.b.v. van computermodellen aan het beschrijven van complexe dynamische systemen. Toen andere takken wetenschap deze modellen incorporeerden, ontstond er een volledig nieuw inzicht dat wellicht een antwoord kon geven op fundamentele problemen van complexiteit en onvoorspelbaarheid die typerend was voor deze problematieken. Momenteel worden m.b.v. biologische termen, perspectieven en modellen bijzonder veel zaken in een nieuw daglicht geplaatst. Predator-Prey modellen worden gebruikt in de economie, kritische faseovergangen in de catastrophetheorie1, zelforganisatie en emergent gedrag dienen als nieuwe basis voor turbulentiemodellen. Nu het Newtoniaanse Wereldbeeld na de kwantumfysica naar het rijk der fabelen is gedirigeerd, lijkt de wereld klaar voor een nieuw paradigma: dat van de biologie. Dit essay tracht aan de hand van een klein aantal voorbeelden karakteristieke kenmerken van de modellen die momenteel succesvol worden gebruikt bij onderzoek en toepassing in complexe processen. Zaken als zelforganisatie, gedecentraliseerde modellen en celautomaten worden onderzocht op hun achtergrond, hun karakteristieken en hun toepassingen.
1 De zin van decentralisatie in de krijgsvoering. Een korte verkenning Throughout human history there have been two distinct ways of waging war, and two primary methods for organizing armed forces. On the one hand is the war machine assembled by the nomads of the Steppes, such as the armies of Genghis Khan which invaded Europe in the thirtheenth century; on the other hand is the war-making machinery invented by sedentary peoples, like the Assyrian, Greek and Roman armies from which modern armies have evolved. Manuel de Landa5
De rationalisatie van de strijdkrachten in doordachte gestructureerde eenheden, werd reeds succesvol ingezet ten tijden van de Grieken. Toepassing van de phalanx, een rigide vierkant van speerdragers, als aanvalseenheid vormde de basis voor de verdedigingslinie van de griekse strijdkrachten. In tegenstelling tot de flexibiliteit en mobiliteit van het nomadische leger beschikte de phalanx over grote slagkracht die echter werd gecombineerd met een slechts geringe capaciteit om te manoeuvreren. M.a.w. de phalanx beschikte slechts in geringe mate de mogelijkheid om zich aan te passen aan het strijdtoneel. De rigiditeit van het leger zou vreemd genoeg in de eeuwen die daar op volgden enkel maar toenemen en cullumeerde in de op mechanistische wijze opererende enorme legers van de 18de eeuw. Debet hieraan was de hiërarchische organisatie van het oorlogsapparaat. Zonder moderne communicatiemiddelen was het eenvoudigweg onmogelijk om kleine eenheden aan te sturen. Fysieke cohesie van het oorlogsapparaat was een kritieke succesfactor voor het voeren van een commandostructuur. Het duurde dan ook tot de 2de wereldoorlog voordat de operationele eenheden van legers fundamenteel veranderden. Directe aanleiding hiervoor was de uitvinding van de veldtelefoon die de Nazi’s in staat stelde met hun Blitzkriek in korte tijd grote delen van Europa te veroveren. D.m.v. kleine legereenheden en snelle informatieuitwisseling beschikten de Nazi’s over ongekend flexibele en bovenal mobiele strijdkrachten. De invloed van technologische ontwikkelingen op decentralisatie vonden echter al plaats in de 19de eeuw, toen de vergrote accuratesse van de gebruikte vuurwapens traditionele opgezette (massale) legerlinies langzaam maar zeker overbodig maakte. Maar wat was nu de feitelijke rede die decentralisatie wenselijk maakte? Als we trachten een model te maken van een militaire eenheid kunnen we wellicht gebruik maken van elementen uit de grafentheorie. Essentieel voor het slagen van een eenheid (of het nu over een volledig leger gaat of over een kleine commandoeenheid) is het feit of de bevelen iedere soldaat bereiken. Als we soldaten voorstellen als punten in een graaf, dan zal er een Euler-pad moeten bestaan in deze graaf. Daar communicatie tijd kost alsmede vergezeld gaat van ruis, is het dus zaak de lengte van de paden die centrum en punten verbinden zo kort mogelijk te houden. Wanneer het daarbij moeilijk is om eenheden van de strijdkrachten te bereiken zal er dus een gewicht hangen aan de paden; het ligt dan ook voor de hand om gebruik te maken van een gerichte gewogen graaf. In een traditionele hiërarchie waarbij de verantwoordelijkheid voor de acties van het leger tot in het kleinste detail bij het centrale commando liggen zullen er grote afstanden moeten worden afgelegd in de graaf om verst liggende punten te breiken. Bovendien kunnen bevelen door ruis dermate vervormd raken dat de militair zich niet gedraagt conform het initiële bevel. Door gebruik te maken van een graaf is het eenvoudig af te leiden waarom de phalanx een succesvol militair orgaan was: de paden tot de punten waren relatief kort zodat de communicatie relatief eenvoudig was. M.a.w. de phalanx was beheersbaar. De hiërarchische commandostructuur heeft echter één belangrijke archilleshiel die haar zeer kwetsbaar maakt: wanneer het commando wordt uitgeschakeld valt het leger uiteen in een ongerichte en daardoor volledig hulpeloze reeks individuele kleine eenheden. In het grafenmodel zou dit betekenen dat wanneer het centrum van de graaf wordt verwijderd, deze uiteenvalt in een groot aantal componenten. Hieruit volgt een volgende grootheid die essentieel is voor het functioneren van het militaire lichaam: robuustheid. Terwijl een relatief compacte samenstelling (korte paden) een voorwaarde was voor een efficiënte commandostructuur, bestaat er een hieraangerelateerde factor: informatie. Tijdens de gevechtshandelingen (zowel offensief als defensief) ontstaan er continu nieuwe situaties waarop in de strategie niet van te voren op geanticipeerd kan worden. Net als in een schaakspel is de branching factor, en daarmee de zoekboom van mogelijke conflictconstellaties astronomisch groot. De frontlinie zal zich telkens moeten aanpassen aan zowel de omgeving als de handelingen van de tegenstander. Dit betekent dat er een continue stroom informatie vanuit de frontlinies naar het commandocentrum loopt, waar naar gelang interpretatie en strategie de bevelen via dezelfde structuur weer worden gedistribueerd naar diezelfde frontlinies. Geregeld kan het voorkomen dat de nieuwe informatie conflicteert met de uitgaande bevelen, daar beide informatiestromen immers tijd nodig hebben om de het centrale commando te bereiken. Om deze factoren te implementeren in het grafenmodel 1. De notie van een kritieke fase stamt echter uit de natuurkunde. Deze werden rond 1890 geformuleerd door Gibbs, Andrews, van der Laar en Van der Waals. (Johanna M. H. Levelt sengers, Fluid Criticality from Van der Waals to the Present, history of Physics Summer 1998 Newsletter, http://www.aps.org/units/fhp/FHPnews/news898.html) 2. Manuel de Landa, War in the age of intelligent machines (New York: Zone Books, 1991, p. 11)
G = (V,E,C) een graaf waarbij:
afbeelding 1.1
V is de bron, Y is put Y is bron, V is put iab is de informatiestroom van de bron y naar de put v iba is de informatiestroom van de bron v naar de put y iX(in), iX(in) is de informatiestroom die in punt X binnenkomt Cxy, Cxy is de capaciteit van de lijn tussen punt x en y CX is de capaciteit van punt X
iv(in),(cv) iv(in),(cv)
v
iw(in),(cw)
w iw(in),(cw)
iwu ,(c
,(c
vu )
wu )
iu(in),(cu)
iu(in),(cu)
wx) iwx,(c
iyx,( cyx) iyx,( cyx)
ix(in),(cx)
iN
u,
(c
Nu
)
iy(in),(cy)
u
Nu
x
xw)
,( ivw
) cvx
(c u, iN
ixw,(c ix(in),(cx)
ivu
)
cwv
,( iwv
)
N
y
instantiatie van G V is centraal commando Y is eenheid frontlinie iab is frontinformatie iba is bevel iX(in), iX(in) is de binnenkomende informatiestroom in eenheid X Cxy, Cxy is zijn de kosten (afstand, moeilijkheidsgraad) CX is de opnamecapaciteit
iy(in),(cy)
informatiestroom(V) = ∑ iv(in) ∑ iv(in) < CV Ieder punt beschikt slechts over een beperkte capaciteit om informatie te verwerken. Wanneer de branching factor voor met punt v (centraal commando) erg hoog is, zal door de beperkte capaciteit van het punt, de informatiestroom onverzadigd zijn.
zullen zowel lijnen als punten moeten worden voorzien van zowel een capaciteit als een stroomsterkte. Centrum (commandocentrum) en eindpunten (gevechtseenheden) hebben een dubbelfunctie: beiden zijn zowel bron als put. Terwijl de stroom de informatie die door het netwerk loopt symboliseert, geeft de capaciteit van de lijnen en punten de tijdsduur aan die deze stroom nodig heeft om het netwerk te doorlopen. Flexibiliteit en aanpassingsvermogen van het militaire apparaat zijn direct af te leiden uit een aantal eigenschappen in het grafenmodel: 1. Robuustheid: bij het weghalen van punten dient de graaf in zo min mogelijk componenten uiteen te vallen 2. Compactheid: de capaciteit van de lijnen de hoeveelheid lijnen (snede) dient zo groot mogelijk te zijn 3. Korte paden: de padlengte van het centrum tot de verst liggende punten van het centrum dient zo kort mogelijk te zijn Concluderend valt dus te stellen dat de traditionele configuratie van het militaire apparaat op alle punten slechte resultaten behaald. De robuustheid en compactheid van het netwerk is minimaal, terwijl daarmee de lengte van het pad (zeker bij massale veldslagen die een grote geografisch oppervlakte beslaan), relatief groot is. Een organisatievorm die aan deze voorwaarden wel voldoet wordt gevormd door de strijdkrachten die zijn betrokken bij een typische guerrillaoorlog. Naast de uiteraard tactische voordelen die dergelijke groeperingen bezitten (bijv. onzichtbaarheid), wordt aan alle voorwaarden voldaan die vanuit het grafenmodel zijn gedefinieerd. Allereerst zijn de gevechtseenheden uiterst compact waardoor de eisen aan compactheid en korte paden worden gehonoreerd. Dit betekent dat de informatiestromen die door het netwerk lopen optimaal zijn waardoor de verschillende punten in het netwerk relatief snel kunnen reageren op veranderende condities en orders. Dit heeft grote consequenties voor de flexibiliteit en handelingssnelheid van de gevechtseenheden, die in de praktijk bevestigd worden. Een goed voorbeeld hiervan is het Noord-Vietnamese leger (Vietcong) tijdens de Vietnamoorlog die o.a. door snelle hergroepering een succesvolle oorlogstaktiek ten de Verenigde Staten praktiseerde). Gerelateerd aan de flexibiliteit van de gevechtseenheden is de belangrijkste succesfactor, namelijk de robuustheid van de gekozen configuratie. Eenheden die vechten in guerillaverband beschikken over een hoge mate van autonomie; dit betekent dat zij tot een vrij hoog niveau in staat zijn om te reageren op specifieke condities zonder hiervoor eerst het centrale (lees: hoogste) commando te hoeven raadplegen. In het grafenmodel betekent dit dat het totale guerilla-apparaat bestaat uit verschillende componenten, die allen over een eigen centrum beschikken. Wanneer een component wordt uitgeschakeld betekent dit niet dat de andere componenten hun functie verliezen. M.a.w. de uitschakeling van een gevechtseenheid heeft nauwelijks kwalitatieve gevolgen voor het functioneren van de overige componenten, terwijl dit bij traditioneel opgezette strijdkrachten een onevenredig grote neerslag heeft op het functioneren ervan. Resultaat van deze relatieve decentralisatie is dat de kwetsbaarheid van een guerillagroepering relatief gering is. Tevens is het voor de tegenstander bijna onmogelijk om een tactisch doel uit te kiezen om de groepering grote schade toe te brengen. De organisatiestructuur blijft altijd overeind; de gekozen structuur is uitermate robuust. Bij dit model vallen echter een aantal kanttekening te maken immers, zelfs de meest gedecentraliseerde guerillagroepering kent enige vorm van centraal bestuur. Het verschil ligt echter in de mate waarin de diverse groeperingen afhankelijk zijn van dit bestuur. In een guerillaoorlog is het centraal bestuur slechts gericht op het formuleren van een algemene strategie. De exacte tactische invulling wordt verder verzorgt door de specifieke cellen die onder het centrale bestuur staan. Hierdoor hoeft het contact tussen centraal bestuur en cellen slechts sporadisch van karakter plaats te vinden. Als we dit willen weergeven in het grafenmodel betekent dit dat de verschillende componenten kortstonding een verbonden met het centrale commandocentrum. Doordat centrum hier een directe lijn ontstaat tussen de diverse centra is het effect van ruis (zoals in de hiërarchische configuratie) relatief klein. Na het kortstondige contact (informatieuitwisseling) valt de organisatie wederom uiteen in zelfopererende cellen. Bij acties tegen terroristische bewegingen die op eenzelfde organisatievorm zijn gestoeld, gebeurt het regelmatig dat aanslagen op de beweging worden uitgevoerd tijdens overlegsituaties. De strijd van Israël tegen de Hamasbeweging is hier een typisch voorbeeld van. M.a.w. wanneer deze groeperingen een tijdelijke hiërarchische organisatie aangaan zijn ze kwetsbaar voor ontmanteling. De voorlopige conclusie is dat decentralisatie in belangrijke mate verantwoordelijkheid is voor de robuustheid, de flexibiliteit en de handelingssnelheid van een militaire organisatie. Het grafenmodel bevestigt deze bevindingen. Desondanks zijn deze bevinding nauwelijks vernieuwend te noemen. Reeds tijdens de tweede wereldoorlog werd een eerste begin gemaakt met de decentralisatie van de legerstructuur (hoewel er nog steeds klassieke massale veldslagen werden geleverd zoals bijv. Stalingrad). Onder invloed van moderne communicatiemiddelen en uiteraard de toename in slagkracht van de individuele soldaat (al dan niet gegroepeerd in tank, pantservoertuig, vliegtuig, etc.) is de decentrale organisatie van het leger volledig. Het moderne slagveld wordt gedomineerd door kleine eenheden die vooral tactische (en dus van te voren wel gedefinieerde) missies uitvoeren. Het Franse leger heeft haar divisies volledig opgesplitst in kleinere eenheden, terwijl een dergelijke reorganisatie ook in het grootste leger ter wereld, dat van de Verenigde Staten, wordt uitgevoerd. Moderne taskforces krijgen dus steeds meer van de eigenschappen van hun vaak lichtbewapende maar effectief strijdende voormalige tegenstanders, waardoor hun effectiviteit wordt vergroot en hun kwetsbaarheid wordt verkleind.
Doublas A. Macgregor, Breaking the Phalanx (Praeger Publishers, 1997)
afbeelding 1.2 c1
V0
afbeelding 1.3 c1
V0
c2
c3
c4
Wanneer in een samenhangende graaf een punt wordt weggehaald valt de graaf uiteen in meerdere componenten. In een hierarchische commandostructuur waarbij het centrale commando wordt vertegenwoordigd door punt V0, betekent dit dat de componenten 2,3 en 4 niet meer aangestuurd kunnen worden.
afbeelding 1.4 c1 V0 1
1 1
1
1 1
1
1
1
1
1
1 1
1
1
1
1
1
1 1
1
1
1
1 1
1
1
1 1
1
c1
afbeelding 1.5
c2
c3 1 1
V1 1
c4 1
1 1
1
V2 1
c5 1
1 1
1
V3 1
c6 1
1 1
1
V4 1
1
1 1
1
V5 1
1 1
In een gedecentraliseerde commandostructuur is er sprake van 2 verschillende configuraties. Afbeelding 1.4 toont de de volledige groepering tijdens een strategische bespreking (v0 representeert het centrale commando). De volledige groepering splitst daarna op in afzonderlijke cellen met hun eigen centrale commando (put V1, V2, V3, V4, V5)
2 Decentralisatie: het netwerk paradigma “We set up a telephone connection between us and the guys at SRI...,” Kleinrock ... said in an interview: “We typed the L and we asked on the phone, “Do you see the L?” “Yes, we see the L,” came the response. “We typed the O, and we asked, “Do you see the O.” “Yes, we see the O.” “Then we typed the G, and the system crashed”... Yet a revolution had begun”... transcriptie van het eerste communicatie over een computernetwerk in 1969 Bron: Sacramento Bee, May 1, 1996, p.D1
Terwijl decentralisatie een rol speelt in allerlei processen, is er één ontwikkeling geweest die haar bestaansrecht volledig aan decentralisatie te danken heeft: het internet. Terwijl netwerken in de vorm van bijv. het telefoonnetwerk al voor de komst van het internet een belangrijke rol speelden, werd het netwerkparadigma pas echt betekenis toen grootschalige integratie van internet in de maatschappij een feit werd. Inmiddels speelt de netwerktopologie een dominante rol in economie, technologie en steeds vaker ook in sociologische modellen. Ondanks deze volledige incorporatie van het netwerk in onze cultuur is de vanzelfsprekendheid van haar succes niet zo voor de hand liggend als op het eerste gezicht lijkt. Allereerst is het van belang een classificatie te maken van verschillende soorten netwerken. Wederom kunnen netwerkklassen worden onderverdeeld in 2 hoofdgroepen: gecentraliseerde netwerken en netwerken die gekenmerkt worden door decentralisatie (direct connect networks). Beide netwerken kunnen eenvoudig d.m.v. een graaf worden gerepresenteerd. afbeelding 2.1
gedecentraliseerde graaf (volledige graaf)
gecentraliseerde graaf
gedecentraliseerd netwerk vs gecentraliseerd netwerk. In een gedecentraliseerd netwerk is het aantal mogelijke paden van één punt naar een ander punt enorm. Alleen al het aantal Hamilton paden (pad waarbij alle punten worden bezocht) is in dat geval (n-2)! groot (bij 16 punten betekent dit al 87.178.291.200 combinaties). In een gecentraliseerde graaf is er slechts één pad van het een punt naar een ander punt, er zijn dus n verbindingen. In de gedecentraliseerde graaf zijn er n(n-1)/2 verbindingen!
In de ontwikkeling van het telefoonnetwerk zijn een aantal belangrijke inzichten opgedaan die de basiscondities vormden voor de organisatie van het internet (dit is vanzelfsprekend daar het internetnetwerk in hoge mate gebruik maakt van dezelfde infrastructuur). De ontwikkeling van het telefoonnetwerk door Graham Bell vindt opmerkelijk genoeg zijn oorsprong in een gedecentraliseerd netwerk. Wellicht valt deze keuze te plaatsen in de Amerikaanse ontwikkeling van het vrije marktdenken die in nauwe verband ligt met de toenmalige industrialisatiegolf (de vrije markt staat rechtstreeks in verband met decentralisatie). Deze discussie valt echter buiten het betoog van dit essay. Terwijl de robuustheid van het door Bell gepropageerde netwerkmodel wordt gegarandeerd, ontstonden er echter andere problemen die nauw samenhangen met de definitie van het begrip robuustheid. Deze problematiek vormt één van de hoofdthema’s in de relatief jonge wetenschap van de grafentheorie1.: de orde van complexiteit van een graaf. ‘Direct connect’ netwerken worden in de grafentheorie gerepresenteerd door zgn. volledige grafen. In een volledige graaf is ieder punt verbonden met ieder ander punt door één lijn. Het is duidelijk dat de hoeveelheid paden in een dergelijk netwerk astronomisch groot wordt (zie bijschrift afbeelding 1.6). De combinatorische complexiteit van dergelijke netwerken vormt echter een paradox. De robuustheid van een dergelijk netwerk is optimaal daar er gegarandeerd meerdere paden lopen van het ene punt naar het andere. Uiteraard is het kortste pad van een punt naar een ander punt de lijn die deze twee punten verbind. Wanneer er echter een gewicht (bijv. afstand, tijdsduur, capaciteit, etc.) wordt toegevoegd aan de lijnen, is de directe verbinding tussen twee punten niet per definitie het laagste gewicht. Er is dus de mogelijkheid dat een pad dat door meerdere punten loopt een lager gewicht heeft dan het direct pad tussen twee punten. Voor de oplossing van dit probleem zijn er diverse algoritmen ontwikkeld, maar er is nog steeds geen methodiek voorhanden die het probleem op efficiënte wijze oplost. Het fundamentele probleem ligt in de verhouding tussen locale en globale eigenschappen van een graaf. M.a.w. om het kortste pad in een graaf te vinden moet er eerst kennis voorhanden zijn over alle mogelijke paden in de graaf en aangezien dit aantal zeer snel oploopt naarmate het aantal punten van de graaf wordt vergroot, betekent dit dat het doorzoeken van de graaf een zeer tijdrovende aangelegenheid is. Constructie-algoritmen zoals dat van Dijkstra2 zijn enkel in staat om op basis van lokale eigenschappen een kortste pad te construeren. Bij gebrek aan beter wordt van dit algoritme nog steeds grootschalig gebruik gemaakt in huidige communicatienetwerken. De verhouding tussen lokale en globale eigenschappen van een netwerk kan tevens beschreven worden met twee andere begrippen die inmiddels gevleugelde termen zijn geworden: bottom-up en top-down. De groei van een netwerk is een typische bottom-up eigenschap; continu worden er knopen aan het netwerk toegevoegd zonder dat hiermee de onderligende topologie wordt ondermijnd. Er is slechts sprake van een kwantitatieve uitbreiding van het netwerk. Het bottom-up aspect ligt in het feit dat er enkel locale eigenschappen van het netwerk in kaart hoeft worden gebracht om een dergelijke groei te bewerkstelligen. De problematiek van het kortste pad ligt net als in de verhouding locaal-globaal in het feit dat een bottom-up perspectief gebruikt wordt om een top-down eigenschap te onderzoeken. 1. Het begrip graaf (“graph”) werd in 1878 geintroduceerd in het artikel getiteld “Chemistry and Algebra” (J.J. Sylvester: Chemistry and Algebra, Nature 17, 1878; pagina 284) door de wiskundige James J Sylvester. Euler deed echter al halverwege de 18de eeuw onderzoek naar grafen. 2. Edsger BWybe Dijkstra 1930-2002
afbeelding 2.2 B
B(1,A) 4
A
2
D 5
2
1
1
2
D(
A
5
2
3
C 1
E(
B(1,A) 4
1
2
,-)
,-)
1
A
5
2
3
C (5,A) 2
D (3,B)
1
A
2
D (3,B) 5
2
3
C (5,A) 3
4
1
E (5,B)
8
E
8
1
B(1,A) 4
E (4,D) 1 3
C (5,A) 4
Het vinden van het kortste pad tussen punt A en E d.m.v. het algoritme van Dijkstra. 1. Gewogen graaf, start in punt A 2. Zoek het kortste pad tussen A en de Buren van A (punt B en C) en label de afstanden en de buur van het punt waartoe de afstand is bepaald. Label alle overige punten met een oneindige afstand. Kies het punt (in dit geval B) met de kortste afstand tot punt A 3. Idem als 2 maar dan vanuit punt B. 4. Idem als 2. Merk op dat de afstand van A tot E van het pad ABE groter is dan die van het pad ABDE. Het algoritme kiest dus dit laatste pad. De totale hoeveelheid iteraties die het algoritme moet doorlopen is n-1, waardoor het algoritme behoorlijk efficiënt is.
3 Zelforganisatie Problemen die gekenmerkt worden door een enorme combinatoriek worden sinds vrij recentelijk benaderd vanuit een ander perspectief: de biologie. Een belangrijk thema dat aan deze optiek ten grondslag ligt is het fenomeen zelforganisatie. Sinds lange tijd buigen met name biologen zich over dit fenomeen dat ondanks dat het overal en veelvuldig voorkomt, lange tijd in mysterie is gehuld. Zwermen spreeuwen van die bestaan uit tienduizenden individuen volgen op macroniveau een ogenschijnlijk uiterst gecoördineerd gedrag. Grote zwermen lijken zich als een stroperige vloeistof aan de hemel te bewegen, of vormen strikte geometrische figuren (bijv. lijn of V-vorm). Hetzelfde geldt voor scholen vissen en in mindere mate voor grote kolonies insecten. De complexiteit van dergelijke structuren dermate groot dat ook als vanzelfsprekend werd aangenomen dat hier sprake was van één of andere manier van centrale controle. Zo werd lang gedacht dat er een dominant individu in een zwerm verantwoordelijk was voor het vertoonde kuddegedrag. Een voorbeeld hiervan is de koninging in een bijenkolonie waarvan lang verondersteld werd dat zij de feitelijke regering van de kolonie onder haar hoede had. Gedurende de opkomst van de eerste computers werd er rond de jaren 50 voor het eerst geëxperimenteerd met zgn. celautomaten (cellular automate). Hoewel er al eerder in de vorm van bijv. Turing machines (1936) met dergelijke methodieken werd gewerkt was het met name John von Neuman1 die de eerste celautomaten heeft ontwikkeld en onderzocht (1952). Von Neuman trachtte een model te maken t.b.v. de simulatie van zelfreproductie in de biologie2. Hierbij vervaardigde hij een systeem op basis van een grid waarop cellen discrete toestanden aan kunnen nemen (bijv. aan of uit). Deze toestanden worden geactiveerd d.m.v. een set regels die worden toegepast op iedere naburige cel (merk op dat dit dus een locale eigenschap is). In de celautomaat zijn er 4 domeinen die variabel zijn, te weten: 1. De celomgeving. Celautomaten kunnen opereren in een multi-dimensionale omgeving. Daar de complexiteit echter zelfs bij 1 of 2 dimensies enorm groot is, worden in de praktijk nauwelijks celautomaten gebruikt in een omgeving van meer dan 3 dimensies. Tevens moet worden bepaald waaruit de “buurt” van een cel bestaat. Meestal wordt gebruik gemaakt van een omgeving met 6 buren (“Moore Neighborhood”) of zelfs met slechts 4 buren (“Neuman Neighborhood”). 2. Toestand van de cel. In celautomaten wordt meestal gebruik gemaakt van discrete toestanden. Het is echter geen enkel probleem om het aantal toestanden dermate groot te maken dat er een lineaire schaal wordt benaderd (bijv. 16.7 miljoen kleuren). 3. Regels. Regels worden gedefinieerd vanuit de eigenschappen van de buren. In een celautomaat waarin cellen 2 discrete toestanden (in dit geval dood of levend) kunnen aannemen kan een regel zijn: wanneer een cel leeft en hij heeft meer dan 3 buren die ook leven dan sterft de cel. Het aantal regels dat op deze wijze kan worden geformuleerd is met name voor cellen met een grote variëteit aan toestanden zeer groot. 4. Beginsituatie. Iedere celautomaat kent een beginsituatie. Dit betekent dat een één of meerdere cellen in de celomgeving is geactiveerd. Wederom is (wanneer de celomgeving voldoende groot is) het aantal beginsituaties enorm groot. afbeelding 3.1
Eenvoudige 1-dimensionale celautomaat met links de regels en rechts het resultaat na 10 iteraties.
Het onderzoek naar celautomaten nam een vlucht tijdens de grootschalige implementatie van computers. Het aantal interacties tussen de cellen in een celautomaat is dermate groot dat de configuratie na een behoorlijk aantal iteraties onmogelijk met de hand valt te berekenen (terwijl de regels die de celtoestanden bepalen meestal uiterst eenvoudig zijn). Om het onderzoek inzichtelijk te houden, werd er vaak gewerkt met cellen die slechts in 2 discrete toestanden bestaan (in het voorbeeld van afbeelding 3.1 bestaan er slechts zwarte en witte celtoestanden). Ondanks deze beperkingen en de relatieve eenvoud van het systeem bleken celautomaten in hoge mate in staat om complexe patronen te vormen. De celautomaat uit afbeelding 3.1 bijv. blijkt na 1500 stappen geen enkele globale regelmaat te vertonen. Het is dus duidelijk dat met eenvoudige middelen een enorme complexiteit kon worden bereikt. Het gedrag van celautomaten levert echter niet in alle gevallen complexe, onvoorspelbare patronen. In sommige gevallen ontstaat er echter juist volledig geordende patronen. 1. John Louis von Neuman, 1903-1957 2. Stephen Wolfram beschrijft de ontwikkeling als volgt:“Around 1947 - perhaps based on chemical engineering - von Neumann began by thinking about models based on 3D factories described by partial differential equations. Soon he changed to thinking about robotics and imagined perhaps implementing an example using a toy construction set. By analogy to electronic circuit layouts he realized however that 2D should be enough. And following a 1951 suggestion from Stanislaw Ulam (who may have already independently considered the problem) he simplified his model and ended up with a 2D cellular automaton (he apparently hoped later to convert the results back to differential equations). “ Stephen Wolfram: Some historical notes, http://www.wolframscience.com/reference/notes/876b, 2002
Eén van de pioniers in het onderzoek naar celautomaten is Stepen Wolfram3.. Wolfram heeft een classificatie ontwikkeld waarin het gedrag van iedere celautomaat kan worden ondergebracht. Wolfram onderscheid de volgende klassen: I “Limit Point”. De eenvoudigste klasse van celautomaten. Hierin bereikt iedere celautomaat een uiteindelijke toestand waarin alle cellen ofwel dood ofwel levend zijn. Wanneer deze toestand is bereikt, is de celautomaat stabiel en veranderen cellen dus niet meer van toestand. II “Limit cycle”. Deze klasse van celautomaten vertonen repetitief gedrag. Dit betekent dat een specifiek patroon na een N aantal iteraties zich herhaald. III De derde klassen vertegenwoordigd celautomaten waarin juist geen enkele orde bestaat. Deze automata vormen bij iedere iteratie een volledig nieuw patroon. IV De meest interessante klasse wordt gevormd door automata die aan de ene kant gestructureerd en complex gedrag vertonen, maar vaak wel typische patronen vertonen van zelforganisatie. Celautomaten werken op basis van lokale interacties tussen individuele cellen. De complexe structuren die op macroniveau ontstaan zijn dus een resultante van zeer eenvoudige basisregels. Het lag dus voor de hand om dergelijke modellen te ontwikkelen t.b.v. de simulatie van kuddes, scholen en zwermen. Inmiddels zijn er dan ook talloze modellen ontwikkeld op basis van celautomaten (of afgeleiden daarvan zoals de “boids” omgeving4, die instaat zijn het complexe, maar zeer geordende gedrag van grote groepen individuen te simuleren. Het blijft fascinerend om te zien hoe op basis van enkele zeer eenvoudige regels een virtuele zwerm vogels zich vloeiend om obstakels beweegt en roofdieren ontwijkt. De regels gaan niet veel verder dan: “vlieg in de gemiddelde richting van je buren”, “hou een specifieke afstand X aan tot je buren”. Belangrijk in dergelijke modellen is dat er altijd een bepaalde mate van stochastiek wordt geïncorporeerd. Het denken vanuit een locale context betekent dat de vogel die vooraan vliegt in de karakteristieke V-vorm daar slechts bij toeval is gekomen. Een kleine willekeurige marge in de vliegsnelheid betkent dat de leider op sommige momenten wordt afgelost door een ander vogel. Zelforganisatie heeft dus een aantal eigenschappen. Het ontstaat vanuit een gedecentraliseerd systeem. Micro-interacties tussen individuen resulteren in een bepaalde mate van geordend gedrag op macro niveau, zonder dat dit gedrag kan worden voorspelt. Men spreekt dan ook over zgn. emergent gedrag.
4 Dijkstra’s mieren Simulatiemodellen gebaseerd op (afgeleide) celautomaten werden door biologen niet enkel ingezet voor het bestuderen van zwermgedrag. Weldra werden d.m.v. dezelfde benadering modellen voor andere processen uit met name de fauna ontwikkeld. Een raadselachtig fenomeen werd opgemerkt in het gedrag van mierenkolonies. Vrijwel iedereen heeft wel eens het geordende, logistiek uiterst effectieve patroon gezien waarin mieren voedsel naar het nest brengen. Mieren presteren het om in een vrijwel rechte lijn (mits er geen obstakels zijn) hun voedsel te transporteren. Vanuit het top-down perspectief bleef dit fenomeen, net als het geordende gedrag van zwermen, een raadsel. Wederom veronderstelde men dat de mierenkolonie vanuit een gecentraliseerd principe (wellicht wederom de koningin) werd geregeerd. Niets bleek echter minder waar. Het was bekend dat mieren communiceren d.m.v. feromonen. Dit zijn vloeistoffen die door de mieren worden uitgescheiden en door andere mieren worden waargenomen. Het incorporeren van deze feromonen in een model gebaseerd op een celautomaat was relatief eenvoudig. Dit maal werd er gebruik gemaakt van 2 lagen cellen: de ondergrond en de individuele mieren (de mieren konden vrij bewegen over de ondergrond). De virtuele mieren werden voorzien van een volgend algoritme: 1. Loop in een willekeurige richting van het nest. 2. Scheidt bij het verlaten van het nest tot voedsel wordt gevonden het nestferomoon uit 3. Wanneer voedsel wordt gevonden: neem een stuk voedsel mee en scheidt het voedselferomoon uit 4. Wanneer voedsel wordt vervoerd, loop in de richting van de hoogste concentratie nestferomoon (anders loop in willekeurige richting) 5. Wanneer geen voedsel wordt vervoerd, loop in de richting van e hoogste concentratie voedselferomoon (anders loop in willekeurig richting) Wanneer dit algoritme door de virtuele mierenkolonie wordt uitgevoerd, gedragen de mieren zich in eerste instantie als een ongeordende zwerm: ze lopen alle kanten op. Na verloop van tijd echter wanneer een aantal mieren het voedsel hebben gevonden ontstaat er langzaam maar zeker een vorm van zelforganisatie. Daar de mieren de feromoonsporen volgen ontstaat er een steeds grotere concentratie in een rechte verbinding tussen het nest en het voedsel. Uiteindelijk transporteren de mieren het voedsel over de kortste route en is er een volledig geordend bewegingspatroon ontstaan. Interessant van dergelijke experimenten is tevens dat de virtuele mierenkolonie adaptief gedrag vertoont. Wanneer er een obstakel in de keten tussen nest en voedsel wordt geplaatst, vertoont de kolonie in eerste instantie hetzelfde gedrag als in het begin van het experiment: de mieren lopen in een ongeordend patroon weg van het obstakel. Na verloop van tijd echter vormt zich een alternatieve route exact om het obstakel heen. De vaardigheid van de kolonie om zich aan te passen aan veranderende omstandigheden openbaart zich tevens bij bijv. het plaatsen van meerdere voedselbronnen. Adaptief gedrag is een voorwaarde voor robuustheid; de mogelijkheid om alternatieven (in dit geval paden) wanneer de primaire oplossing door wat voor reden dan ook weg valt. Het voorgaande experiment heeft grote relaties met de kortste-pad problematiek beschreven in het voorgaande hoofdstuk. Het zelforganiserend gedrag van de mieren t.o.v. hun voedselvergaring is in zekere zin een optimalisatieprobleem dat door een dergelijke afwijkende opzet op verassende wijze wordt opgelost. Wanneer we de virtuele mierenkolonie op een complex netwerk laten voortbewegen, wanneer we de verbindingen als opstakels beschouwen met een discreet gewicht (analoog aan de gewogen graaf), dan zouden de mieren in staat moeten zijn op eenzelfde wijze dit optimaliseringsprobleem op te lossen. In het artikel “Swarm Ants”5 wordt een dergelijk experiment omschreven. Bonabeau en Théraulaz beschrijven een experiment van Marco Dorigo (1992, Vrije Universiteit Brussel) waarin een mierenkolonie zich buigt over het inmiddels legendarische handelsreizigerprobleem. Dit probleem (vindt het kortste cykel in een graaf en bezoek iedere knoop slechts één maal) toont grote overeenkomsten met het kortste-pad probleem. In het experiment werd inderdaad duidelijk dat de virtuele mieren na iedere iteratie een korter pad vonden. Na een relatief klein aantal iteraties (vergeleken met traditionele algoritmen), bereikte de mierenkolonie een behoorlijk hoge mate van optimalisering. In tegenstelling tot andere algoritmen is niet bewezen dat een dergelijke methodiek ook zal leiden tot het optimale pad. Wel is experimenteel aangetoond dat de virtuele mierenkolonie (weliswaar met enige moeite) karakteristieke problemen t.a.v. lokale minima kunnen overbruggen. Een demonstratie van het zgn. “ant cycle algorithm” is te vinden op http://uk.geocities.com/markcsinklair.ace.html.
3. Stephen Wolfram, 19594. software omgeving ontwikkeld door Craig Reynolds, waarin individuele agenten (boids) onafhankelijk kunnen bewegen en net als in celautomaten op basis van locale interacties emergent gedrag vertonen. Craig Reynolds: Boids (Flocks, Hers, and Schools: a distributed beavioral model), http: //www.red3d.com/cwr/boids 5. Eric Bonabeau, Guy Theraulaz: Swarm Ants, Scientific American, maart 2000. Online op: http://dsp.jpl.nasa.gov/members/payman/swarm/ sciam/
5 Conclusie Zonder twijfel hebben gedecentraliseerde systemen een vaste plaats veroverd in onze cultuur. Belangrijk hierbij is echter om hierbij een nuancering te plaatsen, die zowel denken als toepassing betreft. Vanuit een puur toepassingskader valt te bespeuren dat gedecentraliseerde organisatiestructuren eenvoudigweg beter aansluiten op de huidige tendens van globalisering en vrije-marktwerking. De flexibiliteit en met name het aanpassingsvermogen van een gedecentraliseerde structuur in relatie tot veranderende condities is eenvoudigweg noodzakelijk om binnen de zich snel veranderende markt te manifesteren. Telkens blijkt dat traditionele machtsstructuren op basis van een gecentraliseerd model (bijv. bestaande politieke systeem), te langzaam (of te log) zijn in relatie tot de steeds snellere maatschappelijke veranderingen. In dit essay heb ik getracht hiervan een voorbeeld te geven in het eerste hoofdstuk waarbij de ontwikkelingen in de krijgsvoering als een organisatorische kwestie wordt behandeld. Interessant hierbij is dat wiskundige modellen (in dit geval grafen) wel degelijk een bijdrage kunnen leveren aan het begrippenkader waarbinnen dergelijke organisatievormen zich manifesteren. Flexibiliteit en robuustheid kunnen uitstekend in een grafenmodel worden gerepresenteerd. Naast de behandeling van decentralisatie t.a.v. organisatiestructuren is er een fundamentelere kwestie. Veel tot nu toe onopgeloste wetenschappelijke problemen blijken niet te kunnen worden gevangen in traditionele top-down methodieken (bijv. differentiaalvergelijkingen). Met name de ontwikkelingen in de biologie hebben er mijns inziens voor gezorgd dat deze problemen vanuit een ander perspectief kunnen worden benaderd, waarbij fundamentele problemen t.a.v. complexiteit resulterend uit de interactie tussen elementen in een ander oplossingskader worden geplaatst. Het paradigma waarin bottom-up denken, en de resulterende oplossingsmethodieken die hieruit voortvloeien blijken een interessant en vruchtbaar alternatief te vormen voor bestaande methodieken. Het inzetten van een virtuele mierenkolonie voor het oplossen van het kortste-pad probleem is hiervan een treffend voorbeeld. Ik realiseer mij dat dit essay slechts een korte en uiterst schetsmatige verkenning van de wellicht pretentieuze titel. De besproken voorbeelden acht ik echter karakteristiek voor de vershuivingen die plaats vinden binnen zowel maatschappelijke processen als wetenschapsbeoefening. Juni 2002
Bibliografie 1. Steven Johnson, Emergence, thhe connected lives of ants, brains, cities and software (New York: Scribner, 2001) 2. Manuel de Landa, War in the age of intelligent machines (New York: Zone Books, 1991) 3. van Tilborg, Grafentheorie (Heerlen: Open Universiteit, 1989) 4. Stephen Wolfram, A new kind of science (Champain: Wolfram media, 2002)
