A heuristic cellular automata approach for modelling urban land-use change based on simulated annealing

This article presents a novel cellular automata (CA) approach to simulate the spatio-temporal process of urban land-use change based on the simulated annealing (SA) algorithm. The SA algorithm enables dynamic optimisation of the CA's transition rules that would otherwise be difficult to configure using conventional mathematical methods. In this heuristic approach, an objective function is constructed based on a theoretical accumulative disagreement between the simulated land-use pattern and the actual land-use pattern derived from remotely sensed imagery. The function value that measures the mismatch between the actual and the simulated land-use patterns would be minimised randomly through the SA process. Hence, a set of attribution parameters that can be used in the CA model is achieved. An SA optimisation tool was developed using Matlab and incorporated into the cellular simulation in GIS to form an integrated SACA model. An application of the SACA model to simulate the spatio-temporal process of land-use change in Jinshan District of Shanghai Municipality, PR China, from 1992 to 2008 shows that this modelling approach is efficient and robust and can be used to reconstruct historical urban land-use patterns to assist with urban planning policy-making and actions. Comparison of the SACA model with a typical CA model based on a logistic regression method without the SA optimisation (also known as LogCA) shows that the SACA model generates better simulation results than the LogCA model, and the improvement of the SACA over the LogCA model is largely attributed to higher locational accuracy, a feature desirable in most spatially explicit simulations of geographical processes.     

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.     

Integrated modelling of population,employment and land-use change with a multiple activity-based variable grid cellular automaton

A constrained cellular automaton (CA) framework is used to model both land use and, at the same resolution, densities of population and economic activity. The multi-scale processes determining the location of population, economic activity and land use are captured in a variable grid CA, in which the neighbourhood of each cell includes the entire modelled area. The transition rules generating the spatial dynamics incorporate both the land use and the activities, and because they cover the entire modelled area, they represent interaction effects at all spatial scales; effectively, they are distance decay functions. In general, any particular cell hosts a number of activities (population, employment in various sectors) regardless of its land use, so in effect multiple land uses are modelled as multiple activities, although activity levels are normally highest on cells of the corresponding land use. The model is applied to both the urban-centred Greater Dublin Region and the country of Belgium, which consists of the entire polycentric urban system and its rural matrix. Results for both applications are good, as measured by the errors of both predicted populations and fractal dimensions, and the model outperforms the best existing models by these measures.     

Simulating urban land-use changes at a large scale by integrating dynamic land parcel subdivision and vector-based cellular automata

Cellular automata (CA) have been widely used to simulate complex urban development processes. Previous studies indicated that vector-based cellular automata (VCA) could be applied to simulate urban land-use changes at a realistic land parcel level. Because of the complexity of VCA, these studies were conducted at small scales or did not adequately consider the highly fragmented processes of urban development. This study aims to build an effective framework called dynamic land parcel subdivision (DLPS)-VCA to accurately simulate urban land-use change processes at the land parcel level. We introduce this model in urban land-use change simulations to reasonably divide land parcels and introduce a random forest algorithm (RFA) model to explore the transition rules of urban land-use changes. Finally, we simulate the land-use changes in Shenzhen between 2009 and 2014 via the proposed DLPS-VCA model. Compared to the advanced Patch-CA and RFA-VCA models, the DLPS-VCA model achieves the highest simulation accuracy (Figure-of-Merit = 0.232), which is 32.57% and 18.97% higher respectively, and is most similar to the actual land-use scenario (similarity = 94.73%) at the pattern level. These results indicate that the DLPS-VCA model can both accurately split the land during urban land-use changes and significantly simulate urban expansion and urban land-use changes at a fine scale. Furthermore, the land-use change rules that are based on DPLS-VCA mining and the simulation results of several future urban development scenarios can act as guides for future urban planning policy formulation.     

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.     

基于元胞自动机模型的土地利用变化模拟——以大连经济技术开发区为例

元胞自动机模型已经成为模拟土地利用变化的重要方法。传统土地模拟方法中侧重于通过分析影响土地利用变化的因素来构建预测模型,较少从土地利用类型变化及其相互作用的空间角度来关注模型构建。本文以1998年、2004年和2009年1:10000土地利用数据,利用Python语言结合GDAL与Numpy类库实现局部土地利用竞争的元胞自动机模型原型开发,并用于模拟大连市经济技术开发区1998-2009年土地利用变化模拟。研究结果:1建立了发掘多地类之间相互作用关系的试验方法,研究适用于具有明确物理意义的多地类元胞自动机模拟模型;2该模型具有好的模拟精度,对建设用地、农用地和林地等3种不同类型用地进行同时模拟,其对应Kappa系数分别为0.762,0.634和0.678;3该模型建立了研究不同种地类协调作用的基本方法,可以用于进一步研究土地利用变化地类之间驱动原理。     

