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

在分析了已有的求解TSP问题的优化算法后，提出了一种将建立基因库(Ge)与遗传算法结合起来的新算法(Ge_GA)。该算法的目的是用基因库指导整个种群的进化，其核心问题是基因库的建立及如何将基因库运用到遗传算法中。试验结果表明，基因库有效地提高了群体演化的质量，局部搜索与全局搜索的结合大大提高了算法收敛速度。对于每个测试的实例，其结果与最优解的误差都不超过0.001％。特别是对难于求解的TSP问题，如pcb442和n1577，都能够在理想的时间内找到最优解。

A Gene Pool-based Genetic Algorithm for TSP

Based on the analysis of previous genetic algorithms (GAs) for TSP, a novel method called Ge_GA is proposed. It combines gene pool and GA so as to direct the evolution of the whole population. The core of Ge_GA is the construction of gene pool and how to apply it to GA. The experiments results indicate that Ge_GA has great robustness for TSP. 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 pcb442 and fl1577, it is able to find their optimal solutions in acceptable time.