智能优化算法求解TSP问题

第21卷第3期

Vol.21No.3

　控　制　与　决　策

　　ControlandDecision　

2006年3月

　Mar.2006

　　文章编号:100120920(2006)0320241207

智能优化算法求解TSP问题

高海昌a,冯博琴a,朱　利b

(西安交通大学a.电子与信息工程学院,b.软件学院,西安710049)

摘　要:TSP(旅行商)问题代表组合优化问题,具有很强的工程背景和实际应用价值,但至今尚未找到非常有效的

求解方法.为此,讨论了最近研究比较热门的使用各种智能优化算法(蚁群算法、遗传算法、模拟退火算法、禁忌搜索算法、粒子群优化算法、免疫算法等)求解TSP问题的研究进展,指出了各种方法的优缺点和改Hopfield神经网络、进策略.最后总结并提出了智能优化算法求解TSP问题的未来研究方向和建议.

关键词:旅行商问题;蚁群算法;遗传算法;模拟退火算法;禁忌搜索算法;粒子群优化算法中图分类号:TP301　　　　文献标识码:A

ReviewsoftheMeta-heuristicAlgorithmsforTSP

GAOHai2chang,FENGBo2qin,ZHULi

(a.SchoolofElectronicsandInformationEngineering,b.lare,JUniversity,Xi’an710049,China.Correspondent:GAOHai2chang,EAbstract:Travelingsalesisonofakindofcombinationoptimizationproblems,possessingaandpracticalapplicationvalue.However,thereisnoeffectivecorre2spondingsolutiAimthat,theresearchandapplicationofthemostpopularmeta2heuristicmethodssuchasantcolonyalgorithm,geneticalgorithm,simulatedannealing,tabusearch,hopfieldneuralnetwork,particleswarmoptimizationandimmunealgorithm,etc.arereviewed.Theadvantagesanddisadvantagesofeachmethodandtheimprovementstrategiesarediscussed.Thefutureresearchdirectionandsuggestionarealsogiven.

Keywords:TSP;Antcolonyalgorithm;Geneticalgorithm;Simulatedannealing;Tabusearch;Particleswarmop2timization

1　引　　言

　　TSP(旅行商)问题已经被证明是一个NP2hard问题[1],即在P≠NP的假设下,找不到一个多

个重要课题.

2　TSP问题的定义和求解方法分类

2.1　TSP问题的定义

TSP是典型的组合优化问题[2],给定n个城市

项式时间算法来求解其最优解.TSP问题易于陈述但难于求解,自1932年提出以来,已引起许多学者的兴趣,但至今尚未找到非常有效的求解方法.

由于TSP问题代表一类组合优化问题,在实际工程中有许多应用,如计算机联网、电子地图、交通诱导、电气布线、VLSI单元布局、ATM分组交换网等.鉴于其重要的工程与理论价值,TSP常作为算法性能研究的典型算例.求其最优解的代价是指数级的,因此对其近似解的研究一直是算法设计的一

　　收稿日期:2005204225;修回日期:2005208215.

以及各城市之间的距离,要求找到一条遍历所有城

市且每个城市只被访问一次的路线,并使得总路线距离最短,或表述为在有n个结点的完全图中找出最短的Hamilton回路.其数学描述为:设有一个城市集合C=(c1,c2,…,cn),其中每对城市之间的距离d(ci,cj)∈R+,求一对经过C中每个城市一次的路线(cΠ1,cΠ2,…,cΠn),使

　　基金项目:国家863高技术研究发展计划基金项目(2003AA1Z2610).

　　作者简介:高海昌(1978—),男,江苏徐州人,博士生,从事智能优化算法、软件自动化测试的研究;冯博琴(1942—),

男,浙江温州人,教授,博士生导师,从事智能网络的研究.

242

n-1

控　　制　　与　　决　　策

min

第21卷

∑

i=1

d(cΠi,cΠ(i+1))+d(cΠn,cΠ1),

(1)

式中:tabuk(k=1,2,…,m)表示蚂蚁k已经走过城市的集合,开始时tabuk中只有一个元素,即蚂蚁k的出发城市,随着进化的进行,tabuk中的元素不断增加;allowedk={0,1,…,0-1}-tabuk表示蚂蚁k下一步允许选择的城市;Γij是能见度,取路径(i,j)长度的倒数;Α,Β调节信息素浓度Σ与能见度Γ的相对重要程度.

随着时间的推移,以前留在各条路径上的信息素逐渐消失,用参数1-Θ表示信息素的挥发程度.经过w个时刻,蚂蚁完成一次循环,各路径上的信息素的浓度可根据如下公式进行调整:

Σij(t+w)=Θ

第21卷第3期

Vol.21No.3

　控　制　与　决　策

　　ControlandDecision　

2006年3月

　Mar.2006

　　文章编号:100120920(2006)0320241207

智能优化算法求解TSP问题

高海昌a,冯博琴a,朱　利b

(西安交通大学a.电子与信息工程学院,b.软件学院,西安710049)

摘　要:TSP(旅行商)问题代表组合优化问题,具有很强的工程背景和实际应用价值,但至今尚未找到非常有效的

关键词:旅行商问题;蚁群算法;遗传算法;模拟退火算法;禁忌搜索算法;粒子群优化算法中图分类号:TP301　　　　文献标识码:A

ReviewsoftheMeta-heuristicAlgorithmsforTSP

GAOHai2chang,FENGBo2qin,ZHULi

Keywords:TSP;Antcolonyalgorithm;Geneticalgorithm;Simulatedannealing;Tabusearch;Particleswarmop2timization

1　引　　言

　　TSP(旅行商)问题已经被证明是一个NP2hard问题[1],即在P≠NP的假设下,找不到一个多

个重要课题.

2　TSP问题的定义和求解方法分类

2.1　TSP问题的定义

TSP是典型的组合优化问题[2],给定n个城市

项式时间算法来求解其最优解.TSP问题易于陈述但难于求解,自1932年提出以来,已引起许多学者的兴趣,但至今尚未找到非常有效的求解方法.

　　收稿日期:2005204225;修回日期:2005208215.

以及各城市之间的距离,要求找到一条遍历所有城

　　基金项目:国家863高技术研究发展计划基金项目(2003AA1Z2610).

　　作者简介:高海昌(1978—),男,江苏徐州人,博士生,从事智能优化算法、软件自动化测试的研究;冯博琴(1942—),

男,浙江温州人,教授,博士生导师,从事智能网络的研究.

242

n-1

控　　制　　与　　决　　策

min

第21卷

∑

i=1

d(cΠi,cΠ(i+1))+d(cΠn,cΠ1),

(1)

Σij(t+w)=Θ

智能优化算法求解TSP问题

相关文章