.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 // Pro￾ceedings 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 ve￾hicle 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 al￾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, 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 Dis￾posal Ssite // Proceedings of Monitoring Committee of Asahikawa Nakazono Final Disposal Site. Asahikawa, 2010: 1 [11] Kamata A, Tobita A, Matsufuji T, et al. Stabilizing treat￾ment and closure work for Nakazono Final Disposal Site in Asahikawa City. J Jpn Waste Manage Assoc, 2011, 64(301): 282