多叉树蚁群算法及在区位选址中的应用研究

doi:10.11821/xb201102013

地理学报 ›› 2011, Vol. 66 ›› Issue (2): 279-286.doi: 10.11821/xb201102013

• GIS应用 • 上一篇

多叉树蚁群算法及在区位选址中的应用研究

赵元, 张新长, 康停军

中山大学地理科学与规划学院，广州510275

收稿日期:2010-02-24 修回日期:2010-05-30 出版日期:2011-02-20 发布日期:2011-02-20
通讯作者: 张新长(1957-), 男, 教授, 博士生导师，从事城市地理信息系统与土地利用时空模拟方面的研究, 发表有关论文130 多篇。E-mail:eeszxc@mail.sysu.edu.cn
作者简介:赵元(1977-), 男, 博士研究生, 主要从事地理信息建模与土地利用时空结构演变方面的研究。 E-mail: giszy@163.com
基金资助:
国家自然科学基金项目(40971216；41071246)

An Ant Colony Algorithm Based on Multi-way Tree for Optimal Site Location

ZHAO Yuan, ZHANG Xinchang, KANG Tingjun

School of Geography and Planning, Sun Yat-sen University, Guangzhou 510275, China

Received:2010-02-24 Revised:2010-05-30 Online:2011-02-20 Published:2011-02-20
Supported by:
National Natural Science Foundation of China, No.40971216；41071246

摘要/Abstract

摘要： 本文提出了基于多叉树蚁群算法(ant colony optimization based on multi-way tree) 的区位选址优化方法。在多目标和大型空间尺度约束条件下，地理区位选址的解决方案组合呈现海量规模、空间搜索量庞大，难以求出理想解。基于多叉树的蚁群算法对地理空间进行多叉树划分，在多叉树的层上构造蚂蚁路径(ant path)，让蚂蚁在多叉树的搜索路径上逐步留下信息素，借助信息素的通讯来间接协作获得理想的候选解。采用该方法用于广州市的地理区位选址，取得良好结果。实验结果表明：采用基于多叉树的蚁群算法，改善了蚂蚁在空间搜索能力，适合求解大规模空间下的区位选址问题。

关键词: 区位选址, 多叉树, 蚁群算法, 广州

Abstract: Site location by brute-force method is difficult for optimization due to massive spatial data and huge solution space under the constraint condition of multi-objective and large spatial resolutions. In this study, an improved ant colony optimization (ACO) based on multi-way tree is introduced to solve site location problem. Better solutions can be obtained swiftly according to the density of pheromone the ants leave on the search paths constructed in nested subspaces divided by means of the multi-way tree algorithm. First, the algorithm derived from ACO is aiming to search for an optimal path in space regardless of initial distribution, based on the behavior of ants seeking a path at a specific probability. Second, the multi-way tree algorithm's growth rate between search size and spatial scale is logarithmic, so the cost of searching increases slowly as the size of its input grows. The study area, located in Guangzhou city, is a densely populated region. The raster layers have a resolution of 92 m× 92 m with a size of 512 × 512 pixels. This optimization problem consists of two factors: population distribution and spatial distance. Comparison experiment between ACO based on multi-way tree and the simple search algorithm indicates that this method can produce closely related results with a greater convergence rate and spend less computing time. In conclusion, the proposed algorithm is important and suitable for solving site search problems.

Key words: site location, multi-way tree, ant colony optimization, Guangzhou

赵元, 张新长, 康停军. 多叉树蚁群算法及在区位选址中的应用研究[J]. 地理学报, 2011, 66(2): 279-286.

ZHAO Yuan, ZHANG Xinchang, KANG Tingjun. An Ant Colony Algorithm Based on Multi-way Tree for Optimal Site Location[J]. Acta Geographica Sinica, 2011, 66(2): 279-286.

参考文献

[1] Kariv O, Hakimi S L. An algorithmic approach to network location problems (I): The p-centers. SIAM Journal AppliedMathematics, 1979, 37(3): 513-538.

[2] Kariv O, Hakimi S L. An algorithmic approach to network location problems (II): The p-medians. SIAM JournalApplied Mathematics, 1979, 37(3): 539-560.

[3] Cooper L. Location-allocation problems. Operations Research, 1963, 11: 331-343.

[4] Cooper L. Solutions of generalized location equilibrium problems. Journal of Research Science, 1967, 7: 1-18.

[5] Li Xia, Yeh A G O. Optimal spatial search using genetic algorithms and GIS. Acta Geographica Sinica, 2004, 59(5):745-753. [黎夏, 叶嘉安. 遗传算法和GIS结合进行空间优化决策的研究. 地理学报, 2004, 59(5): 745-753.]

[6] Yang Fengmei, Hua Guowei, Deng Meng et al. Some advances of the researches on location problems. OperationsResearch and Management Science, 2005, 14(6): 1-7. [杨丰梅, 华国伟, 邓猛等. 选址问题研究的若干进展. 运筹与管理, 2005, 14(6): 1-7.]

[7] Tabari M, Kaboli A, Aryanezhad M B et al. A new method for location selection: A hybrid analysis. AppliedMathematics and Computation, 2008, 206(2): 598-606.

[8] Mladenovi? N, Brimberg J, Hansen P et al. The p-median problem: A survey of metaheuristic approaches. EuropeanJournal of Operational Research, 2007, 179(3): 927-939.

[9] Fathali J. A genetic algorithm for the p-median problem with pos/neg weights. Applied Mathematics and Computation,2006, 183(2): 1071-1083.

[10] Brookes C J. A genetic algorithm for designing optimal patch configurations in GIS. International Journal ofGeographical Information Science, 2001, 15(6): 539-559.

