一种基于遗传算子优化组合的TSP问题求解方法

A solving TSP algorithm based on genetic combination operator

一般遗传算法求解旅行商问题时,存在着搜索速度与求解质量之间的矛盾.针对此问题提出了一种逆序与对偶组合算子,用以增强遗传算法的局部搜索能力.将其与具有良好全局搜索模式的均匀杂交算子优化组合应用,采用自然数和二进制相互转换的编码方式,构造了一种对TSP问题进行求解的遗传算法,保证了算法的全局收敛性.仿真实验结果表明,该求解方法具有良好的搜索效率和求解质量.

It is difficult for general genetic algorithms（GA） to avoid premature convergence and to raise the speed of algorithm convergence in solving the traveling salesman problems（TSP）.In this paper,a inverse and dual combination operator is proposed as a new genetic operator to improve genetic algorithm local searching,and a solving TSP genetic algorithm that combines uniform crossover operator which has better global searching with the new genetic operator is designed.Besides a coding transform between integer and binary is introduced to make good use of the combination operators.It is proved to be convergent,and the better efficiency of the solving algorithm has been shown by simulative experiments.