基于多目标遗传算法的空间优化选址方法研究

刘 玉，王海起，侯金亮，陈 冉，桂 丽

（1.中国石油大学（华东） 地球科学与技术学院，山东 青岛 266580；2.中国科学院寒区旱区环境与工程研究所 遥感与地理信息科学研究室，甘肃 兰州 730000）

空间优化选址是GIS领域的经典问题之一。空间选址是指在一定地理区域内为一个或多个选址对象选择或分配位置，使某一指标或一组指标达到最优的过程。该类问题常常涉及二维或高维的地理空间、大数据量、多个相互冲突的目标函数和多个限制条件，是NP-hard组合优化问题。与单目标优化问题不同，多目标优化问题常产生一组折衷解，并把这组折衷解定义为Pareto最优解集或非支配解集。因此，传统的优化方法（如brute-force法、盲目搜索法、邻域搜索法等）难以取得很好的效果。

模拟退火[1]、遗传算法[2]、粒子群优化[3]和蚁群算法[4]等智能启发式方法，因其出色的自动搜索能力而被用来解决选址问题。尽管这些方法可以搜索到最优解或近似最优解，但缺点是均通过特定的方式将多目标优化转化为单目标优化问题，忽略了多个目标之间的制约关系，容易漏掉那些实现了多目标最优而单目标不是最优的选址方案[5]；另外，这些方法也没有考虑GIS对象间的空间关系对选址的影响。因此，本文以改进的非支配排序遗传算法（NSGA-II）为基本算法，以选址涉及的服务人口、交通成本、道路可达性等空间因素定义多个目标函数，以表达空间相互作用的权重矩阵为基本形式，将空间信息融合在NSGA-II算法中，从而形成了GIS空间对象的多目标优化选址算法流程，并以山东省10个流行病监控点最优位置的选址为案例进行应用分析与对比研究。

1 改进的NSGA-II

NSGA是一种基于Pareto支配关系的多目标优化算法。它是一个非常有效的算法，但存在高计算复杂度、非精英策略、需设置共享参数等明显缺点。为克服上述缺点，Deb K[6]等提出了改进的NSGA- II。在NSGA- II中需确定每个解的支配解和被支配解，再执行快速排序，以确定每个解的非支配等级。对于具有相同非支配等级的解，定义拥挤距离来估计某个解周围的解密度，以取代适应度共享机制。NSGA- II根据非支配等级选择非支配解，当两个解具有相同的非支配等级时，优先选择拥挤距离较大的解。NSGA-II利用精英策略来保留最好的父个体和子个体，只需MN2（M为目标个数，N为种群大小）的计算复杂度。这些策略使得新一代种群比前一代更有效，且解的分布范围更好，从而收敛到真正的Pareto最优前沿。

2 研究方法和流程

将GIS信息与多目标遗传算法相结合以解决空间选址问题的技术流程如图1所示。

图1 空间优化选址的技术路线图

2.1 GIS空间数据处理

本文以多个流行病监控点的选址为例。疾病监控点作为对人类有益的服务设施，其最优位置的选择需遵循[7]：①平等性：需要反映公平与公正的理念，所有人都能享受该设施提供的服务，因此决策的制定应基于人口的分布情况；②成本有效性：确保每个人可享受服务的同时不能造成资源浪费；③可到达性：用户最大限度地接近服务点，即最小化交通费用或时间成本。基于以上原则，流行病监控点的选址与总服务人口、交通成本和道路可达性等空间因素相关。

2.2 定义目标函数[8-9]

1）最大化服务人口。N个选址点的总服务人口可定义为：

式中，xi、yi为第i个选址点的坐标；n为选址点总数；l为统计覆盖人口的邻域窗口；P'den(x, y)为动态人口密度；A0为每个栅格单元的面积为覆盖率的衰减函数；k为衰减函数的系数。

动态人口密度是在每确定一个选址点后将其覆盖的人口去掉重新计算获得的，一个位置好的选址方案应尽量覆盖最大的人口数/服务半径，即max fpop。

2）最小化交通成本。交通成本的定义为：

一个位置好的选址方案应尽量降低交通出行成本，即minfcost。

3）最小化道路接近度。道路接近度的定义为：

式中，Droad为选址点与道路之间的距离；r为道路因子系数。

一个位置好的选址方案应尽量接近道路，即minfroad。

2.3 染色体编码

空间最优选址问题，即在M1×M2个空间单元中找出n个设施的最优(x, y)坐标，故需设计染色体为n个选址设施的位置组合编码。染色体可有2n个基因，每个基因代表一个x或y坐标：

式中，(xi, yi)为第i个选址点的坐标，i=1, 2,…,n。

2.4 算法流程

融合空间信息的Spatial NSGA-II（SNSGA-II）算法详细步骤为：

1）种群初始化：随机产生n个染色体表示n个个体（即n个候选选址方案）。由染色体的编码形式可知，每个个体包含n个选址点。

2）建立空间权重矩阵：定义对称的二进制空间权重矩阵Wn×n，表示n个选址点之间的相互影响[10]。本文采用两个选址点间的欧氏距离作为权重测度，当第i选址点和第j选址点的距离在给定的范围（该范围由实际问题决定）内时，空间权重矩阵对应的元素Wij=1，说明第i选址点和第j选址点之间存在相互影响；否则，Wij=0说明不存在相互影响。此外，将W所有的主对角元素设置为0。

3）将空间信息融合到NSGA-II中：加权平均每个选址点与邻域选址点的坐标，作为该选址点的新位

置[11]。具体方法为：令为邻域选址点x、y坐标的平均值，即为选址点(xi, yi)唯一的

