Spatial Evolutionary Modelling

Order this book

Reviewed by
Steven M. Manson
Department of Geography, University of Minnesota, Minneapolis, USA.

This is an edited, multi-authored volume on evolutionary algorithms applied to spatial information science. This book lies at the confluence of two research streams. The first is evolutionary modelling, which has been a topic of interest across artificial intelligence, computational intelligence, and complexity theory. The late 1980s and early 1990s saw evolutionary modelling enter the scientific mainstream and become a relatively robust and mature field across disciplines. The second stream is geographic information science (GISc) and its technical manifestation in geographic information systems (GIS), information systems designed to store, manipulate, and visualise spatial data. GISc is a well-established field that dates back to the 1960s and before, if you consider its antecedents of cartography and early computer science. GIS as such is a mainstay application in many settings, aided in part by a move to the desktop computing environment and the growing availability of spatially referenced data. The newest cognate field of GISc is geocomputation, or computation in an explicitly spatial context, and this provides a natural berth for evolutionary modelling.

While the relative maturity of evolutionary modelling and GISc has been instrumental to bringing them together in this volume at this time, this work also answers earlier calls to apply evolutionary modelling in a spatial context. Professor Stan Openshaw, to whom the book is dedicated, and his research group at Leeds University first applied evolutionary modelling to spatial applications in the 1980s. He saw evolutionary modelling and allied fields such as fuzzy logic meeting the need for inductive, intuitive GIS techniques that support exploration of noisy, poorly structured problem domains marked by uncertainty (Openshaw 1992). His Geographical Analysis Machine was one of the first applications of evolutionary modelling in a spatial context, as it used genetic algorithms as an inductive search method in spatialpattern analysis (Openshaw 1988).

The authors divide the book into three parts. Part one introduces the conceptual underpinnings of evolutionary algorithms with respect to information processing and computational modelling. Part two examines evolutionary models in a spatial context, or spatial evolutionary models, and their conceptual and algorithmic corollaries within a GISc setting. Part three focuses on five case studies that highlight various research methodologies across application areas.

Part one introduces evolutionary modelling by examining its underlying concepts and introducing notation and terminology necessary for understanding the rest of the volume. While little here will be new to a practitioner of evolutionary modelling, it is a good introduction to the subject that examines the biological analogues to evolutionary modelling and then goes into the various branches of the field. It acknowledges that there is only tentative agreement on the nature and composition of the evolutionary modelling family tree. This part therefore examines classical genetic algorithms and various flavours of longstanding evolutionary algorithms and programs through to more recent genetic programming and hybrid approaches. This part of the book does a good job at looking at the problems that researchers encounter when programming evolutionary modelling systems, such as fitness determination and representation issues. It then conducts a walkthrough of a simple Java implementation of a genetic algorithm. In keeping with its focus on providing a solid introduction to evolutionary modelling, part one finishes with a bibliography that serves as a good entry point into a sprawling literature.

Part two of the book is where the volume moves into territory that may be new to its readers. It expands the basic rubric of evolutionary modelling to spatial evolutionary algorithms as a related but separate class of models designed to work with spatial information and concepts. The authors begin their discussion by noting that they are interested in spatial evolutionary modelling versus evolutionary models of space. They are therefore not interested in evolutionary models that act on spatial data, but instead on how a spatial focus can permeate evolutionary modelling. In essence, the authors want to create a new branch of the evolutionary modelling family tree. Evolutionary modelling is appropriate for geographic applications that have problem domains defined by complex differentiation of space in both absolute terms (e.g., locations within regions, in fields, or in networks) and in relative terms (e.g., relationships governed by proximity or connections to neighbours in space or networks). As shown by this volume, representing these problem domains and answering questions within them is a task to which evolutionary modelling appears well suited.

Part two is composed of two implicit sections, an overview and an example-driven exposition of evolutionary modelling. The overview begins with a discussion of the various meanings given to space, particularly with respect to the various ways in which theoretical definitions affect computational implementation. This segues into a discussion of translating general spatial concepts into the two most commonly occurring data structures in GIS: vector and raster. Spatial topological concepts such as connectivity, adjacency, and containment in connected graphs have come to define the "vector" data structure in GIS. The authors also consider mathematical field or lattice models that define the complementary "raster" data structure. The overview section concludes with a selective history of spatial evolutionary modelling across a number of disciplines.

