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