A Unified Conceptual Framework for Geographical Optimization Using Evolutionary Algorithms

Abstract

During the last two decades, evolutionary algorithms (EAs) have been applied to a wide range of optimization and decision-making problems. Work on EAs for geographical analysis, however, has been conducted in a problem-specific manner, which prevents an EA designed for one type of problem from being used on others. In this article, a formal, conceptual framework is developed to unify the design and implementation of EAs for many geographical optimization problems. The key element in this framework is a graph representation that defines the spatial structure of a broad range of geographical problems. Based on this representation, four types of geographical optimization problems are discussed and a set of algorithms is developed for problems in each type. These algorithms can be used to support the design and implementation of EAs for geographical optimization. Knowledge specific to geographical optimization problems can also be incorporated into the framework. An example of solving political redistricting problems is used to demonstrate the application of this framework.

Durante las últimas dos décadas, se han aplicado algoritmos evolucionarios (evolutionary algorithms, EA) a una amplia variedad de problemas de optimización y toma de decisiones. Sin embargo, el trabajo en los EA para análisis geográficos se ha realizado de manera específica al problema, que evita que un EA diseñado para un tipo de problema se use para resolver otros problemas. En este artículo se desarrolla un marco conceptual formal para unificar el diseño y la implementación de EA para muchos problemas de optimización geográfica. El elemento clave en este marco es una representación grafica que define la estructura espacial de una amplia variedad de problemas geográficos. Con base en esta representación, se discutieron cuatro tipos de problemas de optimización geográfica y se desarrolló un conjunto de algoritmos para cada tipo de problemas. Estos algoritmos se pueden usar para apoyar el diseño y la implementación de EAs para optimización geográfica. También se puede incorporar en el marco conocimiento específico a los problemas de optimización geográfica. Se usa un ejemplo de resolución de reasignación de distritos políticos para demostrar la aplicación de este marco.

Key words:

• evolutionary algorithms
• geographical optimization problems
• location–allocation analysis
• political redistricting
• spatial representation

关键词:

• 进化算法
• 地理优化问题
• 布局-分配的分析
• 政治选区重划
• 空间表征

Palabras clave:

• algoritmos evolutivos
• problemas de optimización geográfica
• análisis de ubicación-asignación
• reasignación de distritos políticos
• representación espacial

Acknowledgments

I thank Marc P. Armstrong and Iris Hui for their valuable comments. Comments from Mei-Po Kwan and anonymous reviewers are also acknowledged.

Notes

^aThe total population of all spatial units in a data set.

^bThe number of individual solutions used in GEAPR.

^cThe total number of iterations of GEAPR.

^dThe theoretically possible optimal objective function value.

^eThe objective function value of the best solution found in the ten runs.

^fThe median of the best objective function values found in the ten runs.

^gThe objective function value of the worst solution found in the ten runs.

^hAverage last iteration when a better solution is found.

ⁱAverage CPU time used for each run (in seconds).

1. The term geographical optimization problem is loosely used in this article. In general, such a problem requires search for the configuration of a set of discrete spatial entities. In other words, a solution to this type of problem exhibits a spatial pattern that can be displayed on a map. A solution to a p-median problem (Hakimi 1965), for example, represents a spatial configuration where the demand in each geographical unit is served by its nearest facility and a service area map can be drawn accordingly. Some optimization problems with spatial components (see, for example, Leung, Li, and Xu 1998) may not necessarily have this characteristic and therefore are not directly considered in this article, although research incorporating these problems will be an interesting future topic.

2. If a problem can be solved in a time frame that is polynomial with respect to input size, the problem is placed into class P and is typically regarded to be “easy” to solve. For problems in class NP-complete (NP stands for nondeterministic polynomial), however, polynomial time algorithms have not been developed and it is likely that such algorithms do not exist. See Garey and Johnson (1979) and Cormen et al. (2001, ch. 34) for a more formal discussion of this issue.

3. Geographical optimization problems often contain important social, economic, and political factors that are difficult, if not impossible, to place in a mathematical formulation. Optimal solutions to mathematically well-formulated problems will become nonoptimal when the unmodeled factors or objectives are taken into account. Therefore, near optimal (or second best) solutions to a problem may be favorable to decision makers (Simon 1960; Brill 1979; Hopkins 1984).

4. It is important to distinguish spatial constraints and other constraints that may have spatial implications. In this article, spatial constraints refer to explicit requirements of the topological configuration of spatial units. For many applications, some constraints may have spatial implications but they do not require the configuration (or pattern) of spatial units. For example, in the work of Bennett, Xiao, and Armstrong (2004), it is required that the total area of particular land use types should not exceed 25 percent of the overall size of the study area. This requirement, however, does not confine the topological relationship between spatial units and therefore is not considered as a “spatial” constraint in the context of this research.

5. For a redistricting problem of partitioning n spatial units into r districts, the exact number of possible redistricting plans is difficult to compute. However, we know that the upper bound of this number is a “Stirling number of the second kind” that is defined as (see, Even 1973, 60), which occurs when each unit is adjacent to all other units. The lower bound of the number of possible plans occurs when the units are least connected, meaning units arranged as a line and, except for the units at both ends, each unit has only two adjacent units; in this case, there are S ₁ (n,r) = possible plans. For the example of Iowa redistricting, where n = 99 and r = 5, the total number of possible redistricting plans is between 3.6 × 10⁶ and 1.3 × 10⁶⁷.

6. Interactive redistricting software tools are available in many GIS packages such as an ArcView extension (http://www.esri.com/software/arcview/extensions/distr-icting) and a commercial package called Maptitude for Redistricting (http://www.caliper.com/mtredist.htm). Both URLs were last accessed on 18 December 2007.

7. Although compactness is a critical factor, studies did not show that there is no necessary relation between the shape of redistricting plans and gerrymandering, a process intended to favor a particular political party or interest group (Taylor and Johnston 1979), and different compactness measures may lead to different conclusions (Altman 1998b).

8. If we assume all spatial units are adjacent to each other, the optimal solution occurs when the population difference between any two districts is not greater than 1. Accordingly, the optimal objective function value can be calculated as 100× . When the total population can be evenly divided by r, the theoretical optimal solution should have an objective function value of zero. It is important to stress the assumption used here because such a theoretical optimal objective function value may not exist in the spatial connectivity of a real data set.

9. Iowa Code 42.4(1)(b).