一种基于逆转算子的求解TSP问题的改进演化算法

使用逆转算子求解TSP的演化算法具有很强全局搜索能力,在求解TSP问题中显示了巨大的优势。但是,该算法同样存在执行效率低、最终得到的最优个体整体质量不高等缺陷。在对算法和TSP问题进行分析的基础上,对算法进行三方面的改进:就近选择;动态变异概率;基于较优个体的贪婪搜索。实验结果表明:经过改进的算法提高了执行效率,能够改善算法得到的最优个体的整体质量。

An Improved Evolutionary Algorithm for Traveling Salesman Problem Based on Inver-Over Operator

The evolutionary algorithm using inver-over operator for the traveling salesman problem(TSP) has great ascendancy,because its ability in global searching for optimal individual is powerful.However,it has the some limitations: low executive efficiency and the dissatisfactory average individuals obtained by algorithm.To avoid these limitations,improves the algorithm mentioned above in three aspects: close-by visit method,dynamic mutation probability and greedy search based on preferable individuals.A desirable result is obtained.It is showed by the experiment that the algorithm can be executed with high efficiency and the average quality of the optimal individual of the algorithm is improved.