求解TSP的改进人工鱼群算法

Journal of Systems Engineering and Electronics ›› 2009, Vol. 31 ›› Issue (6): 1458-1461.

求解TSP的改进人工鱼群算法

周永权, 谢竹诚

广西民族大学数学与计算机科学学院, 广西, 南宁, 530006

收稿日期:2008-03-18 修回日期:2008-05-19 出版日期:2009-06-20 发布日期:2010-01-03
作者简介:周永权(1962- ),男,教授,博士,主要研究方向为计算智能,神经网络.E-mail:yongquanzhou@126.com
基金资助:
国家自然科学基金项目(60461001);广西自然科学基金项目(08320820991086);国家民族事务委员会科研项目(08GX01)资助课题

Improved artificial fish-school swarm algorithm for solving TSP

ZHOU Yong-quan, XIE Zhu-cheng

Coll. of Mathematics and Computer Science, Guangxi Univ. for Nationalities, Nanning 530006, China

Received:2008-03-18 Revised:2008-05-19 Online:2009-06-20 Published:2010-01-03

摘要/Abstract

摘要： 利用遗传算法的交叉算子,并引入去交叉策略,对人工鱼群算法进行了改进,提出了一种改进型人工鱼群算法,并将该算法用于求解旅行商问题(traveling salesman problem,TSP)这一经典的NP难问题。通过实验仿真与目前TSP已知最优解进行对比分析,结果表明,改进后的人工鱼群算法在种群规模较小,迭代次数较少的情况下也可以收敛到已知最优解。

中图分类号:

TP18

周永权, 谢竹诚. 求解TSP的改进人工鱼群算法[J]. Journal of Systems Engineering and Electronics, 2009, 31(6): 1458-1461.

ZHOU Yong-quan, XIE Zhu-cheng. Improved artificial fish-school swarm algorithm for solving TSP[J]. Journal of Systems Engineering and Electronics, 2009, 31(6): 1458-1461.

[1] 陈志平,徐宗本.计算机数学一计算机复杂性理论与NPC,NP难问题的求解[M].北京:科学出版社,2001.
[2] Carpaneto G,Toth P.Some new branching and bounding criteria for the asymmetric traveling salesman problem[J].Management Science,1980,26:736-743.
[3] Rosenkrantz,Restearns,Lewis Lew Is Pmlew.An analysis of several heuristics for the traveling salesman problem[J].SIAM Journal of Computer,1977,6(1):563-581.
[4] Kirkpatr Ick S,Gelatt C D,Vecchi M P.Optimization by simulated annealing[J].Science,1983,220(4598):671-680.
[5] Tsai Cheng-Fa,Tsai Chun-Wei,Tseng Ching-Chang.A new hybrid heuristic approach for solving large traveling salesman problem[J].Information Sciences,2004,166(1-4):67-81.
[6] Cochranej E M,Beasley E.The co-adaptive neural network approach to the euclidean traveling salesman problem[J].Neural Networks,2003,16(10)..1499-1525.
[7] Tsai C F,Tsai C W,Yang T.A modified multiple-searching method to genetic algorithms for solving traveling salesman problem[C]//IEEE Int.Conf.on Systems,Manand Cybernetics,2002:6-12.
[8] Tu Xiaoyuan.Artificial animals for computer animation,biomechanics,locomotion,perception,and behavior[D].University of Toronto,1999.
[9] 李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法.系统工程理论与实践[J] ,2002,22(11):32-38.
[10] 黄岚,王康平,周春光.等.基于蚂蚁算法的混合方法求解旅行商问题[J].吉林大学学报(理学版),2002,40(4):369-373.
[11] 蔡利剑.智能蚂蚁系统研究[D].天津:河北工业大学论文,2001.
[12] 邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,1999.
[13] 李晓磊,路飞,田国会,等.组合优化问题的人工鱼群算法应用[J].山东大学学报(工学版),2004,34(5):64-67.
[14] 段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.
[15] 高尚.解旅行商问题的混沌蚁群算法[J].系统工程理论与实践,2005(9):100-104.
[16] 王文峰,刘光远,温万惠.求解TSP问题的自逃逸混合离敢粒子群算法研究[J].计算机科学,2007,34(8):143-145.
[17] 蔡之华,彭锦国,高伟,等.一种改进的求解TSP问题的演化算法[J].计算机学报,2005,28(5):823-828.
[18] 陆子强,郭国雄.基于领域搜索的混合遗传算法及其在对称TSP中的应用[J].计算机工程与应用,2005,27(7):79-81.
[19] 王斌,李元香,王治,等.一种求解TSP问题的单亲遗传算法[J].计算机科学,2003,30(5):73-75.