基于基因库求解TSP的改进的反序—杂交算法  

An Improved Inver-over for TSP Based on Gene-pool

作　　者：卿翊轩[1] 康立山[1] 陈毓屏[1] 

机构地区：[1]武汉大学软件工程国家重点实验室,武汉430072

出　　处：《计算机工程与应用》2005年第7期37-39,共3页Computer Engineering and Applications

基　　金：国家自然科学基金(编号:70071042;60073043;60133030)

摘　　要：文章对求解TSP的“反序-杂交”算法在反序时城市位置的选择方式上作了改进,同时限制对每个个体一次循环中反序的次数,提出一种“见好就收”的策略,并利用“基因库”(即保存了好边的矩阵)的思想来指导反序-杂交。实验证明,改进的算法在收敛性和求解速度方面都比原来经典的“反序-杂交”算法有很大的提高。In this paper,the inver-over algorithm for TSP is modified in the way of selection of location of city when inversed.A strategy called stop when improved is presented,which limits the times that every individual is inversed in one circle,and the idea of the gene-pool(the matrix keeping good edges) is implemented to direct the inver-over.Ex-periments prove that the modified algorithm is improved a lot on the convergence and efficiency compared with the classic inver-over.

关 键 词：旅行商问题 反序-杂交 见好就收 基因库 

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