A Genetic Algorithm for Locating Optimal Sites on Raster Suitability Maps

Christopher J. Brookes
Department of Geography, University College London, 26 Bedford Way, London WCIH OAP, United Kingdom

Raster suitability maps can be generated within a GIS using standard multi-criteria evaluation techniques (Jankowski, 1995), but their use for site location is problematic when the sites are larger than the cell size. A candidate site is a region, i.e. a cluster of contiguous cells, which meets both spatial and non-spatial criteria. When the site size is much larger than the cell size, shape becomes a meaningful criterion. The search space for this problem is large and complex; there are many alternate clusters of cells and small changes in the size, location, or configuration, of clusters can have large affects on utility. This paper describes a genetic algorithm which searches for optimal clusters and thereby locates optimal sites. In simulated problems the genetic algorithm finds better solutions than a heuristic search does.

The cell values in a suitability raster are measures of the intrinsic, or non-spatial, suitability of each cell. Optimal regions involve a trade-off between the intrinsic suitability of individual cells and the spatial configuration of cells. or example, the shape of a habitat patch is important because compact shapes minimise edge effects (Morrison et al., 1992). The cells with the highest scores for non-spatial criteria may not constitute viable patches and consequently the optimal patch will incorporate cells with lower scores.

The genetic algorithm technique
Genetic algorithms can successfully find near-optimal global solutions in complex search spaces using only information about the utility of trial solutions (Goldberg, 1989; Davis, 1991). The technique described here couples a genetic algorithm to a raster GIS via a parameterised region growing (PRG) program. The PRG program grows regions on a suitability raster under the control of a string of numeric parameters (Brookes, in press). For any given suitability raster, a set of PRG parameters precisely specifies a region and consequently an optimal PRG parameter set corresponds to an optimal region. It follows that a search for an optimal parameter set is equivalent to a search for an optimal region. The genetic algorithm operates on a population of PRG parameter strings and uses PRG to translate strings into regions which are evaluated within a GIS. The results of the GIS analysis are passed back to the genetic algorithm as fitness values. There are three types of PRG parameters: (1) the control parameters which specify the region's size and location; (2) the shape parameters which guide the region towards an ideal shape; and (3) the trade-off parameter which determines the relative influence of shape suitability and intrinsic suitability. How far the actual region deviates from the ideal shape depends on the trade-off parameter and the underlying suitability raster.

Evaluation of the algorithm
The technique was evaluated by comparing the genetic algorithm solutions to those found by a heuristic method in ten trials. Each trial used the same problem but a different suitability map.

The trial problem was to locate a habitat patch of size 100 cells with optimal core area. The core is all cells which are greater than a threshold distance from the patch perimeter (Laurance, 1991). The utility of a site was defined as the sum of the intrinsic suitability scores of all core cells and the objective was to maximise utility. In the trials the core was defined as all cells more than 1 cell in from the perimeter.

Ten suitability maps were generated to simulate different landscapes patterns. Each Map is a patchwork of natural regions. The typical region size varies between maps, from about 1 cell on map 1, to about 600 cells on map 10. At one extreme, regions of high intrinsic suitability are small, irregularly shaped and widely scattered while at the other extreme the habitat patch would fit easily inside a natural region. Small random variations were superimposed on the maps. Thus, the regions are not homogenous but differences between cells in different regions are greater than differences between cells within a region.

The heuristic method employs two steps: first the search space is reduced by fixing some of the PRG parameters and then the remaining space is exhaustively searched. The fixed parameters were those for a circle (the most compact shape) of size 100 and a trade-off giving equal weight to spatial and non-spatial suitability. With these values all possible locations were evaluated.

In each trial the genetic algorithm utility score exceeded the heuristic score. The difference between scores was greatest for the map with the smallest natural regions and least for those maps where the natural regions are greater than the target size.

Two results are particularly interesting. First, the optimal trade-off varied but was always biased towards spatial suitability. There is no obvious relationship between optimal trade-off and the map characteristics and this result highlights the complex interaction between PRG parameters and map characteristics. Second, the chosen heuristics were suitable for maps with large natural areas but not for those with small areas, whereas the genetic algorithm tackled both problems equally well.

The genetic algorithm can be applied without modification to a range of single site problems. Further research will extend the algorithm to tackle multiple site problems and evaluate the method in case studies.

Brookes, C.J. in press. "A parameterised region-growing program for site allocation on raster suitability maps".

Davis, L.L., 1991. Handbook of genetic algorithms. New York: Van Nostrand Reinhold.

Goldberg, D.E. 1989. Genetic algorithms in search, optimisation, and machine learning. Reading, Massachusetts: Addison-Wesley.

Jankowski, P. 1995. "Integrating geographical information systems and multiple criteria decision-making methods", International Journal of Geographical Information Systems, 9, 251-273.

Laurance, W.F. 1991. "Edge effects in tropical forest fragments: Application of a model for the design of nature reserves", Biological Conservation, 57, 205-219.

Morrison, M.L., Marcot, B.G. and Mannan, R.W. 1992. Wildlife habitat relationships. Wisconsin: University of Wisconsin.