A hybrid parallel cellular automata model for urban growth simulation over GPU/CPU heterogeneous architectures

As an important spatiotemporal simulation approach and an effective tool for developing and examining spatial optimization strategies (e.g., land allocation and planning), geospatial cellular automata (CA) models often require multiple data layers and consist of complicated algorithms in order to deal with the complex dynamic processes of interest and the intricate relationships and interactions between the processes and their driving factors. Also, massive amount of data may be used in CA simulations as high-resolution geospatial and non-spatial data are widely available. Thus, geospatial CA models can be both computationally intensive and data intensive, demanding extensive length of computing time and vast memory space. Based on a hybrid parallelism that combines processes with discrete memory and threads with global memory, we developed a parallel geospatial CA model for urban growth simulation over the heterogeneous computer architecture composed of multiple central processing units (CPUs) and graphics processing units (GPUs). Experiments with the datasets of California showed that the overall computing time for a 50-year simulation dropped from 13,647 seconds on a single CPU to 32 seconds using 64 GPU/CPU nodes. We conclude that the hybrid parallelism of geospatial CA over the emerging heterogeneous computer architectures provides scalable solutions to enabling complex simulations and optimizations with massive amount of data that were previously infeasible, sometimes impossible, using individual computing approaches.     

A high-performance cellular automata model for urban simulation based on vectorization and parallel computing technology

Cellular automata (CA) models can simulate complex urban systems through simple rules and have become important tools for studying the spatio-temporal evolution of urban land use. However, the multiple and large-volume data layers, massive geospatial processing and complicated algorithms for automatic calibration in the urban CA models require a high level of computational capability. Unfortunately, the limited performance of sequential computation on a single computing unit (i.e. a central processing unit (CPU) or a graphics processing unit (GPU)) and the high cost of parallel design and programming make it difficult to establish a high-performance urban CA model. As a result of its powerful computational ability and scalability, the vectorization paradigm is becoming increasingly important and has received wide attention with regard to this kind of computational problem. This paper presents a high-performance CA model using vectorization and parallel computing technology for the computation-intensive and data-intensive geospatial processing in urban simulation. To transfer the original algorithm to a vectorized algorithm, we define the neighborhood set of the cell space and improve the operation paradigm of neighborhood computation, transition probability calculation, and cell state transition. The experiments undertaken in this study demonstrate that the vectorized algorithm can greatly reduce the computation time, especially in the environment of a vector programming language, and it is possible to parallelize the algorithm as the data volume increases. The execution time for the simulation of 5-m resolution and 3 × 3 neighborhood decreased from 38,220.43 s to 803.36 s with the vectorized algorithm and was further shortened to 476.54 s by dividing the domain into four computing units. The experiments also indicated that the computational efficiency of the vectorized algorithm is closely related to the neighborhood size and configuration, as well as the shape of the research domain. We can conclude that the combination of vectorization and parallel computing technology can provide scalable solutions to significantly improve the applicability of urban CA.     

Parallel cellular automata for large-scale urban simulation using load-balancing techniques

Cellular automata (CA), which are a kind of bottom-up approaches, can be used to simulate urban dynamics and land use changes effectively. Urban simulation usually involves a large set of GIS data in terms of the extent of the study area and the number of spatial factors. The computation capability becomes a bottleneck of implementing CA for simulating large regions. Parallel computing techniques can be applied to CA for solving this kind of hard computation problem. This paper demonstrates that the performance of large-scale urban simulation can be significantly improved by using parallel computation techniques. The proposed urban CA is implemented in a parallel framework that runs on a cluster of PCs. A large region usually consists of heterogeneous or polarized development patterns. This study proposes a line-scanning method of load balance to reduce waiting time between parallel processors. This proposed method has been tested in a fast-growing region, the Pearl River Delta. The experiments indicate that parallel computation techniques with load balance can significantly improve the applicability of CA for simulating the urban development in this large complex region.     

基于遗传算法自动获取CA模型的参数