The second section of part two provides the core of the book's argument. This section ultimately succeeds in making the argument, but technical issues hamper it in doing so. The section has three-step expository structure composed of increasingly detailed examination of an example application, structuring the locational decisions of a wireless communication system (i.e., where should wireless communication towers be placed so as to minimise the number of towers needed to provide coverage to a given spatial extent). This application exemplifies a general class of allocation problems in GISc and regional science, where an algorithm must match demand to supply in the most efficient manner possible subject to constraints. It is therefore a good example of how evolutionary modelling can be applied in a spatial context.

The first step examines the siting problem in general and provides the results for several sample applications in different countries and regions. The second step revisits the general outlines of the problem and delves into detail for several aspects, including chromosomes and evolutionary operators. It blends the notation of evolutionary modelling with more GISc-focused concepts such as map algebra (a system of algebraic notation applied to spatial data, after Tomlin 1985). The presentation here is interesting because it introduces notation in a piecemeal manner that sets the stage for step three, which examines an in-depth computational example. This section could have used a few more paragraphs on Map Algebra, which is a bedrock notion in GISc and has a number of potentially interesting ties to evolutionary modelling.

Again, part two succeeds overall but a few changes would improve it. In general, this section appears cobbled together from several different pieces of research. This is a common strategy in edited volumes, but here it leaves the reader wanting a cleaner, more consistent narrative for what is arguably the most important part of the book. Minor technical details exacerbate these discontinuities, such as where the authorial voice shifts between first and third person, leaving the reader to flip back and forth to pick up the train of argument. Also somewhat distracting is the artisanship of the figures, which is inconsistent with that presented elsewhere. A number of graphics have a confusing layout, for example, and several others employ conflicting typographic styles that ultimately distract the reader.

Part three is comprised of case studies that focus on research methodologies. The authors come from the private and public sectors and across disciplines ranging from geography and sociology to mathematics and computer science. This part presents these applications from the general to the specific. The first, by Catherine Dibble, furthers Stan Openshaw's calls for machine learning systems driven by evolutionary modelling by proposing to apply classifier-system frameworks to spatial data. Chris Brooks applies evolutionary modelling to designing patches with optimal spatial configurations in a landscape. Steven van Dijk, Dirk Thierens, and Mark de Berg focus on the long-standing analytical cartography problem of placing names (e.g. of rivers or cities) on maps as an example of using genetic algorithms to address large search spaces defined by combinatorial problems. Ângela Guimarães Pereira applies genetic algorithms to the multi-criteria evaluation problem of locating roads in a manner that minimises negative impacts and maximises positive ones. Finally, Daniel Delahaye examines how evolutionary models can be used to optimally partition airspace in order to minimise potential aircraft crossings and collisions.

The only potential shortcoming of this work - from the perspective of JASSS readers - is its instrumentalist focus. There is growing interest in using evolutionary modelling in ways that go beyond solving optimisation problems and towards using evolutionary models to understand complex processes such as human decision making or emergence in coupled human-environment systems. There are several places where the volume alludes to the potential for evolutionary modelling to deal with larger issues such as learning, knowledge discovery, and evolution, but it leaves these topics unexplored. Otherwise, apart from the problems noted above for part two, the book is technically well executed in a manner in keeping with the high quality of the series of which it is part, Oxford's Spatial Information Systems. The only drawback of the volume, and it is a minor one, is that it could use a glossary given its introductory focus.

In sum, the volume does a good job of demonstrating that established evolutionary modelling approaches can be applied in a spatially explicit manner. The strength of this volume lies in its bringing together concepts, methods, and applications. This book will be useful to GIS researchers but could also appeal to practitioners in the increasingly broad array of professions confronting spatial problems. In an educational setting, the volume could serve as a supplementary textbook for advanced courses in GISc and spatial modelling, with crossover potential for software engineering or computer science courses focused on applications.

References

OPENSHAW S. 1988. Building an automated modelling system to explore the universe of spatial interaction models. Geographical Analysis, 20:31-46.

OPENSHAW S. 1992. Some suggestions concerning the development of artificial intelligence tools for spatial modelling and analysis in GIS. Annals of Regional Science, 26:35-51.

TOMLIN C. D. 1985. Map Algebra. Harvard University Press, Cambridge, MA.

Return to Contents of this issue

(c) Copyright Journal of Artificial Societies and Social Simulation [2004]