De genetica van de cartografie
6 november 2001
Utrechtse informatici hebben in een project van NWO een computerprogramma gemaakt dat zoveel mogelijk namen op landkaarten zet zonder dat deze overlappen. Het programma gebruikt wiskundige regels geïnspireerd op de evolutieleer.
Het Utrechtse programma kan onder andere planologen helpen die snel een specifieke kaart moeten produceren met veel technische details. Die informatie is bijvoorbeeld belangrijk voor het bepalen van de locatie van een toekomstige fabriek. Het Utrechtse programma zet zoveel mogelijk namen overzichtelijk op de kaart die door een geografisch informatiesysteem is samengesteld.
Een probleem bij het automatisch maken van kaarten, is het plaatsen van de namen op de kaart. Elk land, elke stad en elke rivier hebben een naam die herkenbaar op de kaart moet komen. Namen mogen elkaar niet overlappen. De naam van een land moet ongeveer de vorm van het gebied aangeven. Bij een lange rivier moet de naam worden herhaald.
Het computerprogramma gebruikt een genetisch algoritme uit de heuristiek. De heuristiek is de wetenschap die, grof gezegd, via gericht gokken tot een zo goed mogelijk resultaat komt. De klassieke methode die de beste oplossing zoekt, vergt zelfs voor krachtige computers te veel rekenwerk.
Het genetisch algoritme werkt als volgt. De onderzoekers laten de computer willekeurig tweehonderd kaarten maken. Dat is de eerste generatie. De computer selecteert de kaarten met zo weinig mogelijk overlappende plaatsnamen. Uit deze selectie ontstaat de tweede generatie.
Dit gebeurt via de uit de genetica overgenomen begrippen mutatie en crossing over. Bij mutatie verplaatst de computer een naam van een stad naar een andere plek in de buurt van die stad. Crossing over wil in dit geval zeggen dat stukken van de ene kaart combineren met stukken van de andere kaart.
De tweede generatie kaarten bestaat opnieuw uit tweehonderd kaarten. De computer selecteert weer de beste kaarten en combineert ze. Het onderzoek wees uit dat na hooguit vijftig generaties de kaart is uitgeëvolueerd. De kaart is dan voor 97% perfect.
Tot nu toe vertoonden rekenmethodes exponentieel opschalingsgedrag. Anders gezegd, elke plaatsnaam extra verdubbelt de rekentijd. Bij de Utrechtse methode verdubbelt de rekentijd pas als het aantal plaatsnamen met de helft toeneemt. Hier is sprake van kwadratisch opschalingsgedrag.
Nadere informatie bij
* drs. Steven van Dijk (UU, Informatica Instituut)
* tel. 030 253 9049 of 030 253 1454 (secr)
* fax 030 251 3791
* e-mail
* internet
* Promotie 26 november, promotor prof.dr. M.H. Overmars