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

• GIS应用 • 上一篇    

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

赵元, 张新长, 康停军   

  1. 中山大学地理科学与规划学院,广州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   

  1. 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

摘要: 本文提出了基于多叉树蚁群算法(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