两阶段遗传算法在求解TSP问题中的应用

作者：张启义; 邱国庆; 寇学智; 陈亮

来源：L201101016, 2011, (01): 79-83.

• TSP
• 种群多样性
• 贪婪优化遗传算法
• 退火单亲遗传算法
• 两阶段遗传算法 traveling salesman problem
• population diversity
• greedy optimization genetic algorithm
• annealing partheno genetic algorithm
• two-stages genetic algorithm

为了提高利用遗传算法求解TSP(traveling saleman problem)问题的能力,给出了一种种群多样性的定义,提出了一种利用2个阈值在贪婪优化遗传算法和退火单亲遗传算法间切换的两阶段遗传算法,从而可以在保持种群多样性的基础上优化种群。两阶段遗传算法在种群多样性下降到一定程度时,转换遗传方式,在继续寻优的同时,很快提高种群的多样性,当种群多样性上升到一定程度,又转换为原来的算法,如此重复。仿真算例结果表明:两阶段遗传算法收敛速度和全局搜索能力都得到了较大提高,其平均最优解、平均收敛代数和平均耗时优于或与另两种遗传算法相当。

• 单位
  中国人民解放军陆军工程大学; 中国人民解放军汽车管理学院