本文提出了基于遗传算法来寻找CA模型最佳参数的方法。CA被越来越多地应用于城市和土地利用等复杂系统的动态模拟。CA模型中变量的参数值对模拟结果有非常重要的影响。如何获取理想的参数值是模型的关键。传统的逻辑回归模型运算简单,常常用来获取模型的参数值,要求解释变量间线性无关,所以获取的城市CA模型参数具有一定的局限性。遗传算法在参数优化组合、快速搜索参数值方面有很大的优势。本文利用遗传算法来自动获取优化的CA模型参数值,并获得了纠正后的CA模型。将该模型应用于东莞1988~2004年的城市发展的模拟中,得到了较好的效果。研究结果表明,遗传算法可以有效地自动获取CA模型的参数,其模拟的结果要比传统的逻辑回归校正的CA模型模拟精度高。     

A partitioned and asynchronous cellular automata model for urban growth simulation

Cellular automata (CA) models are used to analyze and simulate the global phenomenon of urban growth. However, these models are characterized by ignoring spatially heterogeneous transition rules and asynchronous evolving rates, which make it difficult to improve urban growth simulations. In this paper, a partitioned and asynchronous cellular automata (PACA) model was developed by implementing the spatial heterogeneity of both transition rules and evolving rates in urban growth simulations. After dividing the study area into several subregions by k-means and knn-cluster algorithms, a C5.0 decision tree algorithm was employed to identify the transition rules in each subregion. The evolving rates for cells in each regularly divided grid were calculated by the rate of changed cells. The proposed PACA model was implemented to simulate urban growth in Wuhan, a large city in central China. The results showed that PACA performed better than traditional CA models in both a cell-to-cell accuracy assessment and a shape dimension accuracy assessment. Figure of merit of PACA is 0.368 in this research, which is significantly higher than that of partitioned CA (0.327) and traditional CA (0.247). As for the shape dimension accuracy, PACA has a fractal dimension of 1.542, which is the closest to that of the actual land use (1.535). However, fractal dimension of traditional CA (1.548) is closer to that of the actual land use than that of partitioned CA (1.285). It indicates that partitioned transition rules play an important role in the cell-to-cell accuracy of CA models, whereas the combination of partitioned transition rules and asynchronous evolving rates results in improved cell-to-cell accuracy and shape dimension accuracy. Thus, implementing partitioned transition rules and asynchronous evolving rates yields better CA model performance in urban growth simulations due to its accordance with actual urban growth processes.     

A travel time-based variable grid approach for an activity-based cellular automata model

Urban growth and population growth are used in numerous models to determine their potential impacts on both the natural and the socio-economic systems. Cellular automata (CA) land-use models became popular for urban growth modelling since they predict spatial interactions between different land uses in an explicit and straightforward manner. A common deficiency of land-use models is that they only deal with abstract categories, while in reality, several activities are often hosted at one location (e.g. population, employment, agricultural yield, nature…). Recently, a multiple activity-based variable grid CA model was proposed to represent several urban activities (population and economic activities) within single model cells. The distance-decay influence rules of the model included both short- and long-distance interactions, but all distances between cells were simply Euclidean distances. The geometry of the real transportation system, as well as its interrelations with the evolving activities, were therefore not taken into account. To improve this particular model, we make the influence rules functions of time travelled on the transportation system. Specifically, the new algorithm computes and stores all travel times needed for the variable grid CA. This approach provides fast run times, and it has a higher resolution and more easily modified parameters than the alternative approach of coupling the activity-based CA model to an external transportation model. This paper presents results from one Euclidean scenario and four different transport network scenarios to show the effects on land-use and activity change in an application to Belgium. The approach can add value to urban scenario analysis and the development of transport- and activity-related spatial indicators, and constitutes a general improvement of the activity-based CA model.     

Using a maximum entropy model to optimize the stochastic component of urban cellular automata models

ABSTRACT

