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

传统的遗传算法通常被认为是自适应的随机搜索算法．该文在分析其特点后针对TSP问题提出了一种将建立基因库(Ge)与遗传算法结合起来的新算法(Ge-GA)．该算法利用基因库指导种群的进化方向，并在此基础上使用全局搜索算子和局部搜索算子增强遗传算法的“探测”和“开发”能力．Ge-GA算法大大加快了遗传算法的收敛速度和寻优能力．作者测试了TSPLIB中的多个实例(城市数目从70～1577)，试验结果与最优解的误差都不超过0．001％．特别是对于难求解的TSP问题，如att532和fl1577，都能够在理想的时间内找到最优解．

A Gene-Based Genetic Algorithm for TSP

Based on the analysis of traditional genetic algorithms(GA),which are always regarded as self-adaptive and stochastic,a novel method called Ge_-GA is proposed. It combines gene pool (Ge) and GA so as to direct the evolution of the whole population. Based on gene pool,Ge_-GA aims to enhance the ability of exploration and exploitation by incorporating global search with local search,which largely improves the convergence speed and ability of finding optimal solutions. The algorithm is applied to 11 well-known traveling salesman problems whose numbers of cities are from 70 to 1577. For each test instance,the average value of solution quality stays within 0.001% from the optimum. Especially for some notorious hard problems,such as att532 and fl1577,it is able to find their optimal solutions in acceptable time.