An Ant Colony Algorithm Based on Multi-way Tree for Optimal Site Location
An Ant Colony Algorithm Based on Multi-way Tree for Optimal Site Location
复制标题
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Kang Tingjun
中科院分区：
文献类型：
--
作者：
Kang Tingjun
在多目标、大空间分辨率的约束条件下，由于空间数据量大、解空间大，采用暴力破解方法进行站点定位难以优化。本文提出了一种改进的基于多路树的蚁群算法来解决选址问题。利用多路树算法划分嵌套子空间，根据蚁群在搜索路径上留下的信息素的密度，可以快速得到较好的解。首先，由蚁群算法衍生而来的算法是根据蚂蚁以特定概率寻找路径的行为，在空间中寻找一条不受初始分布影响的最优路径。其次，多路树算法的搜索规模与空间规模之间的增长率是对数的，因此搜索成本随着其输入规模的增长而缓慢增长。研究区位于广州市，是一个人口稠密的地区。光栅层的分辨率为92 mx92 m，尺寸为512 × 512像素。该优化问题包括两个因素：人口分布和空间距离。将基于多路树的蚁群算法与简单搜索算法进行对比实验，结果表明该方法收敛速度快，计算时间短，结果相关度高。综上所述，该算法适用于求解站点搜索问题。
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.