用于TSP的自适应贪婪GA算法

Adaptive Greedy GA Algorithm for TSP

TSP问题是一个典型的组合优化问题,很多现实生活中的问题都可以归结为TSP问题,GA算法是一种典型的优化算法。通过对GA算法要点的分析,提出了一种自适应贪婪GA算法,以解决TSP问题。自适应适应度函数的各种定义、定理,确保了算法的正确性。通过平均复制的方法进行选择操作,使得算法不会过早地陷入局部最优。通过建立基于哈密顿回路的双向环贪婪插入算子进行交叉操作,确保了算法收敛的高效性。最后通过实例的计算分析及与传统GA算法的比较,说明了所提出的自适应贪婪GA算法在TSP研究中能够更好地发挥作用。

TSP is a typical combinatorial optimization problem, and many real life problems can attributed to the TSP. GA is a typical optimization algorithm. Analyzing GA＇s important points, a adaptive greedy GA was proposed to solve TSP. Definitions and theorems on adaptive fitness function ensure the correctness of the algorithm. Algorithm does not prematurely fall into local optimum because of average replication method for select operations. Algorithm can be efficiently converged by establishing bidirectional ring greed insert operator based on Hamiltonian two-way loop circuit for cross operation. Finally, the calculation and analysis of the example and the comparison with the traditional GA algo-rithm show that the proposed GA algorithm can play better role in TSP study.