多目标粒子群算法与选址中的形状优化

Particle-Swarm Optimization for Site Selection with Contiguity Constraints

选址问题是GIS最基本的任务之一。一般性的选址是基于点的位置优化,可利用有关GIS功能完成。实际的选址问题是很复杂的。在给定设施的数量和面积前提下,需要在空间上确定设施的最佳位置,并对形状进行优化,以获取最大的效用。采用一般的方法无法求解这种最优化问题。而且,当选址问题涉及多个目标和不同的约束性条件时,就会变得异常复杂。提出了利用多目标粒子群优化算法和区域形状变异算法相结合来解决复杂的空间选址问题。具有智能的搜索方法,大大提高了空间搜索能力,并保持了搜索区域的连通性,取得了较好的效果。

Site selection,which is one basic task of GIS functionalities,is to search for the best sites for a facility or a number of facilities.The objective is to maximize some utility functions subject to some goals.Traditional site selection methods using GIS only focus on the identifying the best locations(coordinates) of facilities.In many applications,contiguity constraints must be considered in site selection.Site selection should consider not only locations,but also patch configuration for solving many optimization problems.The objective is to maximize utility functions subject to contiguity constraints and various planning goals.The combination of locations and contiguity for site selection is a difficult problem for site selection because of involving huge solution space.The problem becomes more complex when multi-objectives are incorporated in the optimization.Many alternative generating techniques(such as the weighting method and the non-inferior set estimation method) have been developed to help decision-makers search solution spaces.Although these methods are effective under some circumstances,the approaches have several weaknesses:(1) it can only be applied to problems that are mathematically formulated;(2) it is inefficient when applied to large problems;and(3) it may fail to find important solutions.As a consequence,builders of decision-support tools require methods that overcome these limitations and efficaciously generate alternative solutions to multi-objectives decision problems.Particle-swarm optimization(PSO) can be used to achieue such goals.This paper presents a new method to solve such problem by using particle-swarm optimization(PSO) method and shape-mutate algorithms,which is a strict mutation operator to prevent the formation of 'holes' in searching for optimal contiguous sites.Particle-swarm optimization method is used to make the solutions flying to the best locations.Shape contiguity constraint and patch configuration optimization are operated by shape-mutate algorithms.Here,a site is represented by using an undirected graph and a set of operations is designed to change the shape and location of sites during the search for possible solutions.These operations evolve randomly generated initial solutions into a set of optimal solutions to this type of problem;at the same time,the contiguity of a site is maintained and the 'holes' of the site are prevented to formation.This approach is applied to three different types of cost surfaces: uniform random,a conical and a deformed sombrero-like surface.The analyses are focused on a 128×128 grid of cells,where a facility is located at the center of the area;The number of cells for a site is fixed and set at 10.The results demonstrate the robustness and effectiveness of this PSO-based approach to geographical analysis and multi-objective site selection problems.This approach has also been tested in the city of Guangzhou,to search for the best locations for CBD.The results are also reasonable.The experiments have indicated that this approach is effective in solving this problem.It can successfully capture all the best solutions.The results can be used directly as the location selection by the decision-makers because these have been the best solutions.