摘要
TSP问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种方法。文章针对TSP问题,提出了一种改进的遗传算法。在遗传算法中引入进化算法的思想,在此基础上提出顶端培育策略和分阶段策略,以求在保证群体多样性的同时加快收敛速度。在算法的仿真和测试中,改进后的算法明显优于传统的遗传算法。这表明,该算法具有良好的可行性和实用性。
TSP (Traveling Salesman Problem) is a typical NP-complete problem,and the genetic algorithm (GA) is the method for solving NP-complete problem. The paper, in order to solve the problem well, puts forward a new the genetic algorithm, which use dividing periods , encouraging top and mind evolutionary computation(MEC) to enhance the convergence speed without deteriorating diversity of population. According to the analysis and test, the improved genetic algorithm can get the better result than the traditional genetic algorithm. This shows that the method has better feasibility and practicability.
出处
《微机发展》
2004年第6期21-23,共3页
Microcomputer Development
关键词
旅行商问题
遗传算法
进化算法
traveling salesman problem(TSP)
genetic algorithm
mind evolutionary computation
