遗传算法在旅行商问题的研究与应用

旅行商问题（TSP）是一类典型的非确定性多项式（NP）完全组合优化问题.针对基本遗传算法在求解这类问题时容易出现局部收敛现象,提出了改进,采用轮盘赌和优秀个体复制相结合的方法进行选择,对11个城市的旅行商问题进行研究,通过比较发现取得良好的收敛,该方法在解决很多NP完全组合优化问题上同样适用.

Travelling Salesman Problem Based on Genetic Algorithm

Traveling Salesman Problem （TSP） is a typical non-deterministic polynomial （NP） complete combinatorial optimization problem.Since basic genetic algorithm prone to have the phenomenon of local convergence in solving such issues,an im- proved algorithm proposed.Combining roulette and excellent individuals copy to select,conduct research on traveling sales- man problem of 11 cities.By comparing,obtain good convergence.This method also applies in solving many NP-complete combinatorial optimization problems.