虚拟邻居，(xi, yi)与(xi, yi)之间相关系数的计算公式为：

则选址点新的位置(x'i, y'i)为：

用新坐标表示每个个体，形成原始种群。

4）非支配排序：以前述的3个目标函数fpop、fcost、froad为适应度评价函数，按非支配次序和拥挤距离将个体分类。

5）遗传操作：定义匹配池（大小为n/2），采用锦标赛法选择父种群个体，对父种群个体进行交叉和变异操作，得到子种群。

6）合并父种群和子种群，通过精英机制选择最好的n个个体形成新一代的父种群。

7）判断迭代终止条件，若满足，则可视化输出选址结果；否则，转至步骤3）。

2.5 可视化输出结果

利用GIS平台提取上述算法得到的栅格数据选址结果，将栅格数据转化为点数据，并显示在地图上。

3 应用实例

3.1 研究区和空间数据

以山东省作为不规则的大尺度区域，给出10个流行病监控点的最优位置。选取山东省人口密度数据，并在选址过程中排除无效栅格单元，并以山东省内铁路网为道路数据，计算各栅格单元到铁路的距离，从而获取道路接近度（图2）。

图2 道路接近度图

3.2 参数设置

算法采用Matlab 实现，在Intel DUO CPU 2.66GHz环境下运行程序，选择的种群大小为200，最大迭代次数为500，交叉率为0.98，变异率为0.01，衰减函数的系数为0.05，道路因子为0.05，邻域窗口的大小为15。迭代终止条件是达到最大迭代次数或非支配等级最高的个体不再发生变化。另外，算法还采用了谢菲尔德大学Matlab遗传算法工具箱中的一些函数。

3.3 实验结果与分析

比较标准遗传算法（GA）、融合空间信息的遗传算法（SGA）、NSGA-II和SNSGA-II的效果，重复运行3 次，4种算法的实验结果见表1和图3～6。

表1 4种算法的运行时间、解的集中趋势（均值）和离中趋势（标准差）

使用GA的过程、参数设置等与黎夏[8]等提出的方法完全相同，采用相同的权重系数将3个目标函数组合为单一的目标函数，并将该目标函数作为适应度评价函数。图3a表明迭代次数达到180次后，标准适应度达到了峰值0.853 8；迭代次数达到260次时迭代过程终止。

SGA使用与GA相同的设置，并采用空间信息融合方法。图4a表明迭代次数达到230次后，标准适应度达到了峰值0.861 7；迭代次数达到300次时迭代过程终止。

由表1可知，GA、SGA的效率相对较低，尤其是SGA算法，其平均运行时间为57 711 s。NSGA- II、SNSGA-II的效率有显著提升，平均运行时间约为20 000 s，得到的中心位置也更接近研究区域的中心（研究区域的中心坐标为（236, 328））；但SNSGA-II算法具有更大的离中趋势，说明解集的分布范围更广、多样性更好。

比较图3～6的b图可知，4种选址结果中有6个选址位置接近或重合，这说明本文提出方法的稳定性是可以接受的。另外，图3、图5的一些选址点彼此非常靠近，可能是陷入了局部最优，而这种现象在融合空间信息的SGA、SNSGA-II算法中是不存在的。

综上所述，多目标遗传算法可得到更加可靠的结果，空间结构对选址结果也有较大影响。在GIS空间优化选址过程中，采用多目标优化算法并考虑地理空间信息可得到更优的结果。

图3 GA迭代情况和选址结果

4 结 语

在考虑空间因素的基础上，将GIS选址问题作为多目标优化问题，可获取协调多个目标准则的一组均衡解。实际应用表明，融合空间知识的多目标遗传算法可有效解决复杂的空间优化选址问题，不仅可收敛到Pareto最优集，而且解集的分布性更好，算法也具有很好的稳定性。然而，本文案例仅选择了10个，选址点就运行了数小时，这将限制算法的实用性；另外，如何在多目标优化算法中更好地融合空间特征和约束信息也是需重点研究的问题之一。

图4 SGA迭代情况和选址结果

图5 NSGA-II迭代和选址结果

图6 SNSGA-II迭代和选址结果

[1] Aerts J C J H, Heuvelink G B M. Using Simulated Annealing for Resource Allocation[J]. International Journal of Geographical Information Science,2002,16(6):571-587

[2] 黎夏,叶嘉安.遗传算法和GIS结合进行空间优化决策[J].地理学报,2004,59(5):745-753

[3] 杜国明,陈晓翔,黎夏.基于微粒群优化算法的空间优化决策[J].地理学报,2006,61(12):1 290-1 298

[4] 何晋强,黎夏,刘小平,等.蚁群智能及其在大区域基础设施选址中的应用[J].遥感学报,2009,13(2):246-256

[5] 公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究[J].软件学报,2009,20(2):271-289

[6] Deb K, Pratap A, Agarwal S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation,2002,6(2):182-197

[7] 宋广飞.GIS在购物中心选址中的应用研究[D].大连:大连理工大学,2008

[8] LI X, Yeh A G O. Integration of Genetic Algorithms and GIS for Optimal Location Search[J]. International Journal of Geographical Information Science,2005,19(5):581-601

[9] LI X, HE J Q, LIU X P. Intelligent GIS for Solving Highdimensional Site Selection Problems Using ant Colony Optimization Techniques[J]. International Journal of Geographical Information Science,2009,23(4):399-416

[10] 王海起,王劲峰.一种基于空间邻接关系的k-means聚类改进算法[J].计算机工程,2006,32(21):50-51

[11] HU T M, Sung S Y. Data Fusion in Radial Basis Function Networks for Spatial Regression[J]. Neural Processing Letters,2005,21(2):81-93