基于IPSO算法的TSP问题求解研究

计算机科学 ›› 2014, Vol. 41 ›› Issue (Z11): 69-71.

基于IPSO算法的TSP问题求解研究

高峰,郑波

中国民航飞行学院广汉618307;中国民航飞行学院广汉618307

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受中国民航飞行学院青年科学基金项目(Q2013-145)资助

Study on TSP Solving Based on IPSO

GAO Feng and ZHENG Bo

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： 为获得旅行商问题(Traveling Salesman Problem,TSP)的最优解,提出利用改进的粒子群优化(Improved Particle Swarm Optimization,IPSO)算法中求解TSP问题。IPSO算法采用了粒子自适应更新机制和继承式判断机制,克服了传统算法易陷入局部最优位置的缺陷以及可调参数和初始位置随机设定对寻优结果不确定性的影响,确保在解空间内获得一致性的全局最优解。通过对不同样本TSP问题求解,验证了IPSO算法的有效性和稳定性。对比实验表明:IPSO算法在解决大规模寻优问题时具有突出的全局寻优能力。

关键词: 旅行商问题,改进的粒子群优化算法,自适应更新机制,继承式判断机制

Abstract: In order to obtain the optimal solution of TSP,an improved particle swarm optimization (IPSO) was proposed for solving TSP.By using of adaptive updating mechanism and inheritance judgment mechanism,the IPSO overcomes the shortcomings of traditional algorithm falling into local best position easily and the effect of adjustable parameters and initial position set randomly on the uncertainty of optimization results,to ensure to obtain the consistency global optimal solutions in the solution space.By solving the different samples of TSP,we verified the effectiveness and stability of the IPSO.Comparative experiment show that the IPSO in solving large-scale optimization problem has the highlighted ability about the global optimization.

Key words: TSP,IPSO,Adaptive updating mechanism,Inheritance judgment mechanism

高峰,郑波. 基于IPSO算法的TSP问题求解研究[J]. 计算机科学, 2014, 41(Z11): 69-71. https://doi.org/

GAO Feng and ZHENG Bo. Study on TSP Solving Based on IPSO[J]. Computer Science, 2014, 41(Z11): 69-71. https://doi.org/

参考文献

[1] Meer K.Simulated Annealing Versus Metropolis for a TSP Instance[J].Information Processing Letters,2007,2:216-219
[2] 张辉,赵正德,杨立朝,等.TSP问题的算法与应用研究[J].计算机应用与软件,2009,26(4):274-276
[3] 王剑文,戴光明,谢柏桥,等.求解TSP问题算法综述[J].计算机工程与科学,2008,30(2):72-74
[4] 谷文祥,李向涛,王春颖,等.一种求解TSP问题的混合算法[J].东北师范大学:自然科学版,2011,43(3):60-64
[5] Shi X H,Liang Y G,Lee H P,et al.Particle Swarm Optimiza-tion-based Algorithms for TSP and generalized TSP [J].Information Processing Letters,2007,8:169-176
[6] Venter Sobieszczanski-sobieski J.Particle swarm optimization[J].AIAA Journal,2003,41(8):1583-1589
[7] 郑波.基于PSO-SVM的民航发动机送修等级决策研究[J].推进技术,2013,34(5):68-69
[8] Eberhart R,Shi Yu-hui.Particle swarm optimization:Develop-ments applications and resources[C]∥Proc IEEE Int Conf on Evolutionary Computation.Seoul 2001 :81-86
[9] 陈文兰,戴树贵.旅行商问题算法研究综述[J].滁州学院学报,2006,8(3):1-6
[10] 史峰,王辉,郁磊,等.MATLAB智能算法——30个案例分析[M].北京:北京航空航天大学出版社,2011
[11] Dorigo M,Birattari M,Stutzle T.Ant Colony Optimization[J].Computational Intelligence Magazine,200,61(4):28-39
[12] Misevicius A.A tabu search algorithm for the quadratic assignment problem[J].Computational Optimization and Applications,2005(30):95-111

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed