基于基因片段插入的旅行商问题的演化算法研究.pdfVIP

2014年第 3期 闽南师范大学学报(自然科学版) No．3．2014年 (总第 85期) JournalofMinnanNormalUniversity(Nat．Sci．) GeneralNo．85 基于基因片段插人的旅行商问题的演化算法研究 刘欣欣 ．陈宝兴 f闽南师范大学计算机学院，福建漳州363000) 摘 要 ：旅行商问题是组合优化 中一个广泛研究的NP-hard问题．本文引入 了一种新的运算方式：基 因片段插 入 。并利用此运算给 出了一种求解旅行商问题 的演化算法．实验结果表 明，此算法能以较高的概率找到旅行商问 题的近似最优 解． 关键词 ：旅行商问题 ；基 因片段 ；近似最优解 中图分类号 ：TP301 文献标志码 ：A 文章编号 ：2095—7122(2014)03-0034-03 AnEvolutionAlgorithm ofUsingGeneFragmentInsertingfor TravelSalesman Problem LIU Xin-xin．CHEN Bao—xing (SchoolofComputerScience，MinnanNormalUniversity，Zhangzhou，Fujian363000，China) Abstract：The~avehngsalesmanproblem(rsP)isaNP-hardproblemwhichwidelystudiedincombinatorialoptimizationdo玎卜 ain．A new operator,namedgenefragmentinserting，isproposedinthispaper．Byusingthisoperator，anevolutionalgorithm forsolving travelsalesman problem ispresented．Experimentresultsshow thatthe proposed algorithm can find an approximateoptimalsolutionforTSPwiht ahighprobability． Keywords：travelsalesmanproblem ；genefragment；approximateoptimalsolution 旅行商问题(Travelingsalesmanproblem，TSP)可简述为：给定n个城市的集合f1，2，…，n】，旅行商从 自 己所在的城市出发。寻找一条遍历 n个城市，且各城市仅经过一次后，回到 自己出发点的最短路径l【1．TSP 问题看似简单，但难以求得最优解，只能在有限时间内尽可能的找到近似最优解，故该问题是组合优化中 的NP—hard问题． 针对TSP在许多领域得到了广泛的应用，如交通路由、集成电路制造等．针对不同的应用领域，存在 多种求解 P的方法 ，如贪心算法、遗传算法I41、蚁群算法[5~91、湖水能量算法6[1、粒子群优化算法7-【s]、闭环 DNA算法 q【等．其中，郭涛等[1]给出的遗传演化算法具有运算速度快的优点，它能较快找到近似最优解 ，其 缺点是一般情况下不易找到最优解．蔡之华等3]【给出了一种改进的求解 TSP问题的演化算法，此算法是在 郭涛算法的基础上进行改进 ，并对于CHN144实例进行了 1O次的测试 ．实验结果表明有7次可找到最优 解．冯翔等[61给出了湖水能量算法，该算法优点在于求解速度快，但一般情况下只能找到近似最优解． 针对该问题，本文引入了一种新的运算方式：基因片段插入，并利用此运算给出了一种求解旅行商问 题的演化算法．算法以TSPLIB中的四个实例进行验证，结果表明所提算法能够 以较高的概率找到旅行商 问题的近似最优解． 1基于基因片段插入运算的演化算法 对于给定n个城市{1，2，…，nl，及每个城市相应的坐标，可求得两两城市之间的距离 (用dist(i，j)表示 城市i与城市j之间的距离)．文中用a，a，…，a