Simulation of Complex Systems in GIS E-Book

Patrice Langlois

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 514

Veröffentlichungsjahr: 2013

Beschreibung

This book provides a comprehensive view of the field of geographical modeling by dividing the topic into three parts. The first part of the work establishes the foundations of geographical modeling through the use of more general concepts, including: structure, organization, system, geometries, topologies, metrics, material, and object. Finally, introduction of the concept of time leads to the theories of process and spatial interaction, which are fundamental in geography. The second part of the book tackles the use of computer tools for dynamic model building, which are the geographic cellular automata (GCA), and presents several models applied to various themes, such as urban growth, natural risks by flood simulations, as well as more political themes, such as the use of European funds, or the development of voting patterns in France. Finally, a general model of the geographic agents system (GAS) which can be used as a basis for the construction of a model-building platform for dynamic spatial models is presented.

Leseprobe

Table of Contents

General Introduction

PART 1. The Structure of the Geographic Space

Part 1. Introduction

Chapter 1. Structure and System Concepts

1.1. The notion of structure

1.2. The systemic paradigm

1.3. The notion of organization

Chapter 2. Space and Geometry

2.1. Different theories of space

2.2. Geometry and its data structures

2.3. “Neat” geometry and “fuzzy” geometry

Chapter 3. Topological Structures: How Objects are Organized in Spatial Systems

3.1. Topology

3.2. Metrics and topologies

3.3. Calculated topology, structural topology

3.4. Hierarchization

Chapter 4. Matter and Geographical Objects

4.1. Geographic matter

4.2. The notion of observation

4.3. The geographic object: Definitions and principles

Chapter 5. Time and Dynamics

5.1. Time

5.2. Temporalities

5.3. Events, processes

5.4. Decomposition of a complex process

5.5. An epistemic choice: reciprocal dependency between the complexity levels of a phenomenon

Chapter 6. Spatial Interaction

6.1. Presentation of the concept

6.2. Definition of macroscopic interaction

6.3. The four elementary (inter)actions

6.4. Microscopic interaction like a multigraph

6.5. Composition of successive interactions

6.6. The configurations and the trajectories of a simulation are categories

6.7. Intermediary level matrix representation

6.8. Examples of interactions

6.9. First definition of the notion of spatial system

Part 1. Conclusion: Stages of the Ontogenesis

PART 2. Modeling Through Cellular Automata

Chapter 7. Concept and Formalization of a CA

7.1. Cellular automata paradigm

7.2. Notion of finite-state automata

7.3. Mealy and Moore automata

7.4. A simple example of CA: the game of life

7.5. Different decompositions of the functions of a cell

7.6. Threshold automaton, window automaton

7.7. Micro level and Stochastic automaton

7.8. Macro level and deterministic automaton

7.9. General definition of a geographic cellular automaton

7.10. Different scheduling regimes of the internal tasks of the system

7.11. Ports, channels, encapsulation

7.12. Interaction

7.13. Space associated with a geographic cellular automaton

7.14. Topology and neighborhood operator of a GCA

7.15. The notion of cellular layer

7.16. Hierarchized GCA models

Chapter 8. Examples of Geographic Cellular Automaton Models

8.1. SpaCelle, multi-layer cellular automaton

8.2. Example: the evolution model of the Rouen agglomeration

8.3. RuiCells

8.4. GeoCells

Part 2. Conclusion

PART 3. A General Model of Geographic Agent Systems

Part 3. Introduction

Chapter 9. Theoretical Approach of an Integrated Simulation Platform

9.1. For an integrated platform of simulation

9.2. General specifications

Chapter 10. A Formal Ontology of Geographic Agent Systems

10.1. The conceptual framework

10.2. The notion of a geographic agent system

10.3. A generalization of the notion of process

10.4. The notion of a geographic agent

10.5. The formalization of the notion of organization

10.6. The formalization of behavior

10.7. Formalization of a general AOC model

10.8. The Schelling model example

Part 3. Conclusion

General Conclusion

First published 2011 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc. Adapted and updated from Simulation des systèmes complexes en géographie : fondements théoriques et applications published 2010 in France by Hermes Science/Lavoisier © LAVOISIER 2010

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd 27–37 St George's Road London SW19 4EU UK

www.iste.co.uk

