D0I:10.133745.issn1001-053x.2013.07.017 第35卷第7期 北京科技大学学报 Vol.35 No.7 2013年7月 Journal of University of Science and Technology Beijing Jul.2013 一种基于粒子群参数优化的改进蚁群算法及其应用 张超，李擎)凶，陈鹏)，杨守功)，尹怡欣) 1)北京科技大学自动化学院，北京1000832)中国科学院国家天文台，北京100012 ☒通信作者，E-mail:liqing@ies.ustb.edu.cm 摘要针对现有基于粒子群参数优化的改进蚁群算法耗时较大的问题，提出了一种新的解决方案.方案中采用一种全 局异步与精英策略相结合的信息素更新方式，同时合理减少蚁群算法被粒子群算法调用一次所需的迭代代数.对日本旭 川垃圾场巡查机器人路径规划问题仿真求解的结果表明，与其他算法相比，该改进算法具有比较明显的速度优势 关键词粒子群算法：蚁群算法：机器人：路径规划：旅行商问题 分类号TP181 Improved ant colony optimization based on particle swarm optimiza- tion and its application ZHANG Chao),LI Qing),CHEN Peng?),YANG Shou-gong),YIN Yi-rin!) 1)School of Automation,University of Science and Technology Beijing,Beijing 100083,China 2)National Astronomical Observatories,Chinese Academy of Sciences,Beijing 100012,China Corresponding author,E-mail:liqingaies.ustb.edu.cn ABSTRACT This article introduces a novel algorithm to solve the large time-consuming problem of the existing improved ant colony optimization (ACO)based on particle swarm optimization(PSO).A new pheromone update method which combines the global asynchronous feature and elitist strategy was used in the algorithm.Moreover,the iteration steps of ACO invoked by PSO were reasonably reduced.The algorithm was applied to solve the path planning problem of landfill inspection robots in Asahikawa,Japan.It is shown that the algorithm has a better performance in search speed compared with other algorithms recently reported. KEY WORDS particle swarm optimization;ant colony optimization;robots;path planning;traveling salesman problem 目前，蚁群算法已广泛地应用于多种组合优化 成果r-周 及控制系统领域的问题，如路由优化)、模糊神经 本文提出了一种新的基于粒子群参数优化的 控制回、函数优化周、车辆调度【-、图着色同等. 改进蚁群算法.该算法通过采用全局异步与精英策 在蚁群算法中，参数的选取较大地依赖于实验者的 略相结合的信息素更新方法、减少粒子群算法中每 个人经验，人为试凑选取参数的方式极大地影响着 个粒子调用蚁群算法迭代代数等方式大大降低了算 算法的效率和智能性.一旦参数选取不当，蚁群算 法的迭代规模，减小了时间成本 法会出现未成熟收敛等问题，制约了蚁群算法发挥 其最好的性能.因此蚁群算法参数优化，一直是国 1基于粒子群参数优化改进蚁群算法的提出 内外学者研究的热点问题.一些研究人员尝试应用 本文所提基于粒子群参数优化的改进蚁群算 粒子群算法优化蚁群算法中的参数，并取得了一些 法的步骤如下， 收稿日期：2012-04-11 基金项目：教育部第36批“留学回国人员科研启动基金”资助项目(1341)：国家自然科学基金资助项目(60374032)：北京市重点 学科建设项目(XK100080537)
第 35 卷 第 7 期 北 京 科 技 大 学 学 报 Vol. 35 No. 7 2013 年 7 月 Journal of University of Science and Technology Beijing Jul. 2013 一种基于粒子群参数优化的改进蚁群算法及其应用 张 超 1)，李 擎 1) ，陈 鹏 2)，杨守功 1)，尹怡欣 1) 1) 北京科技大学自动化学院, 北京 100083 2) 中国科学院国家天文台，北京 100012 通信作者，E-mail: liqing@ies.ustb.edu.cn 摘 要 针对现有基于粒子群参数优化的改进蚁群算法耗时较大的问题，提出了一种新的解决方案. 方案中采用一种全 局异步与精英策略相结合的信息素更新方式，同时合理减少蚁群算法被粒子群算法调用一次所需的迭代代数. 对日本旭 川垃圾场巡查机器人路径规划问题仿真求解的结果表明，与其他算法相比，该改进算法具有比较明显的速度优势. 关键词 粒子群算法；蚁群算法；机器人；路径规划；旅行商问题 分类号 TP181 Improved ant colony optimization based on particle swarm optimization and its application ZHANG Chao1), LI Qing1) , CHEN Peng2), YANG Shou-gong1), YIN Yi-xin1) 1) School of Automation, University of Science and Technology Beijing, Beijing 100083, China 2) National Astronomical Observatories, Chinese Academy of Sciences, Beijing 100012, China Corresponding author, E-mail: liqing@ies.ustb.edu.cn ABSTRACT This article introduces a novel algorithm to solve the large time-consuming problem of the existing improved ant colony optimization (ACO) based on particle swarm optimization (PSO). A new pheromone update method which combines the global asynchronous feature and elitist strategy was used in the algorithm. Moreover, the iteration steps of ACO invoked by PSO were reasonably reduced. The algorithm was applied to solve the path planning problem of landfill inspection robots in Asahikawa, Japan. It is shown that the algorithm has a better performance in search speed compared with other algorithms recently reported. KEY WORDS particle swarm optimization; ant colony optimization; robots; path planning; traveling salesman problem 目前，蚁群算法已广泛地应用于多种组合优化 及控制系统领域的问题，如路由优化 [1]、模糊神经 控制 [2]、函数优化 [3]、车辆调度 [4−5]、图着色 [6] 等. 在蚁群算法中，参数的选取较大地依赖于实验者的 个人经验，人为试凑选取参数的方式极大地影响着 算法的效率和智能性. 一旦参数选取不当，蚁群算 法会出现未成熟收敛等问题，制约了蚁群算法发挥 其最好的性能. 因此蚁群算法参数优化，一直是国 内外学者研究的热点问题. 一些研究人员尝试应用 粒子群算法优化蚁群算法中的参数，并取得了一些 成果 [7−8] . 本文提出了一种新的基于粒子群参数优化的 改进蚁群算法. 该算法通过采用全局异步与精英策 略相结合的信息素更新方法、减少粒子群算法中每 个粒子调用蚁群算法迭代代数等方式大大降低了算 法的迭代规模，减小了时间成本. 1 基于粒子群参数优化改进蚁群算法的提出 本文所提基于粒子群参数优化的改进蚁群算 法的步骤如下. 收稿日期：2012-04-11 基金项目：教育部第 36 批 “留学回国人员科研启动基金” 资助项目 (1341)；国家自然科学基金资助项目 (60374032)；北京市重点 学科建设项目 (XK100080537) DOI:10.13374/j.issn1001-053x.2013.07.017
.956 北京科技大学学报 第35卷 Stepl初始一定数量的三维粒子群粒子B6, 粒子所对应的参数值反馈回蚁群算法，蚁群算法的 B,…,Pn.一个粒子对应于一组p、a和B 求解结果最优，则称这个粒子为最优粒子.最优粒 参数，粒子在解空间中的位置即为参数值，记为 子所对应的一组参数值表明该粒子在解空间中的位 x:(工0，x1,x2).与位置坐标相对应，粒子在解空 置，即最优粒子位置.记每个粒子当前找到的最优 间中具有三个方向的移动速度，记为V(Vo,V1, 粒子位置为Pest,整个种群当前所找到的最优粒子 V2) 位置为Gbest·Pbest和Gbest的适应度评价值即为 Step2将当前每个粒子对应的参数值反馈回 蚁群算法求得路径的长度，路径长度越小参数质量 蚁群算法.应用这组参数调用蚁群算法X代(X 越好. 取值范围为3,5)⑨后，保留环境中的信息素，并根 Step4得到更新后的Pbest和Gbest后，按照 据当前求解结果（即蚂蚁遍历排列）更新信息素.蚁 群算法采用全局异步与精英策略相结合的信息素更 Vi(k+1)=wVi(k)+cir1(Pbest.i-zi(k))+ 新方式.该方式的信息素量不随蚁群算法迭代代数 的增加而变化，当且仅当出现了具有更强适应度的 c2r2(Gbest -Ti(k)) (6) 解时，才对信息素进行更新，并对该全局最优解经 更新粒子的速度，按照 过的路径进行信息素加强.信息素更新公式如下所 示： Ti(k+1)=工(k)+V(k+1) (7) △()= 更新粒子的位置.式中：w为惯性权重：C1和c2为 Q/Gk,当路径[i,引为最优路径上的片段时； 两个常数，C1调节粒子向自身最好位置靠近的权 0,其他 重，c2调节粒子向全局最好位置靠近的权重，c1和 (1) c2通常在0~2间取值：r1和T2为两个相互独立的 T(t+1)=(1-p)r1(t)+△T(t). (2) 随机函数：V为粒子i在第k代的速度：x()为 式中：△(t)表示本次循环中最优蚂蚁在路径[i引 粒子i在第k代的位置：Pest,i表示当前粒子i找 上释放的信息素量：Q为信息素总量：Gk为最短 到的最优位置；Gbest表示所有粒子找到的全局最 路径长度：P为信息素的挥发程度，取值范围为 优位置. [0,1:T1()表示按照基本信息素更新方式进行更 Stpe5若满足终止条件（达到粒子最大进化代 新持续到当前代数即出现更强适应度解时刻环境中 数或粒子连续进化若干代，未出现性能更好的粒 的信息素量，其计算公式如下所示，该量随蚁群算 子)，算法结束，当前Gst所对应的适应度评价 法的迭代代数变化而更新. 值即为待规划问题的最优解：若不满足，则返回 Step2. T1(t+1)=(1-p)T1(t)+△T1(t), 3) 2 应用背景及环境建模 △r1()=∑△奇1() (4) 2.1背景描述 式中，△奇：表示蚂蚁k在本次循环中在路径[i, 日本北海道旭川市中心垃圾填埋场位于旭川 上释放的信息素量，△1()表示本次循环后路径 市江丹别町中園197番地，占地面积179.7万m2, [i,引上T1(t)值的变化.在ant-cycle模型中，△专1 自1979年6月至2003年6月，大量的生活垃圾和 的计算公式如下式所示： 部分建筑垃圾被填埋至此，填埋量约650万t10.由 于垃圾填埋场排水不畅，所以留存于填埋垃圾内部 △1(t)= Q/Lk,蚂蚁k经过路径[i,引时： (5) 的水分影响垃圾沉降，垃圾渗出液混入地下水源， 0,其他 造成污染.同时填埋垃圾内部缺乏空气流通，形成 式中，Lk表示蚂蚁k在本次循环中所走路径的长 了严重的厌氧环境，并累积了大量的可燃性气体， 度 且由于垃圾填埋场的气体排放管道数量不足，所以 在Step2中，改换粒子及其对应的参数时，信 存在较为严重的安全隐患叫. 息素不清零 针对此情况，旭川市环境部对垃圾场进行改 Step3根据蚁群算法的求解结果判断粒子位 建，采取封闭施工、整修水道等措施，修建了新 置的优劣，求得并更新最优粒子位置.如果将某个 的集水井、渗透液排放水道和瓦斯排放管道.自
· 956 · 北 京 科 技 大 学 学 报 第 35 卷 Step1 初始一定数量的三维粒子群粒子 P0, P1, · · · , Pn. 一个粒子对应于一组 ρ、α 和 β 参数，粒子在解空间中的位置即为参数值，记为 xi (xi0, xi1, xi2). 与位置坐标相对应，粒子在解空 间中具有三个方向的移动速度，记为 Vi (Vi0, Vi1, Vi2). Step2 将当前每个粒子对应的参数值反馈回 蚁群算法. 应用这组参数调用蚁群算法 X 代 (X 取值范围为 [3,5])[9] 后，保留环境中的信息素，并根 据当前求解结果 (即蚂蚁遍历排列) 更新信息素. 蚁 群算法采用全局异步与精英策略相结合的信息素更 新方式. 该方式的信息素量不随蚁群算法迭代代数 的增加而变化，当且仅当出现了具有更强适应度的 解时，才对信息素进行更新，并对该全局最优解经 过的路径进行信息素加强. 信息素更新公式如下所 示： ∆τ 0 ij (t) = ( Q/Gk,当路径 [i, j] 为最优路径上的片段时; 0,其他. (1) τij (t + 1) = (1 − ρ)τij1(t) + ∆τ 0 ij (t). (2) 式中：∆τ 0 ij (t) 表示本次循环中最优蚂蚁在路径 [i,j] 上释放的信息素量；Q 为信息素总量；Gk 为最短 路径长度；ρ 为信息素的挥发程度，取值范围为 [0,1]；τij1(t) 表示按照基本信息素更新方式进行更 新持续到当前代数即出现更强适应度解时刻环境中 的信息素量，其计算公式如下所示，该量随蚁群算 法的迭代代数变化而更新. τij1(t + 1) = (1 − ρ)τij1(t) + ∆τij1(t), (3) ∆τij1(t) = X∆τ k ij1 (t). (4) 式中，∆τ k ij1 表示蚂蚁 k 在本次循环中在路径 [i,j] 上释放的信息素量，∆τij1(t) 表示本次循环后路径 [i,j] 上 τij1(t) 值的变化. 在 ant-cycle 模型中，∆τ k ij1 的计算公式如下式所示： ∆τ k ij1 (t)=( Q/Lk, 蚂蚁 k 经过路径 [i, j] 时; 0,其他. (5) 式中，Lk 表示蚂蚁 k 在本次循环中所走路径的长 度. 在 Step2 中，改换粒子及其对应的参数时，信 息素不清零. Step3 根据蚁群算法的求解结果判断粒子位 置的优劣，求得并更新最优粒子位置. 如果将某个 粒子所对应的参数值反馈回蚁群算法，蚁群算法的 求解结果最优，则称这个粒子为最优粒子. 最优粒 子所对应的一组参数值表明该粒子在解空间中的位 置，即最优粒子位置. 记每个粒子当前找到的最优 粒子位置为 Pbest，整个种群当前所找到的最优粒子 位置为 Gbest. Pbest 和 Gbest 的适应度评价值即为 蚁群算法求得路径的长度，路径长度越小参数质量 越好. Step4 得到更新后的 Pbest 和 Gbest 后，按照 Vi(k+1) = wVi(k) + c1r1(Pbest,i − xi(k))+ c2r2(Gbest − xi(k)) (6) 更新粒子的速度，按照 xi(k+1) = xi(k) + Vi(k+1) (7) 更新粒子的位置. 式中：w 为惯性权重；c1 和 c2 为 两个常数，c1 调节粒子向自身最好位置靠近的权 重，c2 调节粒子向全局最好位置靠近的权重，c1 和 c2 通常在 0∼2 间取值；r1 和 r2 为两个相互独立的 随机函数；Vi(k) 为粒子 i 在第 k 代的速度；xi(k) 为 粒子 i 在第 k 代的位置；Pbest,i 表示当前粒子 i 找 到的最优位置；Gbest 表示所有粒子找到的全局最 优位置. Stpe5 若满足终止条件 (达到粒子最大进化代 数或粒子连续进化若干代，未出现性能更好的粒 子)，算法结束，当前 Gbest 所对应的适应度评价 值即为待规划问题的最优解；若不满足，则返回 Step2. 2 应用背景及环境建模 2.1 背景描述 日本北海道旭川市中心垃圾填埋场位于旭川 市江丹別町中園 197 番地，占地面积 179.7 万 m2， 自 1979 年 6 月至 2003 年 6 月，大量的生活垃圾和 部分建筑垃圾被填埋至此，填埋量约 650 万 t [10] . 由 于垃圾填埋场排水不畅，所以留存于填埋垃圾内部 的水分影响垃圾沉降，垃圾渗出液混入地下水源， 造成污染. 同时填埋垃圾内部缺乏空气流通，形成 了严重的厌氧环境，并累积了大量的可燃性气体， 且由于垃圾填埋场的气体排放管道数量不足，所以 存在较为严重的安全隐患 [11] . 针对此情况，旭川市环境部对垃圾场进行改 建，采取封闭施工、整修水道等措施，修建了新 的集水井、渗透液排放水道和瓦斯排放管道. 自
第7期 张超等：一种基于粒子群参数优化的改进蚁群算法及其应用 .957· 2004年至2009年6年间，该部门先后修建了97根 根山.填埋场地形图如图1所示，图中颜色各异的 瓦斯管道，随着项目的继续，管道预计数量为109 点即为瓦斯排放管道，海拔高度以等高线表示 凳生为久对策施设配置平面图 S=1:1500 凡例 华收10年T 年度 平成年度工 平收21甲度施下 表随工什 图1旭川垃圾场地形图 Fig.1 Topographic map of landfill in Asahikawa 为保护相关工作人员免受有害气体的侵害，该 面的投影如图3所示. 项目采用机器人采集上图所有管道中瓦斯浓度数 据.为了使机器人以最小距离遍历瓦斯管道，其巡 查路线需要事先通过仿真实验得出.这也正是本文 研究工作的背景所在. X 2.2环境信息处理 由于项目要求机器人以最小距离完成数据采 图2瓦斯管道位置三维示意图 集工作，且垃圾场内不存在障碍物，机器人运行环 境可用一个旅行商问题(traveling salesman problem, Fig.2 3D schematic of the location of gas pipelines TSP)问题来拟合.根据瓦斯管道分布高低不一的特 基于以上定位，109根瓦斯管道的三维坐标就 点，本文以三维环境中的欧式距离为基准，对TSP 可以确定下来，如表1所示（由于篇幅所限，文中 问题中节点间的代价进行描述. 仅列出37根瓦斯管道的坐标值).根据表1中的数 因为109根瓦斯管道的海拔高度多在200m上 据，可得出各瓦斯管道之间的三维几何距离，其计 下，所以选取海拔200m的水平平面作为X-Y平 算公式如下： 面.将这些瓦斯管道的位置投影到该平面后发现， D=V(x-xP+(-)2+(2-2)2.(8) 地图中编号8-5的点位于这109个点相对中心的位 置，故将其在X-Y平面上的投影点作为坐标原点. 这样，巡查机器人路径规划问题被拟合为一个三维 109根瓦斯管道的三维图如图2所示，其在X-Y平 TSP问题
第 7 期 张 超等：一种基于粒子群参数优化的改进蚁群算法及其应用 957 ·· 2004 年至 2009 年 6 年间，该部门先后修建了 97 根 瓦斯管道，随着项目的继续，管道预计数量为 109 根 [11] . 填埋场地形图如图 1 所示，图中颜色各异的 点即为瓦斯排放管道，海拔高度以等高线表示. 图 1 旭川垃圾场地形图 Fig.1 Topographic map of landfill in Asahikawa 为保护相关工作人员免受有害气体的侵害，该 项目采用机器人采集上图所有管道中瓦斯浓度数 据. 为了使机器人以最小距离遍历瓦斯管道，其巡 查路线需要事先通过仿真实验得出. 这也正是本文 研究工作的背景所在. 2.2 环境信息处理 由于项目要求机器人以最小距离完成数据采 集工作，且垃圾场内不存在障碍物，机器人运行环 境可用一个旅行商问题 (traveling salesman problem, TSP) 问题来拟合. 根据瓦斯管道分布高低不一的特 点，本文以三维环境中的欧式距离为基准，对 TSP 问题中节点间的代价进行描述. 因为 109 根瓦斯管道的海拔高度多在 200 m 上 下，所以选取海拔 200 m 的水平平面作为 X-Y 平 面. 将这些瓦斯管道的位置投影到该平面后发现， 地图中编号 8-5 的点位于这 109 个点相对中心的位 置，故将其在 X-Y 平面上的投影点作为坐标原点. 109 根瓦斯管道的三维图如图 2 所示，其在 X-Y 平 面的投影如图 3 所示. 图 2 瓦斯管道位置三维示意图 Fig.2 3D schematic of the location of gas pipelines 基于以上定位，109 根瓦斯管道的三维坐标就 可以确定下来，如表 1 所示 (由于篇幅所限，文中 仅列出 37 根瓦斯管道的坐标值). 根据表 1 中的数 据，可得出各瓦斯管道之间的三维几何距离，其计 算公式如下： Dij = q (xi − xj ) 2 + (yi − yj ) 2 + (zi − zj ) 2. (8) 这样，巡查机器人路径规划问题被拟合为一个三维 TSP 问题
.958. 北京科技大学学报 第35卷 Y 9 9 ,4弱形魏 4 65*62 5 ◆89 1湖源9锁9 ◆88 9 02 104105 10805109 图3瓦斯管道位置在X-Y平面上的投影 Fig.3 Projection for the location of gas pipelines in the X-Y plane 表1瓦斯管道坐标（部分） Table 1 Coordinates of gas pipelines (partial) 序号 1 2 3 4 5 6 7 8 编号 8-5 9-5 10-5 11-d 12-d A18 A19 A20 0 -50 -100 -150 -200 -250 -350 -400 Y 0 0 0 0 0 -7 -7 -7 Z 5.6 6.4 7.5 8.2 8.3 8.7 0 0 序号 9 10 11 12 13 14 15 16 编号 7-5 6-5 A17 8-4 9-4 10-4 11-c 12-c X 50 100 150 0 -50 -100 -150 -200 y 0 0 0 50 50 50 52 52 Z 6.3 6.2 4.3 6.0 6.5 6.5 6.5 6.8 序号 17 18 19 20 21 22 23 24 编号 A14 A15 A16 7-4 64 A13 A12 A11 X -250 -350 -400 50 100 150 200 250 46 45 45 50 50 50 50 50 Z 6.8 0 0 6.0 6.5 2.3 -3.1 -13.5 序号 4…小 97 98 99 100 101 102 103 编号 B19 B17 B18 C7 B23 B22 B21 X 104 200 266 0 -70 245 339 F 小 -256 -229 -252 -300 -306 -306 -306 4 8.5 8.3 4.0 16.0 16.0 10.4 5.0 序号 104 105 106 107 108 109 编号 B27 B26 B25 B24 B29 B28 X -12 80 275 375 217 311 y -360 -364 -360 -360 -404 -412 17.4 14.6 8.6 7.4 16.6 8.8 3 本文算法的仿真应用 所示 应用本文所提基于粒子群参数优化的改进蚁 群算法，对旭川垃圾场改建工程中的巡查机器人路 表2本文算法的仿真结果 径规划问题进行求解.以数值均匀分布的方式构建 Table 2 Simulation results obtained by the proposed algo- 包含a、B和p三个参数的三维粒子，各参数的 rithm 取值范围如下：a∈(0,3)，B∈(0,5)，p∈(0,1) 次数 路径长度/m 运行时间/s 6419.5354280 71.3760 取粒子数number=3,w=0.5,c1=2,c2=2,蚂蚁数 6220.6504480 67.9840 AntCount-=50,Q=2000,迭代代数X=3,当粒子群 0 6225.2978520 84.4390 算法迭代次数达到30代时，算法终止.考虑到蚁群 4 6302.8510740 76.6210 算法和粒子群算法应用过程中的随机性，这里对改 心 6228.1088870 67.8720 平均值 6279.2887378 73.6584 进算法求解5次，其统计结果如表2所示，最优路 最优解 6220.6504480 67.8720 径长度的变化情况与粒子群迭代代数的关系如图4
· 958 · 北 京 科 技 大 学 学 报 第 35 卷 图 3 瓦斯管道位置在 X-Y 平面上的投影 Fig.3 Projection for the location of gas pipelines in the X-Y plane 表 1 瓦斯管道坐标 (部分) Table 1 Coordinates of gas pipelines (partial) 序号 1 2 3 4 5 6 7 8 编号 8-5 9-5 10-5 11-d 12-d A18 A19 A20 X 0 −50 −100 −150 −200 −250 −350 −400 Y 0 0 0 0 0 −7 −7 −7 Z 5.6 6.4 7.5 8.2 8.3 8.7 0 0 序号 9 10 11 12 13 14 15 16 编号 7-5 6-5 A17 8-4 9-4 10-4 11-c 12-c X 50 100 150 0 −50 −100 −150 −200 Y 0 0 0 50 50 50 52 52 Z 6.3 6.2 4.3 6.0 6.5 6.5 6.5 6.8 序号 17 18 19 20 21 22 23 24 编号 A14 A15 A16 7-4 6-4 A13 A12 A11 X −250 −350 −400 50 100 150 200 250 Y 46 45 45 50 50 50 50 50 Z 6.8 0 0 6.0 6.5 2.3 −3.1 −13.5 序号 . . . 97 98 99 100 101 102 103 编号 . . . B19 B17 B18 C7 B23 B22 B21 X . . . 104 200 266 0 −70 245 339 Y . . . −256 −229 −252 −300 −306 −306 −306 Z . . . 8.5 8.3 4.0 16.0 16.0 10.4 5.0 序号 104 105 106 107 108 109 编号 B27 B26 B25 B24 B29 B28 X −12 80 275 375 217 311 Y −360 −364 −360 −360 −404 −412 Z 17.4 14.6 8.6 7.4 16.6 8.8 3 本文算法的仿真应用 应用本文所提基于粒子群参数优化的改进蚁 群算法，对旭川垃圾场改建工程中的巡查机器人路 径规划问题进行求解. 以数值均匀分布的方式构建 包含 α、β 和 ρ 三个参数的三维粒子，各参数的 取值范围如下：α ∈(0, 3)，β ∈(0, 5)，ρ ∈(0, 1). 取粒子数 number=3，w=0.5，c1=2，c2=2，蚂蚁数 AntCount=50，Q=2000，迭代代数 X=3，当粒子群 算法迭代次数达到 30 代时，算法终止. 考虑到蚁群 算法和粒子群算法应用过程中的随机性，这里对改 进算法求解 5 次，其统计结果如表 2 所示，最优路 径长度的变化情况与粒子群迭代代数的关系如图 4 所示. 表 2 本文算法的仿真结果 Table 2 Simulation results obtained by the proposed algorithm 次数 路径长度/m 运行时间/s 1 6419.5354280 71.3760 2 6220.6504480 67.9840 3 6225.2978520 84.4390 4 6302.8510740 76.6210 5 6228.1088870 67.8720 平均值 6279.2887378 73.6584 最优解 6220.6504480 67.8720
第7期 张超等：一种基于粒子群参数优化的改进蚁群算法及其应用 .959· 7600 该最优解对应的瓦斯管道编号排列为{47,57， 7400 53,54,55,56,59,58,43,46,38,34,35,44,45,36 g7200 27,15,16,17,28,37,28,18,19,8,7,65,64,6,5,4, 是700 62,63,72,73,89,82,88,81,80,79,71,74,66,60 在6800 61,2,3.14,13,26.25,30,31,32,22,11,10,21,20 盏6600 12,1,9.67,75,83,91,90,86,87.96,101,104,100 6400 95,97,105,108,106.109,107,103.102,99,94.98, 620 0 5 1015202530 93,92,84,85,77,78.70,69,68.76.24.23.33,41, 粒子群迭代代数 42,5049,48.40.39,52,51}.对应的机器人巡查路 图4最优路径长度的变化过程 线如图5所示. Fig.4 Length change of the optimum solution 24 Y- 62 0 03 08 06 107 图5本文算法求得的最优巡查路线 Fig.5 Optimum inspection path obtained by the proposed algorithm 4 仿真对比研究 其他参数选择如下：numberz=3,w=0.5,c1=2,c2=2, 本文算法的提出是建立在文献[7-8]等相关文 AntCount-=50,Q=2000,当粒子群算法迭代次数 达到30代时，算法终止.各参数的取值范围如 献的研究基础之上的.上述文献中所提出的算法结 构基本一致，该算法和本文算法的不同之处主要有 下：a∈(0,3)，3∈(0,5)，pe(0,1).对文献[7]中算法， 选取p=0.329.为减小随机性的影响，这里对每种 两点.首先，算法一代粒子群中每个粒子调用蚁群 算法各求解5次 算法的迭代代数X不同.上述文献中该迭代代数X 较大，根据待求解问题的复杂程度不同多取几十甚 在求解质量相近的情况下，文献[7-8]和本文 至上百，如文献[8！中求解TSP Eils51等问题时，X 算法的求解情况如表3所示.分析表3中的数据可 取值为30：而在本文算法中，X取3~5之间的数. 以看出，在解质量相近的标准下，本文算法的平均 其次，算法采用的信息素更新方式不同.文献[⑦]等 求解时间分别为文献[T]中算法的41.01%和文献[8] 算法中采用常规信息素更新方式，每个粒子调用一 中算法的30.18%，大幅度减小了求解的时间成本. 次蚁群算法，调用结束后算法重新初始化：在本文 算法中，采用全局异步与精英策略相结合的信息素 表3解质量相近情况下不同算法的求解时间 Table 3 Time-consuming of different algorithms in similar 更新方式，信息素在算法整个过程中不断更新，不 search quality 随每次被调用结束而清零 路径长度/m 运行时间/s 4.1相近求解质量时的情况 算法形式 平均值 最优解 平均值最优解 对于文献7-8中的算法，X的取值越大，其求 文献[71算法6263.0418296214.133301174.223166.935 解质量越高，但时间开销均十分庞大.为便于更好 文献[8]算法6265.3204756240.354004 236.746167.315 本文算法6279.2887386220.650448 71.44567.984 地说明问题，经过大量统计实验发现，在文献[7-8] 所提算法中，当X分别取20和25时，其求解质 4.2 相同规划时间尺度时的情况 量与本文算法相近.为此，在仿真对比研究中，文献 为客观对比各种算法在相同时间规模下的求 [7-8和本文算法中的X分别取为20、25和3. 解情况，对文献[7-8]中的算法采用时间尺度统一 首先构建包含α、B和p三个参数的三维粒子. 化处理，即在文献[7-8]和本文算法中，粒子群算法
第 7 期 张 超等：一种基于粒子群参数优化的改进蚁群算法及其应用 959 ·· 图 4 最优路径长度的变化过程 Fig.4 Length change of the optimum solution 该最优解对应的瓦斯管道编号排列为 {47, 57, 53, 54, 55, 56, 59, 58, 43, 46, 38, 34, 35, 44, 45, 36, 27, 15, 16, 17, 28, 37, 28, 18, 19, 8, 7, 65, 64, 6, 5, 4, 62, 63, 72, 73, 89, 82, 88, 81, 80, 79, 71, 74, 66, 60, 61, 2, 3, 14, 13, 26, 25, 30, 31, 32, 22, 11, 10, 21, 20, 12, 1, 9, 67, 75, 83, 91, 90, 86, 87, 96, 101, 104, 100, 95, 97, 105, 108, 106, 109, 107, 103, 102, 99, 94, 98, 93, 92, 84, 85, 77, 78, 70, 69, 68, 76, 24, 23, 33, 41, 42, 50, 49, 48, 40, 39, 52, 51}. 对应的机器人巡查路 线如图 5 所示. 图 5 本文算法求得的最优巡查路线 Fig.5 Optimum inspection path obtained by the proposed algorithm 4 仿真对比研究 本文算法的提出是建立在文献 [7-8] 等相关文 献的研究基础之上的. 上述文献中所提出的算法结 构基本一致，该算法和本文算法的不同之处主要有 两点. 首先，算法一代粒子群中每个粒子调用蚁群 算法的迭代代数 X 不同. 上述文献中该迭代代数 X 较大，根据待求解问题的复杂程度不同多取几十甚 至上百，如文献 [8] 中求解 TSP Eil51 等问题时，X 取值为 30；而在本文算法中，X 取 3∼5 之间的数. 其次，算法采用的信息素更新方式不同. 文献 [7] 等 算法中采用常规信息素更新方式，每个粒子调用一 次蚁群算法，调用结束后算法重新初始化；在本文 算法中，采用全局异步与精英策略相结合的信息素 更新方式，信息素在算法整个过程中不断更新，不 随每次被调用结束而清零. 4.1 相近求解质量时的情况 对于文献 [7-8] 中的算法，X 的取值越大，其求 解质量越高，但时间开销均十分庞大. 为便于更好 地说明问题，经过大量统计实验发现，在文献 [7-8] 所提算法中，当 X 分别取 20 和 25 时，其求解质 量与本文算法相近. 为此，在仿真对比研究中，文献 [7-8] 和本文算法中的 X 分别取为 20、25 和 3. 首先构建包含 α、β 和 ρ 三个参数的三维粒子. 其他参数选择如下：number=3，w=0.5，c1=2，c2=2， AntCount=50，Q=2000， 当粒子群算法迭代次数 达到 30 代时， 算法终止. 各参数的取值范围如 下：α∈(0, 3)，β∈(0, 5)，ρ∈(0, 1). 对文献 [7] 中算法， 选取 ρ=0.32[9] . 为减小随机性的影响，这里对每种 算法各求解 5 次. 在求解质量相近的情况下，文献 [7-8] 和本文 算法的求解情况如表 3 所示. 分析表 3 中的数据可 以看出，在解质量相近的标准下，本文算法的平均 求解时间分别为文献 [7] 中算法的 41.01%和文献 [8] 中算法的 30.18%，大幅度减小了求解的时间成本. 表 3 解质量相近情况下不同算法的求解时间 Table 3 Time-consuming of different algorithms in similar search quality 算法形式 路径长度/m 运行时间/s 平均值 最优解 平均值 最优解 文献 [7] 算法 6263.041829 6214.133301 174.223 166.935 文献 [8] 算法 6265.320475 6240.354004 236.746 167.315 本文算法 6279.288738 6220.650448 71.445 67.984 4.2 相同规划时间尺度时的情况 为客观对比各种算法在相同时间规模下的求 解情况，对文献 [7-8] 中的算法采用时间尺度统一 化处理，即在文献 [7-8] 和本文算法中，粒子群算法
.960 北京科技大学学 报 第35卷 的每个粒子均调用蚁群算法3代.这种时间尺度统 its application to neuro-fuzzy controller design.J Syst 一化处理可显著减小文献[7-8]中算法的时间开销， Eng Electron,2007,18(3):603 同时也会造成算法的求解质量变差 [3]Chen M J,Huang B C,Zhang M.Function optimization 其他参数的选取和4.1节中的取值保持一致， based on an improved hybrid ACO.CAAI Trans Intell 对每种算法各求解5次.在相同的时间规模下，对 Syst,2012.7(4):370 (陈明杰，黄佰川，张旻.混合改进蚁群算法的函数优化.智 算法的求解情况如表4所示.分析表4中的数据可 能系统学报，2012,7(4)：370) 以看出，在同一时间尺度下，本文算法平均解的长 [4]Zhang Q,Xiong S W.Hybrid ant colony algorithm for 度为文献[可]中算法的97.46%和文献[8]中算法的 multi-depot grain logistics vehicle scheduling problem. 97.34%,求解质量略好 Comput Eng Appl,2011,47(7):4 (张强，熊盛武.多配送中心粮食物流车辆调度混合蚁群算 表4相同时间规模下不同算法的求解质量 法.计算机工程与应用，2011,47(7)：4) Table 4 Search quality of different algorithms in similar [5]Lu X S,He W,He Y J.Research on road planning and ve- time-consuming scale hicle scheduling of the post transportation network.Math 算法形式 路径长度/m 运行时间/s Pract Theory,.2009,39(17):66 平均值 最优解 平均值最优解 (卢晓珊，何伟，贺永金.邮政运输网络中的邮路规划和邮 文献[7算法6406.8600216367.534668 73.41370.836 车调度研究.数学的实践与认识，2009,39(17)：66 文献8]算法6414.4759106382.362305 72.77665.860 本文算法 6243.9454756220.650448 71.44567.984 [6]Yin J H,Wu K Y.Graphy,Theory and Its Algorithm. Hefei:University of Science and Technology of China 综合分析表3和表4中的数据，本文所提改进 Press,2003 算法在保证求解质量的同时，大大减小规划时间成 (股剑宏，吴开亚.图论及其算法.合肥：中国科学技术大 本 学出版社，2003) [7]Min K X,Ge H W,Zhang Y,et al.Solving traveling 5结论 salesman problems by an ACO-and-PSO-based hybrid al- (1)针对现有基于粒子群参数优化的改进蚁群 gorithm.J Jilin Univ Inf Sci,2006,24(4):402 算法耗时较长的问题，提出了一种新的改进算法 (闵克学，葛宏伟，张毅，等。基于蚁群和粒子群优化的混 合算法求解TSP问题.吉林大学学报：信息科学版，2006 该算法应用了一种全局异步与精英策略相结合的信 24(4):402) 息素更新方式，并合理确定了蚁群算法被粒子群算 [8]Xia H,Wang H,Chen X.A kind of ant colony parameter 法调用的迭代代数. adaptive optimization algorithm based on particle swarm (②)针对垃圾场巡查环境不存在障碍物的特点， optimization thought.J Shandong Univ Eng Sci,2010 将移动机器人路径规划问题转化为一个三维TSP 40(3):26 问题，从而为此类路径规划问题提供了一种新的数 (夏辉，王华，陈熙.一种基于微粒群思想的蚁群参数自适 学模型抽象方法. 应优化算法.山东大学学报：工学版，2010,40(3)：26) (3)将本文提出的改进蚁群算法应用于日本旭 [9]Chen P.An Improved Ant Colony Optimization and It's 川市垃圾场巡查机器人路径规划问题的求解，与近 Application in the Path Planning for Landfill Inspection 期相关算法相比，在保证求解质量的同时，本文 Robot [Dissertation].Beijing:University of Science and Technology Beijing,2012 算法可以大大提高搜索速度：在同一规划时间尺度 (陈鹏.一种改进的蚁群算法及其在垃圾场巡查机器人路 下，本文算法可求得质量潲高的解 径规划中的应用学位论].北京：北京科技大学，2012) [10 Monitoring Committee of Asahikawa Nakazono Final 参考文献 Disposal Site.Summary for the Nakazono Final Dis- posal Ssite /Proceedings of Monitoring Committee of [1]Gu X P,Jin Y,Hu R L,et al.Wireless sensor networks Asahikawa Nakazono Final Disposal Site.Asahikawa, routing protocol based on ant colony algorithm /Pro- 2010:1 ceedings of 2012 IEEE 3rd International Conference on [11]Kamata A,Tobita A,Matsufuji T,et al.Stabilizing treat- Software Engineering and Service Science.Beijing.2012: ment and closure work for Nakazono Final Disposal Site 161 in Asahikawa City.J Jpn Waste Manage Assoc,2011, [2]Zhao B J,LiS Y.Ant colony optimization algorithm and 64(301):282
· 960 · 北 京 科 技 大 学 学 报 第 35 卷 的每个粒子均调用蚁群算法 3 代. 这种时间尺度统 一化处理可显著减小文献 [7-8] 中算法的时间开销， 同时也会造成算法的求解质量变差. 其他参数的选取和 4.1 节中的取值保持一致， 对每种算法各求解 5 次. 在相同的时间规模下，对 算法的求解情况如表 4 所示. 分析表 4 中的数据可 以看出，在同一时间尺度下，本文算法平均解的长 度为文献 [7] 中算法的 97.46%和文献 [8] 中算法的 97.34%，求解质量略好. 表 4 相同时间规模下不同算法的求解质量 Table 4 Search quality of different algorithms in similar time-consuming scale 算法形式 路径长度/m 运行时间/s 平均值 最优解 平均值 最优解 文献 [7] 算法 6406.860021 6367.534668 73.413 70.836 文献 [8] 算法 6414.475910 6382.362305 72.776 65.860 本文算法 6243.945475 6220.650448 71.445 67.984 综合分析表 3 和表 4 中的数据，本文所提改进 算法在保证求解质量的同时，大大减小规划时间成 本. 5 结论 (1) 针对现有基于粒子群参数优化的改进蚁群 算法耗时较长的问题，提出了一种新的改进算法. 该算法应用了一种全局异步与精英策略相结合的信 息素更新方式，并合理确定了蚁群算法被粒子群算 法调用的迭代代数. (2) 针对垃圾场巡查环境不存在障碍物的特点， 将移动机器人路径规划问题转化为一个三维 TSP 问题，从而为此类路径规划问题提供了一种新的数 学模型抽象方法. (3) 将本文提出的改进蚁群算法应用于日本旭 川市垃圾场巡查机器人路径规划问题的求解，与近 期相关算法相比，在保证求解质量的同时，本文 算法可以大大提高搜索速度；在同一规划时间尺度 下，本文算法可求得质量稍高的解. 参 考 文 献 [1] Gu X P, Jin Y, Hu R L, et al. Wireless sensor networks routing protocol based on ant colony algorithm // Proceedings of 2012 IEEE 3rd International Conference on Software Engineering and Service Science. Beijing, 2012: 161 [2] Zhao B J, Li S Y. Ant colony optimization algorithm and its application to neuro-fuzzy controller design. J Syst Eng Electron, 2007, 18(3): 603 [3] Chen M J, Huang B C, Zhang M. Function optimization based on an improved hybrid ACO. CAAI Trans Intell Syst, 2012, 7(4): 370 (陈明杰, 黄佰川, 张旻. 混合改进蚁群算法的函数优化. 智 能系统学报, 2012, 7(4): 370) [4] Zhang Q, Xiong S W. Hybrid ant colony algorithm for multi-depot grain logistics vehicle scheduling problem. Comput Eng Appl, 2011, 47(7): 4 (张强, 熊盛武. 多配送中心粮食物流车辆调度混合蚁群算 法. 计算机工程与应用, 2011, 47(7): 4) [5] Lu X S, He W, He Y J. Research on road planning and vehicle scheduling of the post transportation network. Math Pract Theory, 2009, 39(17): 66 (卢晓珊, 何伟, 贺永金. 邮政运输网络中的邮路规划和邮 车调度研究. 数学的实践与认识, 2009, 39(17): 66 [6] Yin J H, Wu K Y. Graphy, Theory and Its Algorithm. Hefei: University of Science and Technology of China Press, 2003 (殷剑宏, 吴开亚. 图论及其算法. 合肥: 中国科学技术大 学出版社, 2003) [7] Min K X, Ge H W, Zhang Y, et al. Solving traveling salesman problems by an ACO-and-PSO-based hybrid algorithm. J Jilin Univ Inf Sci, 2006, 24(4)：402 (闵克学, 葛宏伟, 张毅, 等. 基于蚁群和粒子群优化的混 合算法求解 TSP 问题. 吉林大学学报: 信息科学版, 2006, 24(4)：402) [8] Xia H, Wang H, Chen X. A kind of ant colony parameter adaptive optimization algorithm based on particle swarm optimization thought. J Shandong Univ Eng Sci, 2010, 40(3)：26 (夏辉, 王华, 陈熙. 一种基于微粒群思想的蚁群参数自适 应优化算法. 山东大学学报：工学版, 2010, 40(3)：26) [9] Chen P. An Improved Ant Colony Optimization and It’s Application in the Path Planning for Landfill Inspection Robot [Dissertation]. Beijing: University of Science and Technology Beijing, 2012 (陈鹏. 一种改进的蚁群算法及其在垃圾场巡查机器人路 径规划中的应用 [学位论文]. 北京: 北京科技大学, 2012) [10] Monitoring Committee of Asahikawa Nakazono Final Disposal Site. Summary for the Nakazono Final Disposal Ssite // Proceedings of Monitoring Committee of Asahikawa Nakazono Final Disposal Site. Asahikawa, 2010: 1 [11] Kamata A, Tobita A, Matsufuji T, et al. Stabilizing treatment and closure work for Nakazono Final Disposal Site in Asahikawa City. J Jpn Waste Manage Assoc, 2011, 64(301): 282