分支蚁群动态扰动算法求解TSP问题

中国管理科学 ›› 2005, Vol. ›› Issue (6): 57-63.

分支蚁群动态扰动算法求解TSP问题

刘心报, 叶强, 刘林, 杨善林

合肥工业大学管理学院, 安徽, 合肥, 230009

收稿日期:2005-01-10 修回日期:2005-11-15 出版日期:2005-12-28 发布日期:2012-03-07
基金资助:
教育部科学技术研究重点项目(104107);安徽省教育厅自然科学重点科研项目(2004kj308zd);安徽省自然科学基金项目(050460401)

Branching Ant Colony with Dynamic Perturbation Algorithm for Solving TSPs

LIU Xin-bao, YE Qiang, LIU Lin, YANG Shan-lin

School of Management, Hefei University of Technology, Hefei 230009, China

Received:2005-01-10 Revised:2005-11-15 Online:2005-12-28 Published:2012-03-07

摘要/Abstract

摘要： 蚁群优化算法是一种求解组合优化难题的强启发式算法,它利用正反馈和并行计算原理,具备很强的搜索能力。近年来,蚁群优化算法广泛应用于TSP问题的研究。本文提出分支蚁群动态扰动(DPBAC)算法,该算法主要从5个方面对基本蚁群算法做出改进:引入分支策略选取出发城市;改进状态转移规则;引入变异策略改进蚂蚁路径;改进信息素更新规则;引入条件动态扰动策略。实验表明,该算法可以有效改善基本蚁群算法搜索时间较长、容易陷入局部极小等缺点。

关键词: TSP, 蚁群优化算法, 分支策略, 条件动态扰动策略

Abstract: Ant Colony Optimization(ACO)algorithm is a kind of meta-heuristic algorithm for solving NP-hard problems.Using positive feedback and parallel-computing principle,it has strong capability to explore solution.Recently,ACO algorithm is widely used to study TSP problems.This paper proposes Branching Ant Colony with Dynamic Perturbation(DPBAC)algorithm,which improves traditional ACO algorithm in 5 aspects:introducing Branching Method to choose starting points,improving state transition rules,introducing Mutation Method to shorten tours,improving pheromone updating rules and introducing Conditional Dynamic Perturbation Method.Showed by simulated experiments,DPBAC algorithm can improve the shortcomings,as costing too much time and tending to stick in local minimum and so on,of traditional ACO algorithm.

Key words: Traveling Salesman Problem, Ant Colony Optimization algorithm, Branching Method, Conditional Dynamic Perturbation Method

中图分类号:

C931

刘心报, 叶强, 刘林, 杨善林. 分支蚁群动态扰动算法求解TSP问题[J]. 中国管理科学, 2005, (6): 57-63.

LIU Xin-bao, YE Qiang, LIU Lin, YANG Shan-lin. Branching Ant Colony with Dynamic Perturbation Algorithm for Solving TSPs[J]. Chinese Journal of Management Science, 2005, (6): 57-63.

参考文献

[1] A.Colorni,M.Dorigo,V.Maniezzo,M.Trubian.Ant system for job-shop scheduling[J].Belgian Journal of Operation Research,Statistics and Computer Science,1994,34(1):39-54.
[2] 陈峻,沈洁,秦玲,陈宏建.基于分布均匀度的自适应蚁群算法[J].软件学报,2003,14(8):1379-1387.
[3] Cheng-Fa Tsai,Chun-Wei Tsai,and Ching-Chang Tseng.A new hybrid heuristic approach for solving large traveling salesman problem [J].Information Sciences,2004,166:67-81.
[4] 丁建立,陈增强,袁著祉.基于动态聚类邻域分区的并行蚁群优化算法[J].系统工程理论与实践,2003,(9):105-110.
[5] 冯祖洪,徐宗本.用混合型蚂蚁群算法求解TSP问题[J].工程数学学报,2002,19(4):35-39.
[6] 郝晋,石立宝,周家启.求解复杂TSP问题的随机扰动蚁群算法[J].系统工程理论与实践,2002,9:88-91.
[7] 李炳宇,萧蕴诗.基于模式求解旅行商问题的蚁群算法[J].同济大学学报,2003,31(11):1348-1352.
[8] L.M.Gambardella,E.Taillard,M.Dorigo.Ant Colonies for QAP [R].IDSIA,Lugano,Switzerland,Tech.Rep.IDSIA97-4,1997.
[9] L.M.Gambardella,E.Taillard,G.Agazzi.Ant Colonies for vehicle routing problem [C].D.Corne,M.Dorigo and F.Glover editors,vol.New Ideas in Optimization,McGraw-Hill,1999.
[10] 马良.旅行推销员问题的算法综述[J].数学的实践与认识,2000,30(2):156-165.
[11] Marco Dorigo,Luca Maria Gambardella.Ant colonies for the traveling salesman problem.BioSystems,1997,43:73-81.
[12] Ruoying Sun & Shoji Tatsumi & Gang Zhao.Multiagent reinforcement learning method with an improved ant colony system[C].IEEE 2001,1612-1617.
[13] SeungGwan Lee,TaeUng jung,TaeChoong Chung.Improved Ant Agents System by the Dynamic Parameter Decision[C].IEEE International Fuz2y Systems Conference,2001.
[14] Tolga Bektas.The multiple traveling salesman problem:an overview of formulations and solution procedures [J].Omega,2006,34:209-219.
[15] 吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法.计算机学报,2001,24(2):1328-1333.
[16] 熊伟清,余舜浩,赵杰煜.具有分工的蚁群算法及应用[J].模式识别与人工智能,2003,16(3):328-333.
[17] 张纪会,徐心和.一种新的进化算法--蚁群算法[J].系统工程理论与实践,1999,(3):84-87.
[18] 赵赫,杜端甫.TSP的邻域搜索算法的分析和改进[J].中国管理科学,1997,5(1):35-39.
[19] Zhi-Wei Ye,Zhao-Bao Zheng.Research on the configuration of parameter a,β,p in ant algorithm exemplified by TSP[C].Preceedings of the Second International Conference on Machine Learing and Cybernetics,Xi' an,2-5November 2003.