John Wiley & Sons, Inc. 111 River Street Hoboken, NJ 07030 USA

www.wiley.com

© ISTE Ltd 2011

The rights of Patrice Langlois to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

Langlois, Patrice.    Simulation of complex systems in GIS / Patrice Langlois.     p. cm.    Includes bibliographical references and index.    ISBN 978-1-84821-223-7   1. Geographic information systems. 2. Geography--Simulation methods. I. Title.    G70.212.L267 2010    910.285--dc22

2010042667

British Library Cataloguing-in-Publication Data

General Introduction

In [DAU 03], André Dauphiné describes geography as the core of the complexity in human and social sciences. The information tools that permit us to enter the paradigm of geography’s complexity were brought forth by Tobler and Hagerstand through the use of cellular automatons. Then, multi-agent systems appeared near the end of the 1980s thanks to the combined evolution of artificial intelligence, object-oriented programming and distributed intelligence, which were later developed into numerous fields such as physics, biology and computer science [WEI 89], [BRI 01]. Thus, numerous works have contributed to applying these computing and theoretical tools specifically to geography. These studies continue to appear today, in the works of different teams such as the geosimulation group, RIKS, CASA, Milan’s politechnico and urban simulation (SIMBOGOTA) and city network studies from the Universities of Paris and Strasbourg in France. We will not explain these in detail.

Geography is essentially ingrained in space. The geographical map is its direct expression. If we are interested in complex processes, we must consider the interlocking organizational levels that are necessary to understand these phenomena. Modeling adds to the temporal and fundamental dimensions of the expression of dynamics. The multi-level representation in space forces us to address different temporality levels of processes in play.

This work will attempt to contribute to the challenge that is geographic complexity. Complexity is characterized as being a crossroads between physical and human sciences, by its intermediary position in overlapping levels of reality, which are spatial and temporal and finally, by its key position in the degrees of organization complexity, which is the position of human kind in both the living and mineral domains.

It took many years to accomplish this work in the area of geographic modeling. It is a product of reflection and fulfillment in the area of cartography, spatial analysis and geomatics. This study began at the beginning of the 1980s, and coincided with the arrival of micro-computers. This decade witnessed the construction of tools and concepts of solid and efficient representation of space. At the end of the 1990s and at the beginning of the 21st century, necessity passed to the next level: dynamic spatial simulation. It was imposed by the powerful level attained by computers, by the mature development of cartography software and by spatial analysis, through the development of complexity theories and associated simulation tools, since developed in other areas, such as physics.

Through this work, our goal is to share our knowledge in the area of modeling spatial dynamics, based on a systemic, individual-centered and distributed approach. This work is also the continuation of diverse contributions on this theme in works such as [GUE 08] and [AMB 06]. Here we will present a more personal analysis through our theoretic reflections and by means of a few of our realizations which were developed by our research team that are not isolated from the national and international abundance of such productions. We want this work to be an educational tool for students, geographic researchers, developers and computer scientists who wish to learn more about modeling in geography.

The mathematical aspect of certain developments should not alienate the literary reader as the formulae and mathematic notations are not necessary for its general comprehension and may be disregarded during a qualitative reading. These developments are generally associated with text explaining them in today’s terms. The formal aspect must therefore enable the reader to learn about this area and to deal with these notions. They can seem repellent at times but we need to overcome that perception if we wish to numerically test or program these methods or models. Nevertheless, many of these formalisms deal with very simple concepts, and in this work, we have made a constant effort to accompany these formalisms with a simple explanation and to give meaning to the symbols and notations in the text.

Starting with the most general concepts of structure, organization and system, we will firstly approach the fundamental notion of space. The richness of this concept is shown through different formalizations that lead us to geometries, topologies and metrics defined through space. Then, we approach the concepts of matter and object to finally introduce time. This allows us to approach the notions of processes and interaction that are fundamental in dynamic geographic modeling. After this section, presenting the foundations of geographic space modeling we will work with the computing tools of dynamic modeling, which are the geographic cellular automatons (GCA) which enable us to have a general model of a GCA. Then, we generalize it to construct a general system of geographic agents (SGA) model, based on a formal ontology constructed on the Agent-Organization-Behavior triptych where the geographic object appears as a dual entity between the individual and the group. This formal ontology is mathematically formalized as it lets us elaborate a construction totally independent of all technological constraints and provides a rigorous theoretical framework. Thus, we can think of geographic objects according to a more realistic approach, even if it remains simplified. The mathematic formalization enables us to think of continuum or infinity without being preoccupied by the limitations of a computer in which everything must be explicit1, enumerated and finished. We need a theoretic and suppler framework to formalize this construction.

