多目标粒子群优化算法在配置城市土地使用上的应用

多目标粒子群优化算法在配置城市土地使用上的应用Considering the ever-increasing urban population, it appears that land management is of major importance. Land uses must be properly arranged so that they do not interfere with one another and can meet each others needs as much as possible; this goal is a challenge of urban land-use planning. The main objective of this research is to use Multi-Objective Particle Swarm Optimization algorithm to find the optimum arrangement of urban land uses in parcel level, considering multiple objectives and constraints simultaneously. Geospatial Information System is used to prepare the data and to study different spatial scenarios when developing the model. To optimize the land-use arrangement, four objectives are defined: maximizing compatibility, maximizing dependency, maximizing suitability, and maximizing compactness of land uses. These objectives are characterized based on the requirements of planners. As a result of optimization, the user is provided with a set of optimum land-use arrangements, the Pareto-front solutions. The user can select the most appropriate solutions according to his/her priorities. The method was tested using the data of region 7, district 1 of Tehran. The results showed an acceptable level of repeatability and stability for the optimization algorithm. The model uses parcel instead of urban blocks, as the spatial unit.Moreover, it considers a variety of land uses and tries to optimize several objectives Simultaneously.1摘要：考虑到不断增加的城市人口，土地管理看起来就具有重大意义。土地利用必须妥善安排，使它们不会干扰彼此并尽可能满足对方的需要；这个目标对于城市土地利用规划是一个挑战。本研究的主要目的是同时考虑多个目标限制，利用多目标粒子群优化算法来找到最佳用于城市土地安排地块的水平。地理空间信息系统是在开发模型时，用来准备数据和研究不同空间场景。为了优化土地利用布局，定义四个目标为：最大限度地兼容，最大限度地依赖关系，最大限度地提高适用性，并最大限度地提高土地利用的紧凑性。这些目标的特点是根据规划的要求，帕累托以前的解决方案其结果是向用户提供一组最佳的土地利用安排。用户可以选择最合适的解决方案根据他/她的重点。该方法使用区域7德黑兰1的数据进行了测试。结果表明了是一个重复性和稳定性可接受的优化算法。该模型使用地块而不是城市街区地块作为空间单元。此外，同时它考虑不同的土地用途并试图优化多个目标关键词：安排;城市，土地利用，地理信息系统;优化; MOPSOLand-use optimization is a method of resource allocation, in which different activities or land uses are allocated to specific units of land area. These kinds of problems need multiple and often conflicting objectives (such as ecological and economic objectives) to be considered simultaneously (Chandramouli et al. 2009, Xiaoli et al. 2009, Cao et al. 2011, Shifa et al. 2011). Therefore, land-use allocation can be considered as an optimization problem. In multi-objective optimization of land use (MOLU) model, combinations of different objectives are considered. The commonly used objectives include the improvements related to compatibility and dependency among neighbouring land uses, the suitability of land units for land uses, land-use compactness, and the per capita demand for land use. These parameters have been studied and discussed by Berke et al. (2006), Talei et al. (2007), Jiang-Ping and Qun (2009), Haque and Asami (2011), and Koomen et al. (2011).土地利用优化是不同的土地使用行为分配其特定的单位土地面积资源配置的一种方法，。这类问题需要考虑多且被认为是同时相互冲突的目标（如生态和经济目标）（chandramouli等人。2009，小李等人。2009，曹等人。2011，发等人。2011）因此，土地利用配置可以被视为一个优化问题。在土地利用多目标优化（陌路）模型时，考虑了不同的组合目标。常用的目标包括改进相关的邻近土地的使用相容性和依赖性，土单位土地利用的适宜性土地利用结构紧凑，和土地利用人均需求。伯克等人对这些参数进行了研究和讨论。 （2006），Talei等。 （2007年），江平与群（2009），哈克和麻美（2011），以及库门等。 （2011年）。Handling many objectives together is usually more complex than handling a single objective. Therefore, many methods are developed to convert multiple objectives into a single objective. To search the solution space in a single-objective mode, some researchers have used classic methods of optimization such as linear programming (LP). For instance, Maoh and Kanaroglou (2009) used LP to optimize land uses, concentrating on the relation between land use and traffic. Some other models are based on artificial intelligence (AI) methods. For example, Shiffa et al. (2011) used particle swarm optimization (PSO) to optimize the allocation of land uses, considering maximum suitability of land and a minimum cost of changing the land shape. In another study by Semboloni (2004), simulated annealing (SA) method was used to optimize the facilities required for residential and commercial areas. The main problem of these methods is that the results depend strongly on the weights given to the objectives or the function used to combine the objectives into one. Moreover, non-convex optimal solutions cannot be obtained by minimizing linear combinations of objectives (Cao et al. 2011). Besides, decision-makers prefer to explore a set of alternative solutions and their trade-offs regarding different objectives and to make decisions accordingly. To find multiple solutions using such methods, the algorithm has to be run many times, hopefully finding a different solution at each run to create trade-off solutions (Deb et al. 2002).处理许多共同的目标通常比处理一个目标更复杂。因此，许多方法的开发，以多重目标转换成单一目标。在一个单一的目标模式搜索解空间，一些研究人员采用经典的优化方法如线性规划（LP）。例如，例如，他和kanaroglou（2009）使用LP优化土地利用，集中在土地利用与交通之间的关系。其他一些模型是基于人工智能（AI ）方法。例如， Shiffa等。 （ 2011）采用粒子群优化算法（PSO）优化划拨土地使用，考虑最大土地适宜性和最小改变土地形状的成本。在另一项由Semboloni （ 2004）的研究 中，模拟退火（SA）方法被用来优化所需要的设施，住宅和商业区域。这些方法的主要问题是，结果强烈地依赖于考虑到目标或功能用于结合成一个目标的权重。此外，非凸优化的解决方案不能被最小化的线性组合来获得目标（ Cao等2011） 。此外，决策者希望探索一套替代解决方案，权衡不同的目标并做出相应的决策。找到多个解决方案，使用这种方法，该算法必须运行很多次，希望找到不同的解决方案在每次运行时创造权衡解决方案（DEB等。 2002年）。In some other studies, objectives are optimized simultaneously in multi-objective mode focusing on Pareto front. The concept of Pareto front is properly described in Deb et al. (2002) and Coello Coello et al. (2007). The Pareto set is usually independent of the relative importance of objectives, making it suitable for complex applications such as landuse planning. Many studies on land-use optimization are carried out using Pareto front. For example, Feng and Lin (1999) generated different scenarios of urban land uses for urban planners using multi-objective Cumulative Genetic Algorithm (CGA), having the city zones as spatial units. Objective functions were maximizing the suitability of lands for development and maximizing the compatibility of neighbouring zones. Member et al. (2000) used an initiative multi-objective CGA to optimize three objective functions: minimizing traffic, minimizing the costs of transportation, and minimizing current land-use changes. In this initiative algorithm, the optimization process was not performed simultaneously; instead, it was applied step by step for any of the objective functions, and the best results were then taken for optimization of the next function. Ligmann-Zielinska et al. (2008) focused on the efficient utilization of urban space through infill development,compatibility of adjacent land uses, and defensible redevelopment. Cao et al. (2011) used Non-Dominated Sorting Genetic Algorithm (NSGA-II) to propose optimal landuse scenarios with three objective functions: minimizing conversion costs, maximizing accessibility, and maximizing compatibilities between land uses.在其他一些研究中，目标是专注于Pareto前沿在多目标模式下同时优化。 Pareto解的集合概念中的Deb等适当的描述。（ 2002）和科埃略科埃略等人。 （2007年） 。帕累托解的集合是德布等的描述。2002）和Coello Coello等人。2007。帕累托集通常是独立的相对重要的目标，使其适合于复杂的应用，例如土地利用规划。土地利用优化的许多研究都使用了Pareto前沿。例如，冯和林（ 1999）采用多目标累积遗传算法（ CGA ）累计产生城市土地不同的场景用来城市规划，城市区域为空间单元。目标函数是最大化用于开发的土地的适宜性和最大化相邻区的兼容性。Member等（ 2000 ）使用了主动多目标CGA优化三个目标函数：最小化交通，减少运输成本，减少土地利用现状的变化。在这一倡议算法，优化过程中不同时进行；相反，它是一步一步的任何目标函数，得到最好的结果用于随后采取的下一个函数的优化。 Ligmann -杰琳斯卡等。 （ 2008）集中在城市空间的有效利用，通过加密开发，相邻土地用途的兼容性，且正当的重建。 Cao等。 （ 2011 ）使用的非支配排序遗传算法（ NSGA-II ）提出了优化土地利用三目标函数最小化的情景：转换成本，最大化可达性，最大限度地土地使用兼容性。The main objective of this study is to optimize the arrangement of urban land uses in parcel level using Multi-Objective PSO (MOPSO) algorithm, considering multiple objectives and constraints simultaneously. In contrast to the above-mentioned studies, in this research, the main objectives of land-use arrangement (compatibility, dependency, suitability, and compactness) are considered together. In other words, the aim is to optimize the arrangement of urban land uses with respect to all those parameters. This indicates that many objectives have to be considered simultaneously, with a vast search space (many possible arrangements of land uses). The second difference of this research with others is in the usage of PSO for optimization. As indicated in the above literature review, most of the research on multi-objective land-use optimization is based on versions of Genetic Algorithm (GA). The main difference between PSO and GA methods is that PSO does not need genetic operators such as crossover and mutation, which are usually difficult to implement. Moreover, their information sharing mechanism is different: In GA, the information sharing is among all chromosomes, whereas in PSO, only the best particle shares its information with others (Parsopoulos and Vrahatis 2010). In general, the main advantage of PSO is the flexibility and simplicity of its operators (Engelbrecht 2006, Van den Bergh and Engelbrecht 2006). The output of the MOPSO is a Pareto front of optimized answers, among which the user can select the most preferable answer based on his/her own priorities. This model proposes several land arrangements to support decision-making based on parameters specified by a decision-maker.本研究的主要目的是在考虑多重目标同时约束下采用多目标粒子群算法（ MOPSO ）用于优化城市土地地块水平线的安排。相反，在上述研究中，土地利用布局的主要目标（相容性，依赖性，适宜性，和压实度）被认为是在一起的。换句话说，我们的目标是优化城市土地利用相对于这些参数的布置。这表明许多目标必须同时考虑，具有广阔的搜索空间（多土地用途可能的安排） 。在上述文献的回顾表明，大多数对多目标的土地利用优化的研究是基于版本的遗传算法（GA）。PSO和GA方法的主要区别是， 假如不需要遗传操作如交叉和变异，PSO通常很难完成。此外，他们的信息共享机制是不同的：在遗传算法中，信息共享是所有染色体中，而在PSO中，只有最好的颗粒与他人分享它的信息（Parsopoulos和Vrahatis2010）。在一般情况下，PSO算法主要的优点是其运营的灵活性和简单性（公司2006，Van den伯格和公司2006）。在MOPSO的输出是一个帕累托解的集合的优化答案，其中，用户可以选择基于他/她的自己的优先事项的最优选的答案。该模型提出了一些基于决策者指定的参数土地整理决策。2. Fundamentals of the researchIn this section, the concepts of multi-objective optimization and the algorithms applied in this research are discussed.2 该研究的基本原理在本节中，讨论了适用于这项研究的多目标优化算法的概念2.1. Multi-objective optimizationThe purpose of multi-objective optimization problems is to simultaneously optimize several objective functions (Hillier and Liberman 1995; Veldhuizen and Lamont 1999). Thus,there is not only one answer to a problem; instead, one can obtain a set of answers called thePareto front of the optimized answers or the non-dominated answers (Deb et al. 2002,Coello Coello et al. 2007). If we assume that f 1, f 2, . . . , fm are the objective functions of a problem, then xi can be a non-dominated answer if the following conditions are met (Coello Coello and Lomont 2004, Sivanandam and Deepa 2008): The answer xi should not be worse than xj in all objectives; in other words,fk (xi) fk（xj）for all k 1, 2, . . . ,m (1) The answer to xi is better than xj, in at least one objective, that is,fk (xi) fk(xj)for at least one k 1, 2, . . . ,m (2)In multi-objective optimization, when the objective functions are complex and/or the search space is extensive, AI-based methods are often used. Using these methods, the entire search space is not investigated. Therefore, there is no guarantee that the definitely optimum solution can be found. Instead, there is a promise that some solutions near enough to the optimum can be found in reasonable time, regardless of the numerous feasible solutions(Coello Coello and Lamont 2004).2.1 多目标优化多目标优化问题的目的是同时优化几个目标函数（希利尔和利伯曼1995；该和拉蒙特1999）。因此，还有是不是只有一个答案的问题，反而可以得到一组答案叫“帕累托解的集合的优化答案”或“非支配回答，（Deb等人。2002，Coello Coello等人。2007）如果我们假设F 1，F 2，。.FM是一个问题的目标函数，然后xi 可以是一个非支配的答案，如果满足以下条件，（科埃略科埃略和2004年Lomont，Sivanandam和2008年和Deepa）：答案xi不应该比所有的目标的xj更糟，换句话说，fk (xi) fk(xj) for all k 1, 2, . . . ,m (1)对于所有的k1，2，。 。 。 ，M（1）至少在一个目标上答案xi比xj更好，那就是，fk (xi) fk(xj)对于至少一个k1，2，。 。 。 ，M（2）在多目标优化的，当目标函数是复杂的和/或搜索空间是广泛的，基于AI的方法被经常使用。因此，存在不能保证绝对最佳办法可以解决。取而代之的是一个承诺，在众多可行的解决方案中的一些能在合理时间内被发现近优解，（科埃略科埃略和2004年拉蒙特）。2.2. PSO algorithmThe PSO algorithm was developed by Kennedy and Eberhart (1995), as one of the AI-based optimization methods. In PSO, a number of particles are placed in the search space of some problem, each evaluating the objective function (fitness) at its location. In other words, the location of each particle is a solution to the problem, which can be evaluated against the objective function. Each particle decides on its next movement in the search space by combining some aspect of the history of its own best (best-fitness) locations with those of some members of the swarm. The next iteration happens when all particles are moved.Gradually, the swarm moves toward the optimum of the fitness function (Clerc 2006). If the dimension of the search space is d, the current location and velocity of the particle at time t are denoted by vectors x and v, respectively. Furthermore, the best position of all particles in the whole space (Gbest) and the best position of the particle in the previous movement experiences (Pbest) are memorized. With these explanations, the equation of the particlesmotion for any dimension of d (the dth part of this vector will be indicated with the d index) is (Parsopoulos and Vrahatis 2010):where and are the previous velocity and location of the particle in the dth dimension,respectively; and are the new velocity and location of the particle in the same dimension, respectively; w is the inertia weight (commonly set to 2), r1 and r2 are random numbers generated uniformly in the range 0, 1 and are to provide randomness in the flight of the swarm; and c1 and c2 are weighting factors, also called the cognitive and social parameters, respectively (Shi and Eberhart 1998, Poli et al. 2007). The weight coefficients c1 and c2 control the relative effect of the Pbest and Gbest locations on the velocity of a particle. Although lower values for c1 and c2 allow each particle to explore locations far away from already uncovered good points, higher values of these parameters encourage more intensive search of regions close to previous points (Clerc 2006).2.2 粒子群优化算法PSO算法是由甘乃迪和Eberhart开发的（1995），作为一种基于人工智能的优化方法。在PSO，一些粒子被放置在一些搜索问题的空间，在它的位置上有每个目标的评价函数。换句话说，每个粒子的位置是一个解决问题的办法，它可以被目标函数评估。每个粒子结合其历史方面的一些最好的（最适宜）的位置和一些群体其它成员的最好位置决定在搜索空间的下一个动作。所有的粒子移动时下一次迭代发生。渐渐地，群走向的适应度最佳的函数（二零零六年克莱尔奇）。如果搜索空间的维数为d，在时间t的粒子的当前位置和速度是向量X，V表示。此外，所有粒子在整个空间的最佳位置（Gbest）和在先前的粒子的最佳运动位置（Pbest）将被存储。这些说明中，粒子的方程的在d的任何一个维度上移动是（此向量的第d部分会与D指数一起显示）为（Parsopoulos和Vrahatis2010）：其中和为在第d维度上之前的速度和粒子的位置，和是在同样维度上的新的粒子速度和粒子的位置，此外，w为惯性重量（通常为2），r1和r2是在0,1范围内均匀地产生的随机数，并且提供群的随机性飞行；C1和C2是加权因子，也分别称为认知参数和社会参数（Shi和埃伯哈特1998年，波利等人，2007）。权重系数c1和c2控制Pbest位置和Gbest位置对于一个粒子速度的相对影响。c1和c2值较小时允许每个粒子探索地点远离已经发现的好点，这些参数的值越高鼓励粒子搜索靠拢前期点比较密集的区域（二零零六年克莱尔奇）。2.3. MOPSO algorithmMOPSO algorithms can be divided into two categories (Reyes-Sierra and Coello Coello2006). The first category consists of PSO variants that consider each objective function separately. In these approaches, each particle is evaluated with only one objective function at a time, and the best positions are determined following the standard single objective PSO rules, using the corresponding objective function. The main challenge in these PSO variants is the proper manipulation of information from each objective function,in order to guide particles toward Pareto-optimal solutions. The second category consists of approaches that evaluate all objective functions for each particle, and based on the concept of Pareto optimality, produce non-dominated best positions (often called leaders) to guide the particles. The determination of leaders is non-trivial, since they have to be selected among a plethora of non-dominated solutions in the neighbourhood of a particle. This is the main challenge related to the second category. Many methods have been used for this purpose (Reyes-Sierra and Coello Coello 2006, Parsopoulos and Vrahatis 2010; Fan et al.2010). In this article, a method proposed by Coello Coello and Lamont (2004) was used because it has less computational complexity and a quicker convergence (Reyes-Sierra and Coello Coello 2006). The following is a brief explanation of the method.First, an initial population is created, the values of the objective functions are calculated, and non-dominant answers are preserved in an external archive. In the archive of nondominant answers, some hyper-cubes (with the same dimension as objective functions) are created. In Figure 1, an example of a two-dimensional search space and its division into hyper-cubes is shown. In the two-dimensional search space, the hyper-cubes are squares. Then, the following process is employed until the number of repetitions comes to an end and/or the final condition of the algorithm is met.2.3 MOPSO算法MOPSO算法可以分为两大类（雷耶斯- Sierra和科埃略科埃略2006年）。第一类包括分开考虑各目标函数的PSO变种。在这些方法中，每个粒子每次只有一个目标函数进行评价，最好的位置是按照单一目标标准确定PSO规则，使用相应的目标函数。PSO变种面临的主要挑战是每个目标函数的正确的操作信息，这些信息是为了引导粒子走向帕累托最优的解。第二类包括为每个粒子评价所有的目标函数，并基于帕累托最优概念的方法，产生非支配最佳位置（通常被称为领导者）来指导的颗粒。领导者的确定是不平凡的，因为它们是在颗粒的附近过多的非支配解中被选择的。这是第二类别的主要挑战。许多方法已被用于这个目的（雷耶斯- Sierra和科埃略科埃略2006年， Parsopoulos和Vrahatis 2010 ; Fan等。2010） 。在这篇文章中，使用由科埃略科埃略和拉蒙特（ 2004）提出的方法 因为它具有更小的计算复杂度和更快的收敛（雷耶斯- Sierra和科埃略科埃略2006） 。下面是该方法的简要说明。第一，在创建初始种群，计算目标函数的值，与非主导的答案都保存在一个外部档案。在非优势的答案存档中，一些超立方体（具有相同的维数作为目标函数）被创建。在图1中，一个二维搜索空间和其分裂成超立方体被显示。在二维搜索空间中，超立方体是正方形。然后，下面的方法时，直到重复次数玩完和/或算法的最终条件得到满足。 Figure 1. An example of hyper-cubes generated in a two-dimensional search space of two objectivefunctions. Each cell shows one hyper-cube in this space (Coello Coello et al. 2004).图1。在两个目标的二维搜索空间中产生的超立方体的例子功能。每个单元显示在这个空间的一个超立方体（科埃略科埃略等人，2004）。The velocity of any particle in the d dimension can be calculated by the followingequation: where all of the parameters are the same as in Equation (3), with the exception that rep(h) is the value obtained from the non-dominated archive as a leader, as described in the followings.By assuming m as the number of available solutions in a hyper-cube, the probability roulette wheel of Equation (6) is applied to choose a hyper-cube with the h index. In fact, the aim is to choose a hyper-cube with fewer particles to optimize the density of the Paretofront.在d维的任何粒子的速度可以通过以下计算公式： where all of the parameters are the same as in Equation (3), with the exception that rep(h) is the value obtained from the non-dominated archive as a leader, as described in the followings.By assuming m as the number of available solutions in a hyper-cube, the probability roulette wheel of Equation (6) is applied to choose a hyper-cube with the h index. In fact, the aim is to choose a hyper-cube with fewer particles to optimize the density of the Pareto front.所有的参数是相同的在方程（3），除代表（H）从非得到价值主导的档案作为一个领袖，如在以下。通过假设M作为一个超立方体可解的个数，概率方程轮盘（6）应用于选择与H指数超立方体。事实上，其目的是选择用较少的粒子优化的帕累托密度超立方体前。所有的参数是和方程（3）中相同的，除rep(h)是从作为一个领袖的非主导的档案得到的值。如在以下。通过假设m作为一个超立方体可解的个数，概率轮盘方程（6）与指数应用于选择超立方体。事实上，其目的是用较少的粒子选择一个超立方体去优化的帕累托解的集合的密度。where mi is the number of particles in the ith hyper-cube, is a constant coefficient to control the amount of differentiations in the probability values, and k is the number of all hyper-cubes.After choosing hyper-cube h, one of its solutions is chosen randomly as a leader (rep(h) in Equation (5) for the next run, and the new position of the particles is calculated. The process is continued until the optimization criteria are met. In multi-objective optimization, usually the criterion is to reach a specified number of iteration.其中mi是在第i个超立方体颗粒的数，为常数系数，控制概率值中的差异量，以及k是所有的超立方体的个数。当选择超立方体h后，被选择的解决方案中的一个被随机作为下一个运行的一个领导者（REP（h）在公式（5），并且粒子的新位置被计算。该过程继续进行直到最优化准则得到满足。在多目标优化下，通常情况下准则一定会达到迭代的指定数量。3. Developed land-use optimization modelIn this section, we first match the MOPSO method with the problem in hand, the optimizationof land-use arrangement. This includes the definition of the answer structure, the objective functions, and the constraints.In the PSO algorithm used here, every possible arrangement of all considered land uses throughout the entire land units can be considered as a potential particle (particle location) in the search space. The algorithm looks for a particle location (an arrangementof land uses) that satisfies the objective