并行蚁群算法及其在区位选址中的应用  

A Parallel Ant Colony Optimization Algorithm for Site Location

作　　者：赵元[1] 张新长[1] 康停军[1] 

机构地区：[1]中山大学地理科学与规划学院,广东广州510275

出　　处：《测绘学报》2010年第3期322-327,共6页Acta Geodaetica et Cartographica Sinica

基　　金：国家自然科学基金(40971216)

摘　　要：提出基于多叉树并行蚁群算法的区位选址优化方法。算法依据蚁群算法具有的并行特性,采用GPU(graphicprocessing unit,图形处理器)并行运算技术,对地理空间进行多叉树划分,收集蚂蚁在多叉树层间旅行时逐步留下的信息素信息,进行路径选优获得理想的候选解,从而为解决平面空间资源优化配置问题提供新的思路。实验结果表明,与普通蚁群算法相比,采用基于多叉树搜索的并行蚁群算法,能够发挥蚁群算法的并行特征,在短时间内求得较为理想的解,适合计算大区域的空间资源配置问题。An improved parallel ant colony optimization based on multiway tree is introduced to solve p-median site location problem.To take advantage of ant colony optimization and GPU parallel computing,the raster space is divided by the multiway tree and the ant paths are constructed on the nested subspace.An ideal solution can be obtained by the indirect communication of pheromone quickly.The study area is located in Guangzhou city,a densely populated region.This optimization problem considers the condition of population distribution and spatial distance.The raster layers have a resolution of 92×92 m2 with a size of 512×512 pixels.A comparison experiment is conducted between the multiway tree ACO and simple search algorithms.Experiments indicate that this multiway tree ACO method can produce similar results but use lesser computation time,have better performance in convergence precision compared with the simple search algorithms.In conclusion,the proposed algorithm is important and suitable for solving site search problems.

关 键 词：多叉树 蚁群算法 并行运算 区位选址 GPU通用运算 

分 类 号：P208[天文地球—地图制图学与地理信息工程]