Parallel genetic algorithms for optimising cellular automata models of natural complex phenomena: An application to debris flows
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)
- et al.
Simulation of the 1992 Tessina landslide by a cellular automata model and future hazard scenarios
International Journal of Applied Earth Observation and Geoinformation
(2000) - et al.
Cellular automata and lattice Boltzmann methods: a new approach to computational fluid dynamics and particle transport
Future Generation Computer Systems
(1999) - et al.
Simulation of the Parma River blockage by the Corniglio landslide (Northern Italy)
Geomorphology
(2000) - et al.
Revisiting the 1669 Etnean eruptive crisis using a cellular automata model and implications for volcanic hazard in the Catania area
Journal of Volcanology and Geothermal Research
(2003) - et al.
A cellular automata model for soil erosion by water
Physics and Chemistry of the Earth—Part B
(2001) - et al.
Simulating the Curti-Sarno debris flow through cellular automata: the model SCIDDICA (release S2)
Physics and Chemistry of the Earth
(2002) - et al.
First simulations of the Sarno debris flows through cellular automata modelling
Geomorphology
(2003) - et al.
Applying genetic algorithms for calibrating a hexagonal cellular automata model for the simulation of debris flows characterised by strong inertial effects
Geomorphology
(2005) - et al.
Evolving two-dimensional cellular automata to perform density classification: a report on work in progress
Parallel Computing
(2001) - et al.
Simulating lava flows by an improved cellular automata method
Computers & Geosciences
(1997)