Firstly, the set theory and the logic of predicates currently form an elementary basis which is recognized for all mathematical formalizations. We have come a long way from the beginning of the set theory of entities which was initiated by Cantor at the end of the 19th century, a time when fundamental paradoxes shook its axiomatic structure. The set theory has reached its maturity while being conscious of its limits, for example, knowing how to distinguish between what is a set and what is not (which we will call a “family” or a “collection”). There is no formal definition of the notion of “set”. It is a primary definition of the theory. Nevertheless, the family of all sets is not a set in itself, as a set must be clearly defined, either by the thorough and non superfluous list of its elements, (it is therefore defined “in extension”) or by a property characteristic of its elements, (it is then defined “in comprehension”). Another essential rule exists so that the theory does not contradict itself. This has to do with the relation of belonging: a set cannot belong to itself. However, the notion of sub-sets gives birth to the relation of inclusion, which is a relation of order defined on the set P(E) of the parts of a set E.

The inclusion relation is reflexive, as opposed to belonging, which is antireflexive. Thus, in the set theory, a set contains itself but does not belong to itself. With such precautions, Russel’s paradox no longer exists. In fact, this paradox rested upon a particular set, formed by all the sets which do not contain themselves. This paradox resulted from the fact that this set could either contain or not contain itself. These improvements are linked with others in Zermelo-Fraenkel’s axiomatic. The latter confers great weight to this theory. Even if it is not the only one at the basis of a set theory, it is widely used today. It will eventually be accompanied by other complementary axioms, such as the choice axiom, and the continuum hypothesis.

A few other set theories have been formed, such as the theory of types (Whitehead, Russell) and the theory of classes (von Neumann, Godel). In spite of their differences, these theories now appear to be converging translations of the same mathematical reality. Other tentatives of axiomatization were developed in different directions and some of those were formalized. Such is the case for mereology which is a more logical theory formalized by the logician Stanisław Leśniewski (1886–1939). This theory does not form a more fecund advance for our work than the “standard” set theory. For example, one of the main principles of the complexity paradigm is that the whole is more than the sum of its parts. In the set theory, like in mereology, this affirmation is false. The definition of a complex system rests upon a richer concept than a simple set formed of elements (and of parts).

We propose to formulate this enrichment, which is not contradictory by the use of the set theory. This ontological construction is not limited to the single use of the set theory. The whole structure of algebra, geometry, topology and analysis, whose coherence and language rest upon the set theory, will be useful for us at many levels. Nevertheless, we do not want to elaborate a mathematical theory formulated by a series of theorems and demonstrations. We also do not want to elaborate on new axioms. We will only use the mathematical language to define entities of our ontology and to show its coherence. Thus, the level of mathematical knowledge used remains elementary.

In order to define this ontological construction step in a geographic realm, we will start from nothingness with the localizations constituted by what is left of the world, keeping only localizations and coordinates. This nothingness is formed by the space2 of geometry which is void of all matter and content. It allows for the construction of geometric forms and permits them to be put in relation, through topology, in order to construct more complex abstract objects. In the meantime, the profound essence of objects only appears with the introduction of the concept of matter and energy. How can matter be formalized in this geometric space? Does a point, a line or a surface still exist when space becomes material? We will finally examine how the acknowledgement of time permits us to construct facts and behaviors. For example, it permits the birth, the development and the death of either physical, living, social or imaginary beings. It also enables us to add depth of history and incertitude of the future to the diversity of spatial reality. Thus, it seems that the physical triptych of space-time-matter is the preliminary conceptual pedestal on which our ontological construction Agent-Organization-Behavior (AOB) is based. This confirms that the laws of physics do not only apply to life sciences of man and society. If each level of reality possesses its own laws, they keep their vertical coherence, which is to say that each level cannot contradict laws acquired at lower levels.