[11] Aerts C J H, Heuvelink G B M. Using simulated annealing for resource allocation. International Journal ofGeographical Information Science, 2002, 16(6): 571-587.

[12] Lockwood C, Moore T. Harvest scheduling with spatial constraints: A simulated annealing approach. Canadian Journalof Forest Research, 1993, 23(3): 468-478.

[13] Bettinger P, Sessions J, Boston K. Using tabu search to schedule timber harvests subject to spatial wildlife goals forbig game. Ecological Modelling, 1997, 94(2): 111-123.

[14] Brumelle S, Granot D, Halme M et al. A tabu search algorithm for finding good forest harvest schedules satisfyinggreenup constraints. European Journal of Operational Research, 1998, 106(2): 408-424.

[15] Dorigo M, Stützle T. Ant Colony Optimization. London: The MIT Press, 2004: 65-67.

[16] Dorigo M, Gambardella L M. Ant colony system: A cooperative learning approach to the traveling salesman problem.IEEE Transaction on Evolutionary Computation, 1997, 1(1): 53-56.

[17] Dorigo M, Maniezzo V, Colorni A. Ant system: Optimization by colony of cooperating agents. IEEE Transactions onSystems, Man, and Cybernetics Part B, 1996, 26(1): 29-41.

[18] Dorigo M, Di C G, Gambardella L M. Ant algorithms for discrete optimization. Artificial Life, 1999, 5(3): 137-172.

[19] He Jinqiang, Li Xia, Liu Xiaoping et al. Ant colony algorithms for optimal site selection in large regions. Journal ofRemote Sensing, 2009, 13(2): 246-255. [何晋强, 黎夏, 刘小平等. 蚁群智能及其在大区域基础设施选址中的应用.遥感学报, 2009, 13(2): 246-255.]

[20] Raphael F, Bentley J L. Quad trees: A data structure for retrieval on composite keys. Acta Informatica, 1974, 4(1): 1-9.

[21] Zhao Wenji, Hu Zhuowei, Chen Yongliang et al. Quadtree-based three-dimensional visualization for thegeomorphologic data in multiple resolutions. Journal of Image and Graphics, 2007, 12(8): 1457-1462. [赵文吉, 胡卓玮, 陈永良等. 基于四叉树的多分辨率地形数据3 维可视化. 中国图象图形学报, 2007, 12(8): 1457-1462.]

[22] Chen Ye. Ant colony optimization algorithm for continuous function. Journal of Sichuan University: EngineeringScience Edition, 2004, 36(6): 117-120. [陈烨. 用于连续函数优化的蚁群算法. 四川大学学报: 工程科学版, 2004, 36(6): 117-120.]

多叉树蚁群算法及在区位选址中的应用研究

An Ant Colony Algorithm Based on Multi-way Tree for Optimal Site Location

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

[1]	安宁,冯秋怡,朱竑. 基于报业话语的广州非裔社区的空间想象分析[J]. 地理学报, 2019, 74(8): 1650-1662.
[2]	林荣平, 周素红, 闫小培. 1978年以来广州市居民职住地选择行为时空特征与影响因素的代际差异[J]. 地理学报, 2019, 74(4): 753-769.
[3]	杨莹,林琳,钟志平,欧莹莹,徐茜,蒙美昀,郝珊. 基于应对公共健康危害的广州社区恢复力评价及空间分异[J]. 地理学报, 2019, 74(2): 266-284.
[4]	吴蓉,黄旭,刘晔,李志刚. 广州城市居民地方依恋测度与机理[J]. 地理学报, 2019, 74(2): 379-393.
[5]	杨文越,曹小曙. 居住自选择视角下的广州出行碳排放影响机理[J]. 地理学报, 2018, 73(2): 346-361.
[6]	陈淳,袁振杰,朱竑. 城镇化背景下广州流动儿童对“家”空间的建构[J]. 地理学报, 2018, 73(12): 2440-2451.
[7]	周素红, 宋江宇, 宋广文. 广州市居民工作日小汽车出行个体与社区双层影响机制[J]. 地理学报, 2017, 72(8): 1444-1457.
[8]	谭章智, 李少英, 黎夏, 刘小平, 陈逸敏, 李威贤. 城市轨道交通对土地利用变化的时空效应[J]. 地理学报, 2017, 72(5): 850-862.
[9]	傅辰昊, 周素红, 闫小培, 柳林, 陈蔚珊. 广州市零售商业中心的居民消费时空行为及其机制[J]. 地理学报, 2017, 72(4): 603-617.
[10]	陶伟, 王绍续, 朱竑. 广州拾荒者的身体实践与空间建构[J]. 地理学报, 2017, 72(12): 2199-2213.
[11]	尹铎, 高权, 朱竑. 广州鳄鱼公园野生动物旅游中的生命权力运作[J]. 地理学报, 2017, 72(10): 1872-1885.
[12]	陶海燕, 潘中哲, 潘茂林, 卓莉, 徐勇, 鹿苗. 广州大都市登革热时空传播混合模式[J]. 地理学报, 2016, 71(9): 1653-1662.
[13]	周春山, 胡锦灿, 童新梅, 边艳. 广州市社会空间结构演变跟踪研究[J]. 地理学报, 2016, 71(6): 1010-1024.
[14]	朱竑, 李如铁, 苏斌原. 微观视角下的移民地方感及其影响因素——以广州市城中村移民为例[J]. 地理学报, 2016, 71(4): 637-648.
[15]	陈世莉, 陶海燕, 李旭亮, 卓莉. 基于潜在语义信息的城市功能区识别----广州市浮动车GPS时空数据挖掘[J]. 地理学报, 2016, 71(3): 471-483.