AI Basics: Zoekruimtes en Berg klauteren

Als informaticus komen er soms vragen op je pad als: ‘Gegeven een aantal steden en wegen, wat is de kortste route waarbij je elke stad bezoekt en terugkomt bij je punt van vertrek?’ Dit probleem heet het Traveling Salesman Problem (TSP) en staat binnen de wereld van informatica bekend als een klassiek optimalisatie-probleem. Het klinkt in eerste instantie vrij simpel, want je kunt toch gewoon alle paden af gaan? Het zal je misschien verbazen, maar vanaf 20 steden is dit al zo onpraktisch dat je de oplossing beter kunt benaderen. Voor 20 steden zijn er namelijk 19! (121645100408832000) mogelijke paden om af te gaan. Als een computer 100.000 paden per seconde kan bekijken, dan nog zul je bijna 40.000 jaar nodig hebben om het exact te berekenen. Dat is dus geen optie. Door de oplossing niet te berekenen maar te benaderen weet je niet of je de beste oplossing krijgt, het kan dus zijn dat je niet optimaal bezig bent. Maar gezien ik betwijfel of de meeste mensen echt heel veel slechter af zijn als ze af en toe een ommetje nemen, en 40.000 jaar wachten geen optie is: hoe werkt dat benaderen?

Stel je voor dat je geblinddoekt een berg moet beklimmen. Je staat aan de voet van de berg en begint te klauteren. Je voelt met je voeten waar de berg omhoog gaat, soms steil, soms vlakker. Lukraak tast je in het duister op zoek naar houvast. Uiteindelijk voel je dat je voeten op een recht vlak staan. Je tast nog even verder en merkt dat overal om je heen de berg weer lager wordt. Blijf je staan of ga je verder?

De hill climbing methode (bergbeklimmen) is een simpele manier om zo’n probleem te benaderen. Je weet weliswaar niet waar de hoogste top is, maar je weet wel of je omhoog of omlaag gaat, en wat het hoogste punt is dat je al bezocht hebt. Die gegevens kan je in een ruimte uitdrukken, dit heet een zoekruimte. Een punt dat hoger is dan een ander geeft een betere oplossing. In het geval van het TSP kun je bedenken dat hier niet de hoogte van de piek, maar de totale afstand die je hebt afgelegd van belang is: een kortere afstand is een betere oplossing. Elke route gaat alle steden af, en daarna kan je kijken welke ‘routes’ om je heen het het beste doen. Je nabij gelegen buren in de zoekruimte lijken behoorlijk op jouw afgelegde route: ze verschillen in de volgorde van maar een paar steden. Van die buren kies je de beste uit, en je gaat weer om je heen kijken. Je kiest weer de beste buur, en zo wandel je blindelings naar de top. Daar aangekomen zullen al je buren een slechtere oplossing hebben. Maar dan weet je nog niet of je ook echt de kortste route hebt gevonden, we hebben geen zekerheid dat we de ‘werkelijke’ top hebben bereikt. We zitten misschien in een lokaal maximum: een plek die niet de echte top van de berg is, maar alleen een heuveltje in het landschap. Er zijn misschien betere plekken.

Als je bang bent dat je in een lokaal optimum terecht bent gekomen, en geen weg meer naar een hogere piek vindt, kan je naar beneden rollen en een aantal keer compleet opnieuw beginnen (random restart). Dan start je op verschillende plekken en bekijk je het probleem telkens vanuit een andere hoek. En wie weet kom je dan wel eens bij de berg die het hoogste is. Dit is natuurlijk geen garantie, want het kan zijn dat je blindelings elke keer op dezelfde plek omhoog klimt of dat je toch nooit die hoogste top vindt. Je zult het gewoon moeten proberen en zien of het beter wordt.

Natuurlijk is het bij de meeste problemen gek dat we blind naar een top zouden gaan zoeken. Als je brieven moet bezorgen in Amsterdam, Utrecht en Maastricht is de kans groot dat het voordeliger is Amsterdam en Utrecht na elkaar te doen, en niet tussendoor naar Maastricht te gaan om weer helemaal terug te moeten. Dit soort kennis noem je domeinkennis. Als je genoeg domeinkennis hebt hoef je het probleem natuurlijk niet te benaderen, want dan heb je het antwoord al. Helaas is domeinkennis vaak niet zodanig beschikbaar dat je het probleem meteen kan oplossen.

Zoeken door zulke ruimtes wordt veel gedaan in A.I. omdat het een hele praktische manier om een oplossing te benaderen is. Hill climbing en random-restart hill climbing zijn maar twee van de vele manieren waarop je zo’n zoekruimte kunt doorlopen. Deze familie noemen ze ook wel local search (tegenover global search), omdat het lokaal zoekt bij zijn buren of er een betere oplossing te vinden is. Local search is een grappige manier om na te denken over je problemen omdat het je leert te accepteren dat sommige oplossingen niet perfect zijn maar wel voldoende. Tevens legt het heel goed uit hoe het soms moeilijk kan zijn om van een oplossing af te stappen omdat het daardoor slechter wordt. Ook als het vaak de enige manier is om echt vooruit te komen.