The stochastic perturbation of urban cellular automata (CA) model is difficult to fine-tune and does not take the constraint of known factors into account when using a stochastic variable, and the simulation results can be quite different when using the Monte Carlo method, reducing the accuracy of the simulated results. Therefore, in this paper, we optimize the stochastic component of an urban CA model by the use of a maximum entropy model to differentially control the intensity of the stochastic perturbation in the spatial domain. We use the kappa coefficient, figure of merit, and landscape metrics to evaluate the accuracy of the simulated results. Through the experimental results obtained for Wuhan, China, the effectiveness of the optimization is proved. The results show that, after the optimization, the kappa coefficient and figure of merit of the simulated results are significantly improved when using the stochastic variable, slightly improved when using Monte Carlo methods. The landscape metrics for the simulated results and actual data are much closer when using the stochastic variable, and slightly closer when using the Monte Carlo method, but the difference between the simulated results is narrowed, reflecting the fact that the results are more reliable.     

基于局部化转换规则的元胞自动机土地利用模型

传统土地利用元胞自动机(Cellular automata,CA)模型基于空间同质性假设,使用全局性模型建立元胞转换规则,忽略了土地利用变化驱动因素的驱动作用在空间上的变化。以美国佛罗里达州的橙县(Orange County)2003-2009年土地利用变化为例,提出了基于局部化转化规则的CA土地利用模型,其中元胞的土地利用类型适宜性由地理加权多项logit模型(Geographically weighted multinomial logit,GWML)获得。结果表明:GWML模型较传统全局性多项logit(Multinomial logit,MNL)模型有更高的数据解释能力。基于GWML模型的土地利用CA模型能反映局部土地利用变化模式,因而较基于MNL模型的CA模型具有更高的模拟精度。所得结论对未来国内地区的研究有借鉴意义。     

Calibrating cellular automata based on landscape metrics by using genetic algorithms

Landscape metrics have been widely used to characterize geographical patterns which are important for many geographical and ecological analyses. Cellular automata (CA) are attractive for simulating settlement development, landscape evolution, urban dynamics, and land-use changes. Although various methods have been developed to calibrate CA, landscape metrics have not been explicitly used to ensure the simulated pattern best fitted to the actual one. This article presents a pattern-calibrated method which is based on a number of landscape metrics for implementing CA by using genetic algorithms (GAs). A Pattern-calibrated GA–CA is proposed by incorporating percentage of landscape (PLAND), patch metric (LPI), and landscape division (D) into the fitness function of GA. The sensitivity analysis can allow the users to explore various combinations of weights and examine their effects. The comparison between Logistic- CA, Cell-calibrated GA–CA, and Pattern-calibrated GA–CA indicates that the last method can yield the best results for calibrating CA, according to both the training and validation data. For example, Logistic-CA has the average simulation error of 27.7%, but Pattern-calibrated GA–CA (the proposed method) can reduce this error to only 7.2% by using the training data set in 2003. The validation is further carried out by using new validation data in 2008 and additional landscape metrics (e.g., Landscape shape index, edge density, and aggregation index) which have not been incorporated for calibrating CA models. The comparison shows that this pattern-calibrated CA has better performance than the other two conventional models.     

The inclusion of differentially assessed lands in urban growth model calibration: a comparison of two approaches using SLEUTH

This research sought to understand the role that differentially assessed lands (lands in the United States given tax breaks in return for their guarantee to remain in agriculture) play in influencing urban growth. Our method was to calibrate the SLEUTH urban growth model under two different conditions. The first used an excluded layer that ignored such lands, effectively rendering them available for development. The second treated those lands as totally excluded from development. Our hypothesis was that excluding those lands would yield better metrics of fit with past data. Our results validate our hypothesis since two different metrics that evaluate goodness of fit both yielded higher values when differentially assessed lands are treated as excluded. This suggests that, at least in our study area, differential assessment, which protects farm and ranch lands for tenuous periods of time, has indeed allowed farmland to resist urban development. Including differentially assessed lands also yielded very different calibrated coefficients of growth as the model tried to account for the same growth patterns over two very different excluded areas. Excluded layer design can greatly affect model behavior. Since differentially assessed lands are quite common through the United States and are often ignored in urban growth modeling, the findings of this research can assist other urban growth modelers in designing excluded layers that result in more accurate model calibration and thus forecasting.     

