Elsevier

Computers & Geosciences

Volume 32, Issue 7, August 2006, Pages 861-875
Computers & Geosciences

Parallel genetic algorithms for optimising cellular automata models of natural complex phenomena: An application to debris flows

https://doi.org/10.1016/j.cageo.2005.10.027Get rights and content

Abstract

Cellular automata models of natural complex phenomena may depend on a set of parameters which can significantly influence the global dynamics of the simulated events. In order to reliably apply such models for predictive purposes, their parameters have to be estimated with the greatest possible accuracy. However, no standardised optimisation techniques exist in this specific research field. Genetic Algorithms (GAs) offer a possible solution: they are parallel algorithms, and can be easily implemented to exploit the simultaneous use of multiple CPUs, thereby greatly reducing the execution time.

An application of a parallel GA to the optimisation of a cellular automata model for the simulation of debris flows characterised by strong inertial effects is presented. The May 1998, Curti-Sarno (Italy) debris flow has been selected as a case study for the optimisation of the model. Theoretical considerations on the dynamics of the adopted GA are discussed, with reference to two different fitness functions applied to an idealised case study.

Results demonstrated the usefulness of the approach, in terms of both computing time and quality of performed simulations. Moreover, experiments on the idealised case study pointed out that the simplest fitness function (only based on the comparison of affected areas) could conveniently be adopted for calibration purposes.

Introduction

In the last decades, several approaches for modelling natural complex phenomena have been proposed in the literature. Among these, Cellular Automata (CA) represent an interesting possible solution when the phenomena to be simulated evolve on the basis of local interactions of their constituent parts.

CA are dynamical systems, discrete in space and time. They can be thought as a lattice of cells, each one embedding an identical finite automaton, interacting only with a small set of neighbouring cells. The state of each finite automaton is changed by applying the transition function, which defines local rules of evolution for the cell. The CA overall global dynamics emerges from the simultaneous application of the local rules to each cell. Accordingly, basic laws of physics have to be translated into a-centric terms (Toffoli, 1984; Wolfram, 1986, Wolfram, 2002), i.e. into local rules, properly derived by “splitting” the whole natural process into a series of local interactions (elementary processes). In the specific case of modelling macroscopic natural events, Di Gregorio and Serra (1999) developed a CA-based empirical approach, successfully applied to numerous complex non-linear phenomena, such as lava flows and debris flows.

In general, non-linear dynamical systems may generate very different behaviours as a consequence of small changes in their initial conditions (i.e. state and/or values of parameters). Such characteristic is known as “butterfly effect” (Lorenz, 1963), stating that “the flapping of wings of a butterfly produces tiny changes in the atmosphere's status locally, which over the course of time may cause a dramatic divergence from what it would have been elsewhere, so that even a tornado can occur”.

Even discrete non-linear dynamical systems, such as CA, may heavily depend on initial conditions (Wolfram, 2002). Furthermore, according to Di Gregorio and Serra's approach, CA usually depend on many parameters (which not always correspond to actual physical ones, nor do their values strictly need to have a physical meaning). Thus, in order to reliably apply such models for predictive purposes, both CA initial state and parameters (which together define the initial conditions of the system) have to be provided with the highest accuracy. Precision of initial state is restrained by map detail and scale, while parameters have to be estimated, with the greatest possible accuracy, through a proper calibration phase.

In the field of CA-modelling of natural phenomena, no standardised optimisation techniques do exist, and the calibration is often performed “manually”. An alternative solution is offered by Genetic Algorithms (GAs), which are general-purpose search algorithms inspired from genetics and natural selection (Holland, 1992). In many practical applications, sequential GAs demonstrated to be able to find “good solutions” in a reasonable amount of time. Nevertheless, they may also take a long time in others: in such cases, parallel computing can profitably be employed to strongly speed up the GAs execution (Cantù-Paz, 2000).

This paper describes an application of Parallel Genetic Algorithms (PGAs) to the optimisation of the CA model SCIDDICA S4b for the simulation of rapid debris flows (Section 2) by considering the Curti-Sarno (Italy) landslide of May 1998 (Section 3). A Master-Slave GA is applied for model optimisation (Section 4). A study of GA dynamics, with reference to two different fitness functions applied to an idealised case study, is also discussed (Section 5). Final comments are presented (Section 6).

Section snippets

Modelling debris flows characterised by strong inertial effects through cellular automata: the model SCIDDICA S4b

In the last decades, several CA (or CA-like) applications to flow-type phenomena have been proposed. Among the most recent examples are: Smith (1991), Murray and Paola, 1994, Murray and Paola, 1997, Chopard and Masselot (1999), D’Ambrosio et al. (2001) for hydraulic soil erosion; Barca et al., 1986, Barca et al., 1987, Crisci et al., 1998, Crisci et al., 1999, Crisci et al., 2003a and Miyamoto and Sasaki (1997) for lava flows; Crisci et al. (2003b) for pyroclastic flows; Sassa (1988), Segre and

