基于遗传算法的TSP问题求解算法及其系统

A TSP Solving Algorithm and System Based on Genetic Algorithm

TSP问题为组合优化中的经典的NP完全问题。针对这一问题,首先设计了基于遗传算法的求解算法,包括编码设计、适应度函数选择、终止条件设定、选择算子设定、交叉算子设定以及变异算子设定等,给出了基于遗传算法求解TSP问题的一般性流程,然后设计并实现了基于遗传算法的TSP问题求解系统,给出了求解系统的体系结构,并给出了求解系统基于Ja-va语言的实现机制,最后通过实验结果的分析,表明了算法具有较好的寻优性能,系统具有较好的实用性。

TSP is a representative combinational optimization problem and a NP-hard problem. Solving algorithm based on genetic al- gorithm is designed, including chromosome encoding, fitness function design, end condition design, selection operator design, crossover operator design and mutation operator design et al. Then a solving system is designed and implemented： the architecture of solving system is given and implementation mechanism based on Java language is presented. Finally, it is illustrated that the algorithm has good performance and the system has good practicability through analysis of experimental results.