Genetic algorithms for map labeling

Abstract

Map labeling is the cartographic problem of placing the names of features (for example cities or rivers) on the map. A good labeling has no intersections between labels. Even basic versions of the problem are NP-hard. In addition, realistic map-labeling problems deal with many cartographic constraints, which pose more demands on how the labels should be placed in relation to their surroundings. For example, a label is preferably placed above and to the right of a city. These two aspects (combinatorially hard and the need of considering cartographic rules) make the problem challenging. Genetic algorithms (GAs) are heuristic solvers for optimization problems. Based on the theory of Darwinian evolution, they are able to "evolve" solutions using a process similar to adaptation in biology. In this thesis we apply GAs to solve map-labeling problems. Problems dealing with point features (like cities) and line features (like rivers) are discussed. It is also shown how additional cartographic rules can be incorporated in the algorithm. Experiments done on randomly-generated maps and real-world data show that the GAs are successful in finding good solutions. The GAs were designed with theoretical insights regarding linkage and mixing in mind. The map-labeling problem is interesting in that its linkage is geometrically determined and therefore reasonably clear. This property was exploited in the design of the GAs. The GAs were also used to verify the predictions of theoretical models from literature (a convergence model and a population-sizing model). The GA was able to match the assumptions of the models thanks to a novel operator, the so-called geometrically local optimizer. Experimental results indeed matched the predictions of the models. As a result, the number of fitness evaluations scales linearly with the input size (the size of the map).