Gradually morphing a thematic map series based on cellular automata

Maps are often animated to help users make comparisons and comprehend trends. However, large and complex differences between sequential maps can inhibit users from doing so. This paper proposes a morphing technique to highlight trends without manual intervention. Changes between sequential maps are considered as the diffusion processes of expanding classes, with these processes simulated by cellular automata. A skeleton extraction technique is introduced to handle special cases. Experimental results demonstrate that the proposed morphing technique can reveal obvious trends between dramatically changed maps. The potential application of the proposed morphing technique in sequential spatial data (e.g. remote-sensing images) is discussed.     

Characterization of neighborhood sensitivity of an irregular cellular automata model of urban growth

The neighborhood definition, which determines the influence on a cell from its nearby cells within a localized region, plays a critical role in the performance of a cellular automaton (CA) model. Raster CA models use a cellular grid to represent geographic space, and are sensitive to the cell size and neighborhood configuration. However, the sensitivity of vector-based CAs, an alternative to the raster-based counterpart, to neighborhood type and size remains uninvestigated. The present article reports the results of a detailed sensitivity analysis of an irregular CA model of urban land use dynamics. The model uses parcel data at the cadastral scale to represent geographic space, and was implemented to simulate urban growth in Central Texas, USA. Thirty neighborhood configurations defined by types and sizes were considered in order to examine the variability in the model outcome. Results from accuracy assessments and landscape metrics confirmed the model’s sensitivity to neighborhood configurations. Furthermore, the centroid intercepted neighborhood with a buffer of 120 m produced the most accurate simulation result. This neighborhood produced scattered development while the centroid extent-wide neighborhood resulted in a clustered development predominantly near the city center.     

Modelling sustainable urban growth in a rapidly urbanising region using a fuzzy-constrained cellular automata approach

This article presents an application of a fuzzy-constrained cellular automata model to simulate the spatio-temporal processes of urban growth in the rapidly growing Gold Coast City in Southeast Queensland, Australia. Urban growth has been captured in the model as a continuous process in space and over time, which has been affected by a set of primary and secondary transition rules. The primary transition rules deal with the propensity of a local area for development and the impact of its neighbouring cells on such development, while the secondary transition rules reflect the influences of environmental and institutional factors on urban growth. Application of the model demonstrates its re-applicability to different regions and the effectiveness of the cellular automata technique in studying urban dynamics. It also provides tools to explore sustainable urban growth options under different socio-environmental and planning control factors. A sustainable urban future of the region is achievable if development is managed to maintain a balance amongst ecological conservation, economic growth and the contemporary Australian lifestyle.     

Flood evacuation simulations using cellular automata and multiagent systems -a human-environment relationship perspective

ABSTRACT

A flood evacuation represents a complex geographic phenomenon that includes comprehensive interactions among humans, the flood and urban environments; thus, the simulation of flood evacuations requires crowd simulation models to be coupled with flood models. This paper studies the human-environment relationship during flooding and promotes a simulation model that combines cellular automata and a multiagent system to simulate crowd evacuations in flood disasters. A case study of Niaodao Island was used to evaluate the performance of flood evacuation experiments, and real-participant experiments based on the virtual reality (VR) environment were employed for bench-mark comparisons. The integrated model can provide a comprehensive solution to assist flood risk analysis.     

Reconstruction of historical arable land use patterns using constrained cellular automata: A case study of Jiangsu,China

The reconstruction of arable land patterns over historical periods is one of critical research issues in the study of land use and land cover change (LUCC). Taking into account the continuous distribution of arable land and spatial constraints, this paper proposes a constrained cellular automata model to reconstruct historical arable land patterns. The paper describes model establishment, parameter calibration, and results validation in detail. The model was applied to Jiangsu Province, China, and was compared with a conventional spatial allocation method. The results showed that the methodology developed in this study can more objectively reflect the evolution of the pattern of arable land over historical periods, in terms of similarity with contemporary pattern, than the spatial allocation methods and can provide an effective basis for the historical study of arable land.     