基于GA-MCE算法的不规则邻域CA土地利用模拟

不规则邻域元胞自动机通过定义一定的邻域规则,将对中心元胞影响较大的邻域元胞进行识别与计算从而确定邻域形态与影响范围,与传统元胞自动机模型相同尺寸邻域形态相比,模拟更加真实有效。基于不规则邻域识别算法对元胞邻域范围进行划分,再通过遗传算法和多准则评价相结合获取转化规则参数,继而对大连市金石滩国家旅游度假区2004年和2010年土地利用变化进行模拟研究,通过比对分析以及Kappa系数检验法对模拟精度做一检验,研究模拟结果总体Kappa系数为81.62%,具有一定的可靠性,研究显示该模型在多地类碎小斑块之间的转化模拟具有一定的优势,对于模拟土地利用/覆盖变化模型具有一定的改进。     

多层次矢量元胞自动机建模及土地利用变化模拟

城市规划对土地利用变化起着重要的引导作用,各层次规划相互支撑、互为补充,自上而下影响着土地利用格局的演变。矢量元胞自动机以不规则的地理实体作为基本单元,可以更逼真地表达客观复杂的城市用地空间结构。然而,当面向具有层次协同性、空间引导性和管控传导性等特征的城市规划时,其元胞多层次体系构造、层次间协同方法和转换规则获取等关键问题凸显出来。本文以江阴市2007年、2012年、2017年3期土地利用现状数据为基础,在多层次矢量元胞自动机建模基础上,模拟了2017年土地利用变化,通过模拟结果与用地现状对比分析,对模型个别参数进行了修正,进一步提高了模型的可行性与适用性,进而预测了2022年城市土地利用格局。模拟结果显示,中心城片区建设用地发展已经趋于饱和,澄南、澄东南和澄东片区建设用地扩张较为明显,有逐步形成“中心城区—城镇组团—村庄”三级城乡空间聚落体系的趋势。最后利用FoM指标对模拟结果进行了评价,得到整体和各片区的精度基本都大于或接近于0.21,表明模拟结果精度较高,其构建的模型在面向多层次规划的用地变化模拟方面具有更好的效果。     

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.     

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.     

A comparative approach to modelling multiple urban land use changes using tree-based methods and cellular automata: the case of Greater Tokyo Area

Urban multiple land use change (LUC) modelling enables the realistic simulation of LUC processes in complex urban systems; however, such modelling suffers from technical challenges posed by complicated transition rules and high spatial heterogeneity when predicting the LUC of a highly developed area. Tree-based methods are powerful tools for addressing this task, but their predictive capabilities need further examination. This study integrates tree-based methods and cellular automata to simulate multiple LUC processes in the Greater Tokyo Area. We examine the predictive capability of 4 tree-based models – bagged trees, random forests, extremely randomised trees (ERT) and bagged gradient boosting decision trees (bagged GBDT) – on transition probability prediction for 18 land use transitions derived from 8 land use types. We compare the predictive power of a tree-based model with multi-layer perceptron (MLP) and among themselves. The results show that tree-based models generally perform better than MLP, and ERT significantly outperforms the three other tree-based models. The outstanding predictive performance of ERT demonstrates the advantages of introducing bagging ensemble and a high degree of randomisation into transition probability modelling. In addition, through variable importance evaluation, we found the strongest explanatory powers of neighbourhood characteristics for all land use transitions; however, the size of the impacts depends on the neighbourhood land use type and the neighbourhood size. Furthermore, socio-economic and policy factors play important roles in transitions ending with high-rise buildings and transitions related to industrial areas.     

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

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

Simulating urban growth by integrating landscape expansion index (LEI) and cellular automata

