求解TSP问题的一种改进的遗传算法

An Improved Genetic Algorithm for TSP Problem

TSP问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种理想方法。文章针对解决TSP问题,提出使用改进的遗传算法,即用浓度控制选择策略以保证群体的多样性,用贪婪交叉算子和启发式倒位变异算子来提高算法的收敛速度,较好地解决了群体的多样性和收敛速度的矛盾。算法的分析和测试表明,该文算法的改进是有效的。

TSP(Traveling Salesman Problem)is a typical NP-Complete problem,genetic algorithm(GA)is the perfect method for solving NP -Complete problem.This paper,in order to solve the contradiction between the diversity of population and the convergence speed of algorithm,puts forward an improved genetic algorithm,which use density control selection operator to protect diversity of population and use greedy crossover operator and heuristic inverse mutation operator to enhance the convergence speed.As it is proved by analysis and test,a better result is obtained by the improved genetic algorithm.