Toen het gratis dagblad Metro nog op NS-stations en andere
uitdeelpunten te vinden was, stond daar regelmatig de puzzel Kamertje
verhuur
in. Bij de HCC Artificiële
Intelligentie interessegroep opperde Titus Krijgsman dat deze puzzels
misschien aangepakt kunnen worden met een genetisch algoritme
(GA). Dat leidde tot de oprichting van een projectgroepje, dat zichzelf
een maand de tijd gaf om dat uit te zoeken. Mijn deelname aan die
onderneming leverde, naast de nodige kennis, inzicht en ervaring, ook
deze webpagina op. Hieronder wordt eerst de puzzel zelf uitgelegd, en
daarna het genetische algoritme.
Bij het opstarten (of herladen) toont deze webpagina hieronder een
voorbeeldpuzzel, geleend
uit de Metro van 25 februari 2019. Het
diagram (met blauwgrijze achtergrond) bevat 81 kamertjes
(9
horizontaal bij 9 vertikaal; de hoekpunten zijn met dikke vierkante
stippen
aangegeven), die elk minimaal 0 en maximaal 4
wandjes
kunnen krijgen. Kamertjes met een cijfer moeten precies
zoveel wandjes krijgen als het cijfer aangeeft; voor kamertjes zonder
cijfer is het aantal wandjes (nog) onbekend. De wandjes die al in het
diagram zijn ingetekend, zijn vooraf gegeven (dat wil zeggen,
verplicht!). Alle wandjes samen moeten één grote lus (=
rondgaande lijn) vormen, die zichzelf nergens snijdt of raakt.
Het is leerzaam om zelf eens te proberen of u de puzzel kunt oplossen.
Dat kan door te klikken op de plekken waar u de muurtjes wilt hebben.
Reeds aanwezige muurtjes worden juist verwijderd als erop wordt geklikt;
zo kunt u desgewenst een vergissing herstellen. Maar wees voorzichtig!
Ook de oorspronkelijk gegeven muurtjes kunnen zo worden gewist, waardoor
u de puzzelopgave verminkt
en mogelijk onoplosbaar maakt. En als
u per ongeluk op een kamertje klikt (doordat u een muurtje net mist)
verminkt u de puzzel ook, want dan verandert het cijfer in dat kamertje.
Mocht u de voorbeeldpuzzel door verkeerd klikken onbruikbaar hebben
gemaakt, en u kunt dat niet meer herstellen, dan zit er weinig anders
op dan deze webpagina te herladen en weer opnieuw te beginnen —
of het op te geven, en het genetisch algoritme te proberen.
Het idee is om de oplossing van de puzzel in de computer te laten
evolueren
. Het programma verzint
willekeurig,
a.h.w. door telkens een muntje op te gooien, een aantal strings
(computerwoorden
) waarin gecodeerd staat welke muurtjes wel en
welke niet aanwezig zijn. Zo'n string, naar analogie met de biologische
genetica ook wel chromosoom genoemd, vormt dus een
mogelijke oplossing van de puzzel. De kans dat één
van die probeeroplossingen
toevallig volledig correct is, is
natuurlijk (nagenoeg) nul; sommige zullen veel fouten bevatten, en andere
wat minder.
Uit deze eerste groep probeersels, de zgn. begingeneratie, kiest het programma een even grote nieuwe generatie, waarbij de beste probeersels (d.w.z. met de minste fouten) de meeste kans maken om (evt. meermalen) in de nieuwe generatie terug te komen (selectie). Daarna vindt er kruising plaats: de probeersels wisselen willekeurig stukjes met elkaar uit, in de hoop dat oplossingen die al grotendeels goed zijn hun resterende slechte stukjes inruilen voor andere, betere stukjes. Voor de goede orde worden tenslotte ook nog blindweg hier en daar een paar willekeurige wijzigingen in de probeersels aangebracht (mutatie).
Door deze drie stappen (selectie, kruising en mutatie) telkens te herhalen, zou de verzameling van probeersels (de populatie) gemiddeld geleidelijk steeds minder fouten moeten gaan bevatten, totdat er uiteindelijk hopelijk een probeersel verschijnt zonder fouten: de oplossing van de puzzel.
Onder het diagram staan eerst enkele regels waar het programma uitvoer
kwijt kan (generatie:
, aantal fouten:
, en een lege regel
voor mededelingen of foutmeldingen), en daaronder weer een rijtje knoppen
(wis
, onthoud
, herstel
, begin
en ga!
).
Om het genetisch algoritme (GA) uit te proberen moet er een correcte
puzzelopgave (zoals de voorbeeldpuzzel — herlaad zonodig deze
pagina) in het diagram staan. Druk op de begin-knop om op grond
van het diagram een beginpopulatie aan te maken. Door op ga! te
klikken zet u het GA in gang; van elke generatie wordt het beste
probeersel
in het diagram getoond, met het bijbehorende aantal
fouten eronder. Wanneer de oplossing van de puzzel (0 fouten) is gevonden,
stopt het GA uit zichzelf. Door de rol die toeval in een GA speelt, is
niet te voorspellen hoe lang dat duurt. De voorbeeldpuzzel vergt
gewoonlijk minder dan 10.000 generaties — maar garanties
zijn er niet. En er zullen ook puzzels zijn waar het GA niet, of zeer
zelden, een oplossing vindt.
Wanneer u het genetisch algoritme opstart, krijgt de ga!-knop het
opschrift stop
. U kunt dan dezelfde knop gebruiken om het proces
te onderbreken (bijv. om het diagram eens goed te bestuderen). Bij
onderbrekingen krijgt de knop weer het opschrift ga!
en kunt U
'm gebruiken om het programma weer door te starten.
Nieuwe puzzels kunnen in het diagram worden ingevoerd door te klikken op
muurtjes (om ze aan
of uit
te zetten) en op kamertjes (om
het cijfer te veranderen). Vooraf kan het diagram desgewenst worden
leeggemaakt door op de wis-knop te drukken. Zodra de puzzel
correct in het diagram staat, kan met begin en ga! het
GA weer worden beproefd.
U kunt nieuwe puzzels op het Internet vinden: zoek op kamertje
verhuur
, kamertje verhuren
, of slitherlink
(de meest voorkomende engelse naam voor dit type puzzel).
Dit programma kan natuurlijk geen puzzels groter dan 9×9
behappen. Puzzels van 7×7 of kleiner kunnen wel worden ingevoerd,
door de vakjes aan de rand(en) te vullen met nullen; deze truc werkt
niet voor 8×8-puzzels, omdat er tussen de omringende nullen en
het eigenlijke diagram een rij lege vakjes moet overblijven.
werkgeheugen
Omdat het zelf invoeren van puzzels op den duur niet leuk meer is, is het programma voorzien van een primitieve geheugenfunctie: de onthoud-knop slaat de huidige stand van het diagram op in het programmageheugen. (Die wordt dus slechts bewaard zolang de pagina in de browser staat!) De herstel-knop zet de laatst opgeslagen versie van het diagram terug. Dat kan van pas komen als u het GA vaker wilt loslaten op een en dezelfde handmatig ingevoerde puzzel — bijvoorbeeld om statistieken te verzamelen, of om, als het GA er niet uitkomt, het nogmaals te proberen met een nieuwe beginpopulatie.
© GV 17-01-2024
Terug naar leesmij.txt.