基于路径共同顺序的TSP遗传算法  

A Genetic Algorithm Based on Common Path for TSP

作　　者：张金强[1] 操云甫[1] 王常青[1] 戴国忠[1] 杨富春[1] 

机构地区：[1]中科院软件研究所,北京100080

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

基　　金：国家863高技术研究发展计划基金(编号:2001AA414610;2002AA111080;2002AA414010)

摘　　要：遗传算法是一种解决TSP问题的有效算法。文章提出了一种基于路径共同顺序的新型遗传操作方法,即首先寻找父辈的共有路径信息,然后构建后代,该方法缩小了搜索优解的范围,加快了优化过程的收敛速度。在此基础上针对TSP实例,实现了基于共同顺序的优化方法来解决小规模TSP问题,以及更有效的基于共同顺序的循环优化方法来解决大规模TSP问题。实验结果验证了该方法的有效性。Genetic algorithm is a promising approach for solving Traveling Salesman Problem(TSP).This paper presents an original GA operator that first finds the common path of two parent paths and then constructs the child paths.This approach constructs offspring based on common path,decreases the search space of optima and accelerates optimal con-vergent rate.For TSP problems ,first an optimal method based on common path for TSP of small scale is given,then a more efficient method based on common path with loop optimization for TSP of large scale is given.Experiment analysis proves its efficacy.

关 键 词：共同顺序 遗传算法 TSP 

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