摘要
旅行商问题(Traveling Salesman Problem TSP)是一个典型的组合优化问题,但应用基本遗传算法求解TSP问题时存在许多不足.结合TSP问题的特点,提出一种改进的遗传算法:应用贪心策略初始化种群,用2-opt对其进行优化,使得在初始个体中就包含较优子路径,在一定程度上加快算法收敛性,防止早熟和近亲繁殖.对交叉算子和变异算子进行改进后,既能维持种群的多样性,也保留了父代个体大部分优良性能.应用改进的算法对20个城市的TSP问题进行求解,结果表明该算法求解速度快而且求解的质量较好.
Traveling Salesman Problem （TSP） is a classical combinatorial optimization problem. Genetic algorithm （GA） is a method for solving this problem. But it is hard for GA to find global optimization quickly and prevent premature convergence. Considering the characteristic of TSP, this paper puts forward an improved genetic algorithm, that is, using greedy strategy to initialize species, using 2-opt operator to optimize it so that the initialized individuals contain optimized paths, which quickens the convergence of the algorithm to some degree and protects prematurity and close relative reproduction. After improving cross operator and mutation operator, the diversity of population and most of the good performance of last generation can be maintained. And the improved algorithm is used to solve TSP problem in 20 cities and the experimental result indicates that the algorithm is fast and has good solutions.
出处
《重庆工学院学报》
2007年第9期86-90,共5页
Journal of Chongqing Institute of Technology
基金
重庆市教委科学研究基金资助项目(KJ050809)
