多种群退火贪婪混合遗传算法的研究与应用

【作者】 任刚；

【导师】 王文义；

【作者基本信息】 郑州大学 ， 计算机软件与理论， 2005， 硕士

【摘要】 遗传算法是一种模拟自然界生物进化的搜索算法,由于它简单易行、鲁棒性强,尤其是不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程,从而使它的应用范围极为广泛,并且已在众多领域得到了实际应用,取得了令人瞩目的成果,引起了广大学者和工程人员的关注。遗传算法是一种新兴的技术,正处于发展期。虽然在应用领域获得了丰收,但其理论基础还较薄弱,有许多地方需要研究和发展充实。 近几年来,基于遗传算法求解旅行商(TSP)问题的研究相当活跃。在遗传算法研究中,TSP问题已被广泛地用于评价不同的遗传操作及选择机制的性能。 人们对遗传算法甚是喜爱,但是在具体应用的过程中,其表现并不尽如人意。众所周知,遗传算法有两个严重的缺点,即容易过早收敛,以及在进化后期搜索效率较低。本文在此背景下,针对遗传算法上述的两个缺点提出了一种新型混合遗传算法:多种群退火贪婪混合遗传算法(Multi-group Annealing Greedy Hybrid Genetic Algotithm,MAGHGA)。该算法将局部搜索能力较强的贪婪算法引入遗传算法,并且同模拟退火算法和多种群并行遗传进化思想有机地结合起来。仿真结果表明,该算法避免了遗传算法中存在的早熟收敛的问题,增强了算法的全局收敛性,并且提高了算法的收敛速度。 然后,本文使用改进后的算法,针对旅行商问题进行求解,重新计算了中国三十一个省会城市的遍历最短路径,其结果较已知的最优解缩短了500公里,表明了算法的可行性和高效性。 最后,指出了本文算法的缺点及其局限性,及其以后需要努力的方向。更多还原

【Abstract】 The genetic algorithm is a kind of searching method which simulates the natural evolution. It is simple and easy to implement, especially it doesn’t need the special field knowledge, so it has been used in every broad fields. Now the genetic algorithm has got a lot of fruits and more scholars begin to pay attention to it.The genetic algorithm is still a new developing technology. Despite its success in so many domains, its theoretical fundament is relatively weak. There are still lots of problems to be studied and improved.Firstly, this paper has done some work in the research and application of the genetic algorithm. A new hybrid genetic algorithm is derived, that is the multi-group annealing greedy hybrid genetic algorithm. Greedy algorithm which has more local search ability is imported to this algorithm and is well combined with the ideas of simulated annealing and multi-group parallel evolution in this paper. Simulation results show that this method not only avoids the premature convergence problem existed in genetic algorithms, but also enhances the globe convergence, thus improves the convergence velocity.Secondly, the algorithm that is improved is presented for TSP problem in this paper. By using the improved algorithm, this paper recalculates the shortest route connecting all the capitals of the 31 provinces which is 500 kilometers shorter than the widely acknowledged one. The results of the experiment demonstrate that the method is valid and efficient.Finally, the present author points out the weak points, limitation of this thesis and makes a plan for further study.更多还原