The concepts of agent and organization are at the heart of geographic object construction. They define a geographic object dually, which consists of a more or less abstract membrane, the external side of which is turned towards the exterior world with which it acts. This realm is formed on the one hand by a diverse part of agent-objects of the same level, more or less evolved but nevertheless of the same general conception, and on the other hand by an englobing system into which all of these objects are integrated. It also consists of an internal side which presents the object as an organization turned towards the isolated depth of its interior for which its parts are still agent-objects forming a system. These two sides express the fundamental interaction which is the object’s essence that is active and evolutive (some would say “inactive”). These qualities permit a co-construction (or even a co-evolution) from both the collective exterior and interior universes. If the AOB ontology was initially inspired by Jacques Ferber’s AGR work (Agent-Group-Role), it defers from the duality of agent and organization which integrates this auto-reference and its internal and external environments which derive from it. Geography’s main interest with respect to this structure derives from the fact that it expresses a systematic, multi-level vision. Furthermore, it permits us to identify the exterior and interior limits of the model. Thus, we can often identify three levels of modeling (but this number is not limited, i.e. macro, meso and micro).

The macro level is limited by the global system’s envelope (which corresponds to the entire model) and contains the highest level of organization. The main level of the system’s objects is constructed in this environment (the one that contains objects we study) which are at the meso-level. These objects can themselves be structured by terminal objects so they cannot be deteriorated by more elementary objects. This is what we call the “particular” or “micro” level. If the problem persists, we can always add more levels. This representation (see Figure I.1) is evident to an individual observer (or an individual observed by the modeler), who can see at its meso-level the grouping of the other individuals of this level, who can internally “feel” the grouping of these micro-level internal components and who are also in relation to this system in which it evolves (at the macro-level).

Moreover, these two formalization steps that we use, mathematically and informatically, are not antagonistic but complementary and can be mutually enriched. Our method will thus be presented more often as an object or as a concept in the form of a description, as is customary in geography. Then we will mathematically formalize it, and/or see how it can be translated in a conceptual, structural or algorithmic computer science formalization.

Figure I.1.Relations between the individual, collective, internal and external

Notations used

We constantly use two formalization methods: mathematic and algorithmic. These two methods conform with slightly different conventions so it is therefore a good idea to know the difference, depending on the context. The mathematic language generally uses one symbol (typically a letter), sometimes accompanied by an index to represent an entity as either a variable, an element, a set, a function, an unknown, etc. When we associate two letters which represent numbers, this often signifies that we multiply them. On the contrary, in computer science, as the number of symbols in a program or in an algorithm can be large, we represent an entity by a rather explicit name, by using many letters. The same formula or series of calculations can be written in two manners, and the same symbols can have different significations:

– In mathematical language, the symbols are written in italics to differentiate them from common language. The multiplication operation is implied (or more rarely indicated by a point). The expression of equality a=b indicates a mathematical equality, which means that a and b are two ways of signifying the same quantity or the same element of a set. We use specific symbols for operations (summation, integration, fraction line, square root, etc.).

So,

the number is y equal to the y minimum added to the product of j by p numbers

indicates that the number x bar (showing an average in statistics), is equal to the opposite of n multiplied by the sums of xi for the index i varying from 1 to n, which makes us divide the sum of xi by n:

– In algorithmic language, we use the “typewriter” font where we often use a syntactic approach close to the Pascal language. The multiplication is then represented by a star. The symbol of equality “=” does not have the same sense as it does in mathematics. Here it is a logical operation that gives the “true” result if the left and right members represent the same quantity or quality, otherwise giving a “false” result. We must not confuse the symbol of equality with the symbol of allocation, noted in the Pascal language “:=” or sometimes in the algorithmic language, by an arrow “←”. The expressions “a := b+c” or “a ← b + c” mean that we read the values contained in the memory files named b and c, that we use the b+c addition and that we write (or store) the result in the “a” memory file. In algorithmics, we do not use special symbols (Greek, etc.), we only use keyboard symbols. The entities are often named by chains of many characters. The point represents a separator between a complex entity (an object) and a component of this entity (an attribute, property or method).

For example, the two following formulae could be written as:

where “yMin” and “PasY” are fields (attributes) of the “DTM” object. We can also have an algorithmic style of writing, like in the following example that calculates the average of values contained in the X chart.

AveX :=0;for i :=1 to n do AveX := AveX + X[i]end; AveX := AveX/n