Traditional urban cellular automata (CA) model can effectively simulate infilling and edge-expansion growth patterns. However, most of these models are incapable of simulating the outlying growth. This paper proposed a novel model called LEI-CA which incorporates landscape expansion index (LEI) with CA to simulate urban growth. Urban growth type is identified by calculating the LEI index of each cell. Case-based reasoning technique is used to discover different transition rules for the adjacent growth type and the outlying growth type, respectively. We applied the LEI-CA model to the simulation of urban growth in Dongguan in southern China. The comparison between logistic-based CA and LEI-CA indicates that the latter can yield a better performance. The LEI-CA model can improve urban simulation accuracy over logistic-based CA by 13.8%, 10.8% and 6.9% in 1993, 1999 and 2005, respectively. Moreover, the outlying growth type hardly exists in the simulation by logistic-based CA, while the proposed LEI-CA model performs well in simulating different urban growth patterns. Our experiments illustrate that the LEI-CA model not only overcomes the deficiencies of traditional CA but might also better understand urban evolution process.     

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 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 general-purpose parallel raster processing programming library test application using a geographic cellular automata model

A general-purpose parallel raster processing programming library (pRPL) was developed and applied to speed up a commonly used cellular automaton model with known tractability limitations. The library is suitable for use by geographic information scientists with basic programming skills, but who lack knowledge and experience of parallel computing and programming. pRPL is a general-purpose programming library that provides generic support for raster processing, including local-scope, neighborhood-scope, regional-scope, and global-scope algorithms as long as they are parallelizable. The library also supports multilayer algorithms. Besides the standard data domain decomposition methods, pRPL provides a spatially adaptive quad-tree-based decomposition to produce more evenly distributed workloads among processors. Data parallelism and task parallelism are supported, with both static and dynamic load-balancing. By grouping processors, pRPL also supports data–task hybrid parallelism, i.e., data parallelism within a processor group and task parallelism among processor groups. pSLEUTH, a parallel version of a well-known cellular automata model for simulating urban land-use change (SLEUTH), was developed to demonstrate full utilization of the advanced features of pRPL. Experiments with real-world data sets were conducted and the performance of pSLEUTH measured. We conclude not only that pRPL greatly reduces the development complexity of implementing a parallel raster-processing algorithm, it also greatly reduces the computing time of computationally intensive raster-processing algorithms, as demonstrated with pSLEUTH.     

A bat-inspired approach to define transition rules for a cellular automaton model used to simulate urban expansion

A new metaheuristic approach is presented to discover transition rules for a cellular automaton (CA) model using a novel bat movement algorithm (BA). CA is capable of simulating the evolution of complex geographical phenomena, and transition rules lie at the core of these models. An intelligence algorithm based on the echolocation behavior of bats is used to discover explicit transition rules for use in simulating urban expansion. CA transition rules are formed by links between attribute constraint items and classification items. The transition rules are derived using the BA to optimize the lower and upper threshold values for each attribute. The BA-CA model is then constructed for the simulation of urban expansion observed for Nanjing City, China. The total accuracy of newly formulated BA-CA model for this application is 86.9%, and the kappa coefficient is 0.736, which strongly suggest that the interactions of bats are effective in capturing the relationships between spatial variables and urban dynamics. It is further demonstrated that this bat-inspired BA-CA model performs better than the null model, the particle swarm optimization-based CA model (PSO-CA), and the ant colony optimization-based CA model (ACO-CA) using the same dataset. The model validation and comparison illustrate the novel capability of BA for discovering transition rules of CA during the simulation of urban expansion and potentially for other geographic phenomena.     

Simulating urban land use change by integrating a convolutional neural network with vector-based cellular automata

ABSTRACT

Vector-based cellular automata (VCA) models have been applied in land use change simulations at fine scales. However, the neighborhood effects of the driving factors are rarely considered in the exploration of the transition suitability of cells, leading to lower simulation accuracy. This study proposes a convolutional neural network (CNN)-VCA model that adopts the CNN to extract the high-level features of the driving factors within a neighborhood of an irregularly shaped cell and discover the relationships between multiple land use changes and driving factors at the neighborhood level. The proposed model was applied to simulate urban land use changes in Shenzhen, China. Compared with several VCA models using other machine learning methods, the proposed CNN-VCA model obtained the highest simulation accuracy (figure-of-merit = 0.361). The results indicated that the CNN-VCA model can effectively uncover the neighborhood effects of multiple driving factors on the developmental potential of land parcels and obtain more details on the morphological characteristics of land parcels. Moreover, the land use patterns of 2020 and 2025 under an ecological control strategy were simulated to provide decision support for urban planning.