Hoorcollege
Zwerm-intelligentie en slime mould
Kennen
Enkele voorbeelden van NP-volledige problemen: het rugzakprobleem, het handelsreizigerprobleem (TSP), het vervulbaarheidsprobleem in propositielogica (SAT), het kliekprobleem, het schuifpuzzelprobleem, het dominantieprobleem.
Ontzettend veel problemen zijn NP-volledig, zoals combinatorische problemen, optimalisatieproblemen, routeproblemen, planproblemen, roosterproblemen, en vervulbaarheidsproblemen.
NP-volledig betekent: NP en minstens even moeilijk als elk ander NP probleem.
NP-volledige problemen zijn allemaal even moeilijk: heb je een goed algoritme voor één NP-volledig probleem, maakt niet uit welke, dan heb je meteen een goed algoritme voor alle NP-volledige problemen.
De notie NP probleem: in non-deterministisch-polynomiale tijd op te lossen. Wat dit precies betekent hoef je niet te weten. Wat je wel moet weten is dat zoeken typisch exponentiële tijd kost (vaak niet hard te maken dat dat noodzakelijk zo is), maar dat aangereikte of gevonden kandidaat-oplossingen altijd snel (officieel: in polynomiale tijd) zijn te verifiëren.
Het handelsreizigerprobleem: vind een kortste gesloten toer die elke stad aandoet, waarbij tussen elk tweetal steden gereisd mag worden en een afstand bekend is.
Mierenkolonie-optimalisatie (ACO): mieren, voedsel, geurstof, pad.
De mier als handelsreiziger: mieren lopen in generaties, en paden van winnaars (kortste toerders) krijgen extra feromoon.
De aantrekkelijkheid van een verbinding (i, h) is gelijk aan m(i, h)v(i, h)β, waarbij m feromoon is, v omgekeerd evenredig aan de afstand d(i, h), en β een stuurparameter.
Hoe de mier een volgens stad kiest bij 1) exploratie 2) exploitatie.
De functie van de parameters α (neiging to exploratie), β (neiging tot kiezen van kortste verbindingen in weerwil van feromoon) en ρ (verdampingssnelheid).
Status theorievorming ACO.
Wat slijmzwammen zijn en dat de slijmzwammen Physarum Polycephalum (“Physarum”) en Dictyostelium Discoideum (“Dicty”) gebruikt worden als inspiratie voor zoekalgoritmen.
De Japanse school (stroom door pijpleidingen, continue wiskunde); de Europese school (deeltjes op een grid, discrete wiskunde).
Mechanisme van een Physarumdeeltje op een grid. De sensoren FL, FF, FR; de parameters SO, SA, RA en ST.
De notie Steiner tree en eigenschappen daarvan. De relatie tussen Steiner trees en de patronen die ontstaan bij gridsimulatie van Physarum.
Methodes om voedsel op een grid te initialiseren: filamenteuze condensatie (filamentous condensation), filamenteus voederen (filamentous foraging), en plasmodiale krimp (plasmodial shrinkage).
Het handelsreizigers-probleem oplossen met gesimuleeerde Polycephalum.
Kunnen
Aangeven naar welke stad een mier loopt als m, d en β gegeven zijn. Bij exploratie, bij exploitatie.
Een gevoeligheidsanalyse doen in een ACO-model, i.e., aangeven wat er in een simulatie veranderd als één van α, β of ρ iets stijgt (of daalt).
Een deeltjesmodel van Physarum ontwerpen, en implementeren in een speciaal daarvoor ingerichte programmeeeromgeving zoals Netlogo of Java's Processing.
Materiaal
Slides Zwerm-intelligentie en slime mould.
Dictaat Marco Wiering H4.4.
Art. Jones & Adamatzky.
Werkcollegedictaat.