基于构建基因库求解TSP问题的改进遗传算法  

A Modified Genetic Algorithm Based on Gene Pool for TSP

作　　者：董子乐[1] 范俊峰[1] 胡纯德[1] 

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

出　　处：《计算机工程与应用》2005年第36期42-43,88,共3页Computer Engineering and Applications

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

摘　　要：文章针对TSP问题设计了一种将基因库和遗传算法结合起来的新算法,该算法首先构建一个基因库,在单亲演化中利用基因库指导种群的进化方向,其次在此基础上采用单亲进化遗传算法中的基因重组操作,保留每次获得的最好解组成初始种群,最后采用顺序交叉算子进行群体演化。给出的实验结果显示,该算法所获得的解与最优解的相对误差都不超过2%,该算法的收敛速度和寻优能力明显优于该问题的单亲进化遗传算法。This paper presents a new algorithm which combines gene pool and Genetic Algorithm.First of all,the algorithm structures a gene pool during the single-parent evolution so as to direct the evolution of the whole population.Secondly,it performs gene reconstruction operations based on gene pool to produce the offspring in the Partheno Evolution Genetic Algorithm.The best solution is to be saved each time to form the initial population.Finally,it performs order crossover operator to march the population evolution process.The experiment results show that the average value of solution quality stays within 2% from the optimal solution for each test instance and the proposed algorithm is better than the Partheno Evolution Genetic Algorithm for this problem on the convergence speed and capability of searching for optimal solution.

关 键 词：TSP问题 基因库 遗传算法 基因重组 

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