摘要
空间优化选址是GIS空间决策分析的重要问题之一,指的是在一定地理区域内为一个或多个空间对象选定合适的位置,使某一指标或综合指标达到最优的过程。此问题常常涉及高维地理空间、海量数据、多个互相冲突的目标和限制条件,是NP-hard组合优化问题。传统的优化方法,如穷举法、盲目搜索法等难以取得很好的效果。本文提出了将空间结构知识和关联模式融合到多目标遗传算法,结合GIS强大的空间数据处理、空间查询、空间分析和可视化等技术进行空间优化决策。
首先,从影响空间优化选址的定性因素和定量因素两方面着手,分别进行不确定的定性因素分析、量化及建模和确定性的定量因素分析及建模,利用粗集的知识将定性因素定量化的表达为一个综合效用因子并引入到定量因素的数学模型中,进行空间优化选址的影响因素建模。
其次,在对多目标遗传算法的原理、内部机制的分析基础上,建立融合空间结构知识和关联模式的NSGA-II、SPGA2和PESA-II三种多目标空间优化选址模型。同时,将GIS与应用模型紧密无缝集成,并构建不同的评价体系评价不同模型的性能。
最后,设计和开发基于ArcGIS Engine9.3+C#.net的GIS桌面应用系统,并进行大型不规则区域的北京市医院空间优化选址应用实践。实验结果证明,空间结构知识和关联模式对空间优化选址有较大的影响,本文所建模型在保持稳定性、鲁棒性的基础上,生成的Pareto最优集的收敛性更好、搜索到的最优位置的分布范围更广,三种模型的性能较单纯多目标算法模型均有不同程度的提高。
Spatial optimal location is one of the classic problems in the realm of GIS. It selected the most appropriate location for site or sites in a certain geographic area and made performance or a combination of performances to reach optimum. This problem usually involves high-dimensional geographical space, massive data, multiple conflicting objectives and constraints and the issue is a NP-hard combinatorial optimization problems. Thus, traditional methods such as brute-force, blindness search and etc. are infeasible to find the optimal solution. This paper demonstrates the method integration of the knowledge of spatial structure and association patterns into multi-objective genetic algorithm to executive spatial optimal decision based on GIS’s powerful spatial data processing, spatial query, spatial analysis and visualization and so on technology.
Firstly, the paper taking two basic aspects—qualitative and quantitative factors that affect the process of site location into account. Analysis, quantification and modeling of uncertainty qualitative factors, and deterministic quantitative factors analysis and modeling respectively, then quantified qualitative factors with a comprehensive utility factor using rough sets processing method and introduced the comprehensive utility factor into mathematical model of quantitative factors so as to realize the modeling process
Secondly, based on the analysis of principle and internal processes of multi-objective genetic algorithm, we established the three models about multi-objective spatial optimal location, that is to say NSGA-II, SPGA2 and PESA-II that integration of the knowledge of spatial structure and association patterns. Meanwhile, we reached the compacted seamless integration of GIS and application model.
Finally, design and development GIS desktop application system based on ArcGIS Engine9.3 + c #.net and conduct the experiments about spatial optimal location of Beijing hospitals in large irregular area. Experimental results show that the knowledge of spatial structure and association patterns has great influence on spatial optimal location, models created in the paper can be convergent to Pareto optimality sets more effectively, the distribution of the optimal location is better and improved performance than pure multi-objective genetic algorithms while maintained stability and robustness of model.
引文
[1] Aerts J.C.J.H..Using simulated annealing for resource allocation[J]. International Journal of Geographical Information Science, 2002.
[2] Mavin A.A., Sukran N.N. and Basheer M. K.. An empirical comparison of Tabu Search, Simulated Annealing, and Genetic Algorithms for facilities location problems[J]. International journal of Production Economics, 2006, 104:742–754.
[3] Liu N., Huang B., and Chandramouli M.. Optimal Siting of Fire Stations Using GIS and ANT Algorithm[J]. journal of computing in civil engineering, 2006.
[4] Du G.M., Chen X.X., Li X.. Particle Swarm Optimization Approach for Location of Supermarkets [J].Computer Engineering and Applications, 2006.
[5] LI X., GAR-ON YEH. Integration of genetic algorithms and GIS for optimal location search[J]. International Journal of Geographical Information Science, 2005,V19:581-601.
[6]黎夏,叶嘉安.遗传算法和GIS结合进行空间优化决策[J].地理学报,2004,59(5).
[7]杜国明,陈晓翔,黎夏.基于微粒群优化算法的空间优化决策[J].地理学报,2006.
[8]黎海波,黎夏等.多目标粒子群算法与选址中的形状优化[J].遥感学报,2008,12(5).
[9]何晋强,黎夏,刘小平,陶嘉.蚁群智能及其在大区域基础设施选址中的应用[J].遥感学报,2009.
[10]刘萌伟,黎夏.基于Pareto多目标遗传算法的公共服务设施优化选址研究——以深圳市医院选址为例[J].热带地理,2010,06.
[11] Brookes C.J.. A genetic algorithm for designing optimal patch configurations in GIS [J]. International Journal of Geographical Information Science,2001,V15(6): 539-559.
[12] Jaramillo J.H., Bhaduryand J. and Batta R.. On the use of genetic algorithms to solve location problems[J]. Computers & Operations Research,2002,V29(6):761-779.
[13] Stewart T.J., Janssen R. and Herwijnen M.B.. A genetic algorithm approach to multi-objective land use planning[J]. Computers & Operations Research,2004.
[14]Ducheyne E.I., Wulf R.R.D.and Baets B.D.. A spatial approach to forest-management optimization: linking GIS and multiple objective genetic algorithms [J]. International Journal of Geographical Information Science,2006,V20(8):917–928.
[15]Park S.Y., choiand J.H., Wang S.. Design of a water quality monitoring network in a largeriver system using the genetic algorithm.Ecological Modelling[J]. Ecological Modelling,2006:289-297.
[16] Babaie-Kafaki S., et al., Solving Bus Terminal Location Problem Using Genetic Algorithm[J]. International Journal of Applied Science, Engineering and Technology, 2006.
[17] Zhang, L. and G. Rushton. Optimizing the size and locations of facilities in competitivemulti-site service systems[J]. Computers & Operations Research, 2008. 35: 327-338.
[18] Iannoni A.P., Morabito R.and Saydam C.. An optimization approach for ambulance location and the districting of the response segments on highways[J]. European Journal of Operational Research,2009:528-542.
[19] Xiao N., Bennett D.A. and Armstrong M.P.. Using evolutionary algorithms to generate alternatives for multi-objective site-search problems[J]. Environment and Planning, 2002,V34: 639- 656.
[20] Xiao N., Bennett D.A. and Armstrong M.P.. Interactive evolutionary approaches to multi-objective spatial decision making: A synthetic review[J]. Computers, Environment and Urban Systems, 2007, 31: 232–252.
[21]陈南祥,李跃鹏,徐晨光.基于多目标遗传算法的水资源优化配置[J].水利学报, 2006,36(3).
[22]包伟,姚建刚等.G I S支持下基于NSGA-Il算法的火电厂多目标选址[J].电力系统保护与控制,2008,36(22).
[23]丁胜祥,董增川等.基于Pareto强度进化算法的供水库群多目标优化调度[J].水科学进展,2008,9:679-684.
[24]阎志伟,田菁,李汉铃.基于改进的NSGA-Ⅱ算法的区域覆盖卫星星座优化[J].空间科学学报,2004,24(1).
[25]涂启玉,基于小生境遗传算法的区域水资源优化配置[J].水利科技与经济,2008,14(3):67-69.
[26]谢涛,陈火旺.多目标优化与决策问题的演化算法[M].中国工程科学, 2002,4(2).
[27]谢涛,陈火旺,康立山.多目标优化的演化算法[M].计算机学报,2003, 26(8).
[28]周明,孙树栋.遗传算法原理及其应用[M].北京:国防工业出版社,1999.
[29] Xiao, N., Geographic Optimization Using Evolutionary Algorithms[J]. 2004.
[30] Xiao, N., An Evolutionary Algorithm for Site Search Problems[J]. Geographical Analysis 2006. 38: p. 227–247
[31] Xiao N.. A Unified Conceptual Framework for Geographical Optimization Using Evolutionary Algorithms[J]. Annals of the Association of American Geographers, 2008, 4: 795- 817.
[32] Coello C.A.C., Van V.D.. Lamont GB. Evolutionary Algorithms for Solving Multi-Objective Problems. New York:Kluwer Academic Publishers, 2002.
[33] Coello C.A.C., Computacion S.d. and Zacatenco C.S.P..Twenty years of evolutionary multi-objective optimization:A historical view of the field. IEEE Computational Intelligence Magazine,2006.
[34] Coello C.A.C., Van V.D., Lamont GB. Evolutionary Algorithms for Solving Multi-Objective Problems. 2nd ed., New York: Springer-Verlag, 2007.
[35] Zitzler E..Evolutionary algorithms for multiobjective optimization: Methods and applications. 1999.
[36] Schaffer J.D.. Multiple objective optimization with vector evaluated genetic algorithms[C].Proceedings of the first international conference on genetic algorithm. Lawrence Erlbaum,1985:93-100.
[37] Borges C.H.C. and Barbosa H.J.C.. A Non-generational Genetic Algorithm for Multi-objective Optimization[C].Congress on Evolutionary Computation,2000.
[38] Fonseca M.C. and Fleming P.J.. Genetic Algorithms for Multiobjective Optimization:Formulation, Discussion and Generalization[C]. in the fifth international conference on genetic algorithms,1993.
[39] Fonseca M.C. and Fleming P.J.. Multiobjective optimization and multiple constraint handling with evolutionary algorithmsⅡ:Application Example[J]. IEEE Transactions on Systems, Man and Cybernetics, 1998.
[40] Horn J., Nafpliotis N., Goldberg D.E.. A niched pareto genetical gorithm for multiobjective optimization[C]. Proceeding of the First IEEE Conference on Evolutionary Computation (CEC’1994),1994:82-87.
[41] Deb.Wiley, K. and Chichester. Multi-Objective Optimization using Evolutionary Algorithms. 2001.
[42] Deb K., Pratap A.. A fast and elitist multi-objective genetic algorithm:NSGA-II[J]. IEEE Trans. on Evolutionary Computation, 2002,6(2):182?197.
[43] Pradyumn Kumar Shukla , Kalyanmoy Deb. On finding multiple pareto optimal solutions using classical and evolutionary generating methods[J]. European Journal of Operational Research ,2007 , 181 :1 630 - 1 652.
[44] Kalyanmoy Deb , Santosh Tiwari . Omni - optimizer : A generic evolutionary algorithm for single and multi - objective optimization[J]. European Journal of Operational Research , 2008 ,185:1062 - 1087.
[45]Corne D.W., Knowles J.D., Oates M.J.. The pareto envelope-based selection algorithm for multiobjective optimization[A].Marc Schoenauer,Kalyanmoy Deb,Gunter Rudolph,etal.(editors) [C].P roceedings of the Parallel Problem Solving from Nature VI Conference Springer,2000,839-848
[46]Corne D.W., Jerram N.R. et al. PESA-II:Region- based selection in evolutionary multiobjective optimization [A].Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001)[C]. Morgan Kaufmann Publishers, 2001:283-290.
[47]Zitzler E. and Thiele L.. An evolutionary algorithm for multiobjective optimization:The strength pareto approach[R]. Swiss Federal Institute of Technology,TIK-Report,1998.
[48] Zitzler E, Thiele L. Multi-Objective evolutionary algorithms: A comparative case study and the strength Pareto approach[J]. IEEE Trans. on Evolutionary Computation, 1999,3(4):257?271.
[49] Zitzler E., Deb K.and Thiele L.. Comparison of Multi-objective Evolutionary Algorithms:Empirical Results[J]. Evolutionary Computation, 2000,8(2):173-195.
[50] Zitzler E., Laumanns M. and Thiele L.. SPEA2:Improving the Strength Pareto Evolutionary Algorithm[J].EUROGEN,2001.
[51]徐磊.基于遗传算法的多目标优化问题的应用与研究[D].长沙:中南大学,2007.
[52]王向慧,连志春等.基于Pareto最优概念的多目标进化算法研究[J].计算机工程与应用,2008,9.
[53]唐云岚,赵青松等.Pareto最优概念的多目标进化算法综述[J].计算机科学,2008,10.
[54]公茂果,焦李成等.进化多目标优化算法研究[J].软件学报,2009,20(2):271-289.
[55]李晓翠,张跃鹏,金澄.GIS在空间选址中的应用现状分析[J].测绘科学与工程,2006,26(4).
[56]李晓翠GIS技术在空间选址中的应用[D] .西安:长安大学,2007.
[57]李晓翠,张跃鹏,金澄.空间选址关键因素及其建模研究[J].测绘科学,2009,34(1).
[58]宋广飞.GIS在购物中心选址中的应用研究[D].大连:大连理工大学.2009.
[59]祁向前.GIS空间分析功能在超市选址中的应用[J].测绘科学,2008,33(6): 223-225.
[60]刘小林,温程杰,张江水.运用GIS进行空间选址分析[J].测绘与空间地理信息,2010,33(4) .
[61]戴晓爱,仲凤呈等.GIS与层次分析法结合的超市选址研究与实现[J].测绘科学, 2009,34(1):184-186.
[62]黎夏,刘凯.GIS与空间分析——原理与方法[M].北京:科学出版社.2006.
[63]黎夏,刘小平,李少英.智能式GIS与空间优化[M].北京:科学出版社.2010.
[64]李军利,宋亚杰.基于ArcEngine的空间权重矩阵的实现与应用[J].测绘与空间地理信息,2010,33(3).
[65]潘海燕,程朋根,肖根如.基于ArcObjects的空间权重矩阵的建立与实现[ J ] .测绘科学,2007,32 (6):130 -133.
[66] Li M.Q., Zheng J.H., Xiao G.X.. Uniformity assessment for evolutionary multi-objective optimization [C ].In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC’2008) , Hongkong, 2008, 6:625-632.
[67] Tong D.Q., Murray A.T.,Xiao N.. Heuristics in Spatial Analysis: A Genetic Algorithm for Coverage Maximization[J].Annals of the Association of American Geographers,2009,99(4):698-711.
[68]韩鹏,王泉等.地理信息系统开发——ArcEngine方法[M].武汉:武汉大学出版社,2008.
[69]任峰,刘应宗,牛东晓.热电厂优化选址研究[J].计算机工程与应用,2010,46(23):212-214.
[70]刘清.Rough集和Rough推理[M] .北京:北京科学出版社,2003.
[71] Ronald G.M., T M.C..Constrained location of competitive facilities in the plane[J]. Computers & Operations Research ,2005 (32): 359–378.