一种求解旅行商问题的新型单亲遗传算法  

A New Partheno-Genetic Algorithm for Traveling Salesman Problem

作　　者：胡纯德[1] 祝延军[1] 高随祥[1] 

机构地区：[1]中国科学院研究生院,北京100039

出　　处：《计算机工程与应用》2004年第35期37-40,共4页Computer Engineering and Applications

基　　金：国家863高技术研究发展计划重大专项(编号:2002AA103061);国家自然科学基金项目(编号:10171095)资助

摘　　要：论文针对旅行商问题,提出了一种新型的单亲遗传算法。它在同一条染色体上采用基因换位、基因段移位、基因段逆转和基因分组定界等操作进行基因重组,取消了传统遗传算法中的交叉算子,遗传操作简单,收敛速度快。但过早的收敛将影响结果精度,使全局最优解的出现机率很小。为此,该算法模拟自然界演化的周期性,使用基因插入操作增强算法的搜索能力,并提出运算终止的两个准则,使所得的解为全局最优解的可信度大为提高。给出了该算法的数值算例,实验结果表明,该算法较好地解决了收敛速度和寻优能力的矛盾,证明了该算法的有效性。In this paper,a new Partheno-Genetic Algorithm(PGA)is presented to solve TSP.It performs gene recon-struction operations to produce the offspring such as gene exchange,moving and inversion on a single chromosome ,instead of traditional crossover operator.Compared with traditional Genetic Algorithm,the genetic operations are simpler and the convergence speed is faster in PGA.However,too early convergence will effect the precision of the result and minimize the probability to gain the global optimal solution.Therefore,the proposed algorithm simulates the recurrence of nature evolution process,and the insertion operation is designed to ensure its strong searching capability.And two principles of calculation ceasing are put forward,which make the solution thus gained as the global optimal solution greatly promote the reliability.Numerical example based on the design is given.The experiment results show that the proposed algorithm solves the contradiction between the convergence speed and the capability of searching for global optimal solution.Through experiments,the validity of the algorithm is proved.

关 键 词：旅行商问题 单亲遗传算法 基因重组 组合优化 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] O242.23[自动化与计算机技术—计算机科学与技术]