Multiobjective site-search problems are a class of decision problems that have geographical components and multiple, often conflicting, objectives; this kind of problem is often encountered and is technically difficult to solve. In this paper we describe an evolutionary algorithm (EA) based approach that can be used to address such problems. We first describe the general design of EAs that can be used to generate alternatives that are optimal or close to optimal with respect to multiple criteria. Then we define the problem addressed in this research and discuss how the EA was designed to solve it. In this procedure, called MOEA/Site, a solution (that is, a site) is encoded by using a graph representation that is operated on by a set of specifically designed evolutionary operations. This approach is applied to five different types of cost surfaces and the results are compared with 10 000 randomly generated solutions. The results demonstrate the robustness and effectiveness of this EA-based approach to geographical analysis and multiobjective decisionmaking. Critical issues regarding the representation of spatial solutions and associated evolutionary operations are also discussed.
Get full access to this article
View all access options for this article.
References
1.
ArentzeT ABorgersA W JTimmermansH J P, 1996, “An efficient search strategy for site-selection decisions in an expert system”Geographical Analysis28126–146
2.
ArmstrongM P, 2000, “Geography and computational science”Annals of the Association of American Geographers90146–156
3.
ArmstrongM PDenshamP JLolonisPRushtonG, 1992, “Cartographic displays to support locational decision making”Cartography and Geographic Information Systems19154–164
4.
BaerwaldT J, 1981, “The site selection process of suburban residential builders”Urban Geography22339–357
5.
BeasleyDBullD RMartinR R, 1993, “A sequential niche technique for multimodal function optimization”Evolutionary Computation1101–125
6.
BennettD AWadeG AArmstrongM P, 1999, “Exploring the solution space of semi-structured geographical problems using genetic algorithms”Transactions in GIS351–71
7.
BrillE DJrFlachJ MHopkinsL DRanjithanS, 1990, “MGA: a decision support system for complex, incompletely defined problems”IEEE Transactions on Systems, Man, and Cybernetics20745–757
8.
BrookesC J, 1997, “A parameterized region-growing programme for site allocation on raster suitability maps”International Journal of Geographical Information Science11375–396
9.
BrookesC J, 1998, “A genetic algorithm for locating optimal sites on raster suitability maps”Transactions in GIS2201–212
10.
BrookesC J, 2001, “A genetic algorithm for designing optimal patch configurations in GIS”International Journal of Geographical Information Science15539–559
11.
Cantú-PazEGoldbergD E, 2000, “Efficient parallel genetic algorithms: theory and practice”Computer Methods in Applied Mechanics and Engineering186221–238
12.
CasatiRSmithBVarziA C, 1998, “Ontological tools for geographic representation”, in Formal Ontology in Information Systems Ed. GuarinoNIOS Press, Amsterdam) pp 77–85
13.
ChambersLTaylorM, 1996, “Planning with GENIE: a model for forecasting and decisionmaking”Environment and Planning B: Planning and Design23697–709
14.
CoelloC A C, 2000, “An updated survey of GA-based multiobjective optimization techniques”ACM Computing Surveys32109–143
15.
CohonJ L, 1978Multiobjective Programming and Planning (Academic Press, New York)
16.
CovaT JChurchR L, 2000a, “Contiguity constraints for single-region site search problems”Geographical Analysis32306–329
17.
CovaT JChurchR L, 2000b, “Exploratory spatial optimization in site search: a neighborhood operator approach”Computers, Environment and Urban Systems24401–419
18.
CurrentJMinHSchillingD, 1990, “Multiobjective analysis of facility location decisions”European Journal of Operational Research49295–307
19.
DebK, 1997, “Introduction (to representations)”, in Handbook of Evolutionary Computation Eds BäckTFogelD BMichalewiczZOxford University Press, New York) pp C1.1:1–4
20.
DebK, 1999, “Multi-objective genetic algorithms: problem difficulties and construction of test problems”Evolutionary Computation7205–230
21.
De JongK A, 1975An Analysis of the Behavior of a Class of Genetic Adaptive Systems doctoral dissertation, Department of Computer and Communication Sciences, University of Michigan, Ann Arbor, MI
22.
De JongK A, 1998, “Evolutionary computation: where we are and where we're headed”Fundamenta Informaticae35247–259
23.
DenshamP J, 1994, “Integrating GIS and spatial modelling: visual interactive modelling and location selection”Geographical Systems1203–219
24.
DibbleCDenshamP J, 1993, “Generating interesting alternatives in GIS and SDSS using genetic algorithms”, in Proceedings of GIS/LIS '93Minneaspolis, Minnesota, pp 180–189
25.
DiplockG, 1998, “Building new spatial interaction models by using genetic programming and a supercomputer”Environment and Planning A301893–1904
26.
FischerM MLeungY, 1998, “A genetic-algorithms based evolutionary computational neural network for modelling spatial interaction data”The Annals of Regional Science32437–458
27.
FogelD B, 2000Evolutionary Computation: Toward a New Philosophy of Machine Intelligence (IEEE Press, Piscataway, NJ)
28.
FogelD BAngelineP J, 1997, “Guidelines for a suitable encoding”, in Handbook of Evolutionary Computation Eds BäckTFogelD BMichalewiczZOxford University Press, New York) pp C1.7:1–2
FogelL JOwensA JWalshM J, 1966Artificial Intelligence through Simulated Evolution (John Wiley, New York)
31.
FonsecaF TEgenhoferM J, 1999, “Ontology-driven geographic information systems”, in ACM GIS '99: Proceedings of 7th International Symposium on Advances in Geographic Information Systems Ed. MedeirosC MACM Press, New York) pp 14–19
32.
FonsecaC MFlemingP J, 1993, “Genetic algorithms for multiobjective optimization: formulation, discussion and generalization”, in Proceedings of the Fifth International Conference on Genetic Algorithms Ed. ForrestSMorgan Kaufmann, San Mateo, CA) pp 416–423
33.
FonsecaC MFlemingP J, 1995, “An overview of evolutionary algorithms in multiobjective optimization”Evolutionary Computation31–16
34.
FonsecaC MFlemingP J, 1998, “Multiobjective optimization and multiple constraint handling with evolutionary algorithms—part I: application example”IEEE Transactions on Systems, Man, and Cybernetics—Part A2838–47
35.
FonsecaF TEgenhoferM JDavisC AJrBorgesK A V, 2000, “Ontologies and knowledge sharing in urban GIS”Computer, Environment and Urban Systems24251–272
36.
GaltonA, 2001Qualitative Spatial Change (Oxford University Press, Oxford)
37.
GhoshARushtonG, 1987, “Introduction: progress in location-allocation modeling”, in Spatial Analysis and Location – Allocation Models Eds GhoshARushtonGVan Nostrand Reinhold, New York) pp 1–18
38.
GilbertK CHolmesD DRosenthalR E, 1985, “A multiobjective discrete optimization model for land allocation”Management Science311509–1522
39.
GoldbergD E, 1989Genetic Algorithms in Search, Optimization and Machine Learning (Addison-Wesley, Reading, MA)
40.
GoldbergD ERichardsonJ, 1987, “Genetic algorithms with sharing for multimodal function optimization”, in Genetic Algorithms and Their Applications: Proceedings of the Second International Conference on Genetic Algorithms Ed. GrefenstetteJ JLawrence Erlbaum Associates, Hillsdale, NJ) pp 41–49
41.
GrefenstetteJ, 1997, “Rank-based selection”, in Handbook of Evolutionary Computation Eds BäckTFogelD BMichalewiczZOxford University Press, New York) pp C2.4:1–6
42.
GuarinoN, 1998, “Formal ontology and information systems”, in Formal Ontology in Information Systems Ed. GuarinoNIOS Press, Amsterdam) pp 3–15
43.
Guimarães PereiraÂ, 1996, “Generating alternative routes by multicriteria evaluation and a genetic algorithm”Environment and Planning B: Planning and Design23711–720
HobbsM, 1996, “Spatial clustering with a genetic algorithm”, in Innovations in GIS 3 Ed. ParkerDTaylor and Francis, London) pp 85–93
46.
HollandJ H, 1975Adaptations in Natural and Artificial Systems (University of Michigan Press, Ann Arbor, MI)
47.
HopkinsL D, 1984, “Evaluation of methods for exploring ill-defined problems”Environment and Planning B: Planning and Design11339–348
48.
HopkinsL DBrillE DJrWongB, 1982, “Generating alternative solutions for dynamic programming models of water resources problems”Water Resources Research18782–790
49.
HosageC MGoodchildM F, 1986, “Discrete space location-allocation solutions from genetic algorithms”Annals of Operations Research635–46
50.
HwangC-LMasudA S M, 1979Multiple Objective Decision Making: Methods and Applications (Springer, Berlin)
51.
KeeneyR LRaiffaH, 1993Decisions with Multiple Objectives: Preferences and Value Tradeoffs(John Wiley, New York)
52.
KnowlesJ DCorneD W, 2000, “Approximating the nondominated front using the Pareto archived evolution strategy”Evolutionary Computation8149–172
53.
KozaJ RBennettF HIIIAndreDKeaneM A, 1999Genetic Programming III: Darwinian Invention and Problem Solving (Morgan Kaufmann, San Francisco, CA)
54.
KrzanowskiR MRaperJ, 1999, “Hybrid genetic algorithm for transmitter location in wireless networks”Computers, Environment and Urban Systems23359–382
55.
LaneWMcDonaldR, 1983, “Land suitability analysis, landfill siting”Journal of Urban Planning and Development10950–61
56.
LeungYLiGXuZ-B, 1998, “A genetic algorithm for the multiple destination routing problems”IEEE Transactions on Evolutionary Computation2150–161
57.
MalczewskiJ, 1992, “Site selection problem and a quasi-satisficing decision rule”Geographical Analysis24299–316
58.
MalczewskiJ, 1999, “Spatial multicriteria decision analysis”, in Spatial Multicriteria Decision Making and Analysis: A Geographic Information Sciences Approach Ed. ThillJ-CAshgate, Aldershot, Hants) pp 11–48
59.
MalczewskiJOgryczakW, 1995, “The multiple criteria location problem: 1. A generalized network model and the set of efficient solutions”Environment and Planning A271931–1960
60.
MalczewskiJPaznerMZaliwskaM, 1997, “Visualization of multicriteria location analysis using raster GIS: a case study”Cartography and Geography Information Systems2480–90
61.
MarcoNLanteriS, 2000, “A two-level parallelization strategy for genetic algorithms applied to optimum shape design”Parallel Computing26377–397
62.
MartinW NLienigJCohoonJ P, 1997, “Island (migration) models: evolutionary algorithms based on punctuated equilibria”, in Handbook of Evolutionary Computation Eds BäckTFogelD BMichalewiczZOxford University Press, New York) pp C6.3:1–16
63.
MichalewiczZ, 1996Genetic Algorithms + Data Structures. Evolution Programs (Springer, Berlin)
64.
MichalewiczZFogelD B, 2000How to Solve It: Modern Heuristics (Springer, Berlin)
65.
MiettinenK M, 1999Nonlinear Multiobjective Optimization (Kluwer Academic, Boston, MA)
66.
MinorS DJacobsT L, 1994, “Optimal land allocation for solid and hazardous waste landfill siting”Journal of Environmental Engineering1201095–1108
67.
ObayashiSSasakiDTakeguchiYHiroseN, 2000, “Multiobjective evolutionary computation for supersonic wing-shape optimization”IEEE Transactions on Evolutionary Computation4182–187
68.
OpenshawS, 1998, “Neural network, genetic, and fuzzy logic models of spatial interaction”Environment and Planning A301857–1872
69.
ParetoV, 1971Manual of Political Economy (Augustus M. Kelley, New York) translated from French edition of 1927 by SchwierAnn S., first published in 1896
70.
RechenbergI, 1965Cybernetic Solution Path of an Experimental Problem library translation 1122, Royal Aircraft Establishment, Farnborough, Hants
71.
RittelH W JWebberM M, 1973, “Dilemmas in a general theory of planning”Policy Sciences4155–169
72.
RitzelB JEheartJ WRanjithanS, 1994, “Using genetic algorithms to solve a multiple objective groundwater pollution containment problem”Water Resources Research301589–1603
73.
Rubenstein-MontanoBZandiI, 1999, “Application of a genetic algorithm to policy planning: the case of solid waste”Environment and Planning B: Planning and Design26893–907
74.
SaupeD, 1988, “Algorithms for random fractals”, in The Science of Fractal Images Eds PeitgenH-OSaupeDSpringer, New York) pp 71–136
75.
SawaragiYNakayamaHTaninoT, 1985Theory of Multiobjective Optimization (Academic Press, Orlando, FL)
76.
SrinivasNDebK, 1995, “Multiobjective optimization using nondominated sorting in genetic algorithms”Evolutionary Computation2221–248
77.
Van VeldhuizenD ALamontG B, 2000, “Multiobjective evolutionary algorithms: analyzing the state-of-the-art”Evolutionary Computation8125–147
78.
WentzE A, 2000, “A shape definition for geographic applications based on edge, elongation, and perforation”Geographical Analysis3295–112
79.
WongC KTongC OWongS C, 1999, “The development and calibration of a Lowry model with multiple market segments”Environment and Planning A311905–1918
80.
XiaoNBennettD AArmstrongM P, 2000, “Solving spatio-temporal optimization problems with genetic algorithms: a case study of a seed dispersal model”, in Proceedings of the 4th International Conference on Integrating GIS and Environmental Modeling: Problems, Prospects, and Needs for ResearchBanff, Canada, http://www.colorado.edu/research/banff/upload/389/
81.
ZitzlerEThieleL, 1999, “Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach”IEEE Transactions on Evolutionary Computation3257–271
82.
ZitzlerEDebKThieleL, 2000, “Comparison of multiobjective evolutionary algorithms: empirical results”Evolutionary Computation8173–195
83.
ZitzlerEDebKThieleLCoelloC A CCorneD (Eds), 2001Evolutionary Multi-criterion Optimization: Proceedings of the First International Conference (Springer, Berlin)
