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.     

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.     

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.     

元胞自动机在城市模拟中的误差传递与不确定性的特征分析

元胞自动机(Cellular Automata,简称CA)已越来越多地用于地理现象的模拟中,如城市系统的演化等。城市模拟经常要使用GIS数据库中的空间信息,数据源中的误差将会通过CA模拟过程发生传递。此外,CA 模型只是对现实世界的近似模拟,这就使得其本身也具有不确定性。这些不确定因素将对城市模拟的结果产生较大的影响,有必要探讨CA在模拟过程中的误差传递与不确定性问题。本文采用蒙特卡罗方法模拟了CA误差的传递特征,并从转换规则、邻域结构、模拟时间以及随机变量等几个方面分析了CA不确定性产生的根源。发现与传统的GIS模型相比,城市CA模型中的误差和不确定性的很多性质是非常独特的。例如,在模拟过程中由于邻域函数平均化的影响,数据源误差将减小;随着可用的土地越来越少,该限制也使城市模拟的误差随时间而减小;模拟结果的不确定性主要体现在城市的边缘。这些分析结果有助于城市建模和规划者更好地理解CA建模的特点。     

Configuring the neighbourhood effect in irregular cellular automata based models

Cellular automata (CA) models have been widely employed to simulate urban growth and land use change. In order to represent urban space more realistically, new approaches to CA models have explored the use of vector data instead of traditional regular grids. However, the use of irregular CA-based models brings new challenges as well as opportunities. The most strongly affected factor when using an irregular space is neighbourhood. Although neighbourhood definition in an irregular environment has been reported in the literature, the question of how to model the neighbourhood effect remains largely unexplored. In order to shed light on this question, this paper proposed the use of spatial metrics to characterise and measure the neighbourhood effect in irregular CA-based models. These metrics, originally developed for raster environments, namely the enrichment factor and the neighbourhood index, were adapted and applied in the irregular space employed by the model. Using the results of these metrics, distance-decay functions were calculated to reproduce the push-and-pull effect between the simulated land uses. The outcomes of a total of 55 simulations (5 sets of different distance functions and 11 different neighbourhood definition distances) were compared with observed changes in the study area during the calibration period. Our results demonstrate that the proposed methodology improves the outcomes of the urban growth simulation model tested and could be applied to other irregular CA-based models.     

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.     

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.     

An agent-integrated irregular automata model of urban land-use dynamics

Urban growth models are useful tools to understand the patterns and processes of urbanization. In recent years, the bottom-up approach of geo-computation, such as cellular automata and agent-based modeling, is commonly used to simulate urban land-use dynamics. This study has developed an integrated model of urban growth called agent-integrated irregular automata (AIIA) by using vector geographic information system environment (i.e. both the data model and operations). The model was tested for the city of San Marcos, Texas to simulate two scenarios of urban growth. Specifically, the study aimed to answer whether incorporating commercial, industrial and institutional agents in the model and using social theories (e.g. utility functions) improves the conventional urban growth modeling. By validating against empirical land-use data, the results suggest that a holistic framework such as AIIA performs better than the existing irregular-automata-based urban growth modeling.     

Mining transition rules of cellular automata for simulating urban expansion by using the deep learning techniques

Along with the gradually accelerated urbanization process, simulating and predicting the future pattern of the city is of great importance to the prediction and prevention of some environmental, economic and urban issues. Previous studies have generally integrated traditional machine learning with cellular automaton (CA) models to simulate urban development. Nevertheless, difficulties still exist in the process of obtaining more accurate results with CA models; such difficulties are mainly due to the insufficient consideration of neighborhood effects during urban transition rule mining. In this paper, we used an effective deep learning method, named convolution neural network for united mining (UMCNN), to solve the problem. UMCNN has substantial potential to get neighborhood information from its receptive field. Thus, a novel CA model coupled with UMCNN and Markov chain was designed to improve the performance of simulating urban expansion processes. Choosing the Pearl River Delta of China as the study area, we excavate the driving factors and the transformational relations revealed by the urban land-use patterns in 2000, 2005 and 2010 and further simulate the urban expansion status in 2020 and 2030. Additionally, three traditional machine-learning-based CA models (LR, ANN and RFA) are built to attest the practicality of the proposed model. In the comparison, the proposed method reaches the highest simulation accuracy and landscape index similarity. The predicted urban expansion results reveal that the economy will continue to be the primary factor in the study area from 2010 to 2030. The proposed model can serve as guidance in urban planning and government decision-making.