1 Contrary to mathematics that are based on an implicit syntactic construction (a definition once stated is assumed to be known afterwards) and on the implicit contents. For example, we only know out of the real numbers those which can be formulated or made explicit, but there is an infinity of numbers that will never be made explicit. Many mathematical objects are implicitely definite by theorems of existence, but we either don’t know or cannot always determine them effectively.

2 This term is used in a voluntarily ambiguous manner to evoke geography’s disciplinary area, but also to indicate that we are situated in a physical space, which is mathematically formalized.

PART 1The Structure of the Geographic Space

Geometry and movement are the two inseparable problems in geographic theory. Regardless of the movement, they leave their mark on the terrestrial surface. They produce a geometry, then the geometry produces movements: circulations in states are created by national frontiers, and in return they contribute to create these frontiers.

William Bunge

Part 1Introduction

The concept of geographic space has been used by geographers and spatial economists since the end of the 19th century, by such people as von Thunen, Weber, Losch, Christaller and many others. It is mostly done through network studies, taking into account locations, distances, and terrestrial surfaces. There are also “functional distances” which are no longer expressed in kilometers, but in transport cost, in travel time, in energy spent, etc. Surfaces are measured not only in hectares or in square kilometers but also in population size, density and revenues. Thus, geographic space appears as though it has been constituted by all of its “geographic matter”, (natural or constructed, human or social). It is a space of diverse activities that consumes energy and thus possesses an economic dimension. Then, there is a sort of generalized or abstract roughness that expresses the degree of difficulty to deal with the fundamentally heterogeneous space. For example, Jacques Levy speaks of different pedestrianized “metrics” to express this notion. This has led to different types of cartographic representations where geometric space is deformed in order to better visualize this spatial roughness through anamorphosic methods (Tobler, Charlton, Cauvin–Raymond, Langlois, etc.).

Also, the concept of space is not totally foreign to the concept of geographic objects, which has been used for a long time in human geography. We will elaborate on the precise and concrete definition of this notion of geographic object later on in geomatics. In addition, the notion of objects is also a central concept in computer science, where object–oriented languages have an important place, and are well adapted to multi–agent modeling. In the context of geographic phenomena modeling, the use of the term “object” may cause confusion. Nevertheless, we use it here not to refer to oriented–object programming, but in a more general, systemic and auto–referential “physics” sense. We will demonstrate how the object is the central concept through which the first concepts of space, time and energy–matter were structured. It is also the interface between the observation and modeling levels of reality.

The object is not only defined as its inanimate material element but covers the whole disciplinary field, as we believe that in the field of computer modeling the same elementary principles of structuring and function are applicable, from a pebble to a social group. The important differences between objects come from the differences in the levels of complexity and not because they come from the essence or from fundamental epistemic differences, in particular between inanimate and living things. We must then be able to formalize and program them with the same methods and modeling language, on the same platform of computer modeling.

If we were to reflect upon the concept of a modeling platform, we would need a clear conceptual and mathematic formalization of the concepts of space, spatial structure, objects and spatial systems. We could then elaborate on the notions of dynamics, process and behavior, which gives these objects an “agent” status.

Chapter 1Structure and System Concepts

1.1. The notion of structure

According to Raymond Boudon, “structure appears as indispensable in all human sciences, judging by the increase of its employment, and it being difficult to pinpoint”. Amongst the definitions contained in the Universalis Encyclopedia, there are four concerning our subject:

– complex organization (administrative structure);

– the way in which things are organized to form a set (abstract or concrete);

– in philosophy the stable set of interdependent elements, such that each one is dependent on its relation with others;

– in mathematics, a set composed of certain relations or laws of composition.

Let us observe at which point these definitions converge towards our subject. The first reintroduces complexity; the second brings us back to the notion of an organized set; the third, in its simplified version, refers to the structuralist theories (Saussure, Merleau–Ponty, Piaget, Lévi–Strauss, etc.) but does not contradict the way in which mathematics formalizes it through the fourth definition. Furthermore, it corresponds to a contemporary trend consisting of defining an object, not by its intrinsic properties, but by its connections with others. Its function is defined because it consumes and produces on the outside and not by its content or its internal mechanism of functioning. In particular, it is the systemic paradigm of the “black box”.

1.1.1. In mathematics and in physics

1.1.1.1. The mathematical structure of group and physics invariants