The case study: the May 1998 Curti debris flow

On May 5–6, 1998, hundreds of soil slip-debris flows were triggered by heavy rains in Campania, Southern Italy, mostly on the slopes of the Pizzo d’Alvano Massif (Del Prete et al., 1998). In the study area, a regolith mainly derived from pyroclastic fall deposits of the Somma–Vesuvius volcanic complex (Arnò et al., 1987) overlies the Mesozoic carbonate bedrock (Ippolito et al., 1973; Bonardi et al., 1988). The thickness of the regolith, and its geotechnical properties, widely vary from site to

Optimising SCIDDICA S4b through parallel genetic algorithms: performance and results

Genetic Algorithms (Holland, 1992) are general-purpose iterative search algorithms inspired by natural selection and genetics. They were applied, with good results, in many different fields: for the solution of difficult combinatorial problems (Poon and Parks, 1992); in the study of the interaction between evolution and learning (Hinton and Nowlan, 1987); in evolutionary robotics (Nolfi and Floreano, 2000; Nolfi and Marocco, 2001). Recently, GAs have also been used for improving the performance

Theoretical considerations on the GA dynamics: an idealised case study

In the GA experiments that have been performed, individuals characterised by relatively high fitness rapidly evolved, even if the initial population was randomly generated and the search space was quite large (cf. Fig. 6). This behaviour is, at least partially, due to the presence of morphological constraints along the flow path. In fact, by analysing simulations of several individuals (which define alternative sets of S4b parameters) evolved in the first steps, similar behaviours were observed

Discussion

The adoption of PGAs permitted a more efficient optimisation of the CA model SCIDDICA S4b for simulating fast debris flows. In fact, with respect to previous attempts of GAs calibration performed in a sequential computing environment (Iovine et al, 2005), a greater number of tests could be performed in reasonable times, shortening the execution by a factor of 15. Speed-up measurements demonstrated the linear scalability of PGAPack on the considered Beowulf cluster, which combined constitute an

Acknowledgements

The family “Sx” of SCIDDICA was developed thanks to specific funding of Regione Campania. The authors are grateful to all the collaborators which participated in the development of the model, and particularly to Salvatore “Toti” Di Gregorio which greatly contributed in the development of the model. L. Merenda and G. Nardi coordinated the project, V. Lupiano drafted the figures of this paper.

Finally, authors very appreciated suggestions received by Prof. Marco Tomassini and by another anonymous

References (59)

  • S. Nolfi et al.

    Evolving robots able to Integrate sensory-motor information over time

    Theory in Biosciences

    (2001)
  • T. Toffoli

    Cellular automata as an alternative to (rather than an approximation of) differential equations in modeling physics

    Physica

    (1984)
  • E. Alba et al.

    Parallelism and evolutionary algorithms

    IEEE Transactions on Evolutionary Computation

    (2002)
  • V. Arnò et al.

    Eruptive history

  • D. Barca et al.

    A cellular space model for flow type landslides

  • D. Barca et al.

    Flow-type landslide modelling by cellular automata

  • G. Bonardi et al.

    Carta geologica dell’Appennino meridionale in scala 1:250000 (Geological map of Southern Apennines in scale 1:250000)

    Memorie Società Geologica Italiana

    (1988)
  • E. Cantù-Paz

    Efficient and Accurate Parallel Genetic Algorithms

    (2000)
  • Crisci, G.M., Di Gregorio, S., Rongo, R., Spataro, W., 1998. Lava area hazard determination for the town of Nicolosi...
  • Crisci, G.M., Di Francia, A., Di Gregorio, S., Rongo, R., Spataro, W., 1999. An improved cellular automaton model for...
  • G.M. Crisci et al.

    A cellular automata model for simulating pyroclastic flows and first application to the 1991 Pinatubo eruption

  • Cruden, D.M., Varnes, D.J., 1996. Landslide types and processes. In: Turner, A.K., Schuster, R.L. (Eds.), Landslides:...
  • D. D’Ambrosio et al.

    Modelling surface flows for macroscopic phenomena by cellular automata: an application to debris flows

  • D. D’Ambrosio et al.

    Simulating debris flows through a hexagonal cellular automata model: SCIDDICA S3hex

    Natural Hazards and Earth System Sciences

    (2003)
  • De Jong, K.A., 1975. An analysis of the behavior of a class of genetic adaptive systems. Ph.D. Dissertation, Department...
  • M. Del Prete et al.

    Preliminary report on the landslides of 5 May 1998, Campania, Southern Italy

    Bulletin of Engineering Geology and the Environment

    (1998)
  • S. Di Gregorio et al.

    An empirical method for modelling and simulating some complex macroscopic phenomena by cellular automata

    Future Generation Computer Systems

    (1999)
  • S. Di Gregorio et al.

    Combining cellular automata and genetic search in complex environmental modelling

  • S. Di Gregorio et al.

    Environmental applications of genetic algorithms

  • Cited by (0)

    View full text