Simulating urban growth under planning policies through parcel-based cellular automata (ParCA) model

In recent decades, the cellular automata model, among the urban development prediction models, has been applied considerably. Studies show that the output of conventional cellular automata models is sensitive to cell size and neighborhood structure, and varies with changes in the size of these parameters. To solve this problem, vector-based cellular automata models have been introduced which have overcome the mentioned limitations and presented better results. The aim of this study was to present a parcel-based cellular automata (ParCA) model for simulating urban growth under planning policies. In this model, undeveloped areas are first subdivided into smaller parcels, based on some geometric parameters; then, neighborhood effect of parcels is defined in a radial structure, based on a weighted function of distance, area, land-use, and service level of irregular cadastral parcels. After that, neighborhood effect is evaluated using three components, including compactness, dependency and compatibility. The presented model was implemented and analyzed using data from municipal region 22 of Tehran. The obtained results indicated the high ability of ParCA model in allocating various land-uses to parcels in the appropriateness of the layout of different land-uses. This model can be used in decision-making and urban land-use planning activities, since it provides the possibility of allocating different urban land-use types and assessing different urban-growth scenarios.     

How much past to see the future: a computational study in calibrating urban cellular automata

The objective of this computational study was to investigate to which extent the availability and the way of use of historical maps may affect the quality of the calibration process of cellular automata (CA) urban models. The numerical experiments are based on a constrained CA applied to a case study. Since the model depends on a large number of parameters, we optimize the CA using cooperative coevolutionary particle swarms, which is an approach known for its ability to operate effectively in search spaces with a high number of dimensions. To cope with the relevant computational cost related to the high number of CA simulations required by our study, we use a parallelized CA model that takes advantage of the computing power of graphics processing units. The study has shown that the accuracy of simulations can be significantly influenced by both the number and position in time of the historical maps involved in the calibration.     

基于随机森林的元胞自动机城市扩展模拟——以佛山市为例

本文提出一种基于随机森林的元胞自动机城市扩展(RF-CA)模型。通过在多个决策树的生成过程中分别对训练样本集和分裂节点的候选空间变量引入随机因素,提取城市扩展元胞自动机的转换规则。该模型便于并行构建,能在运算量没有显著增加的前提下提高预测的精度,对城市扩展中存在的随机因素有较强的容忍度。RF-CA模型可进行袋外误差估计,以快速获取模型参数;也可度量空间变量重要性,解释各空间变量在城市扩展中的作用。将该模型应用于佛山市1988-2012年的城市扩展模拟中,结果表明,与常用的逻辑回归模型相比,RF-CA模型进行模拟和预测分别能够提高1.7%和2.6%的精度,非常适用于复杂非线性特征的城市系统演变模型与扩展研究;通过对影响佛山市城市扩展的空间变量进行重要性度量,发现对佛山城市扩张模拟研究而言,距国道的距离与距城市中心的距离具有最重要的作用。     

Modeling urban expansion by using variable weights logistic cellular automata: a case study of Nanjing,China

Simulation models based on cellular automata (CA) are widely used for understanding and simulating complex urban expansion process. Among these models, logistic CA (LCA) is commonly adopted. However, the performance of LCA models is often limited because the fixed coefficients obtained from binary logistic regression do not reflect the spatiotemporal heterogeneity of transition rules. Therefore, we propose a variable weights LCA (VW-LCA) model with dynamic transition rules. The regression coefficients in this VW-LCA model are based on VW by incorporating a genetic algorithm in a conventional LCA. The VW-LCA model and the conventional LCA model were both used to simulate urban expansion in Nanjing, China. The models were calibrated with data for the period 2000–2007 and validated for the period 2007–2013. The results showed that the VW-LCA model performed better than the LCA model in terms of both visual inspection and key indicators. For example, kappa, accuracy of urban land and figure of merit for the simulation results of 2013 increased by 3.26%, 2.96% and 4.44%, respectively. The VW-LCA model performs relatively better compared with other improved LCA models that are suggested in literature.