基于旅行商问题的改进遗传算法研究

针对遗传算法在解决旅行商问题时容易出现局部最优和收敛速度慢的问题,提出了一种新的改进遗传算法。针对遗传算法的基本算子进行改进,初始种群采用贪婪算法生成优质种群,使得寻优速度得到提高;改进交叉算子引入一种新的交叉模型,保证算法的收敛速度、进化方向以及种群多样性;最后还加入了进化逆转操作,保留亲代较多信息,增强搜索能力。通过仿真实验所显示结果表明,改进后的遗传算法与传统的遗传算法对比精确性和收敛速度均有显著提高。

A new improved genetic algorithm is proposed to solve the problem that local optimization and convergence speed are easy to be solved when solving the traveling salesman problem.The basic operator of the genetic algorithm is improved, and the initial population uses the greedy algo- rithm to generate the high quality population, which makes the optimization speed improved.The improved crossover operator introduces a new cross model to ensure the convergence speed, evolution direction and population diversity： Finally joined the evolutionary reversal operation, to retain more information on the parent, enhance the search ability.The results of the simulation show that the improved genetic algorithm and the traditional ~enetic algorithm have improved the accuracy and convergence rate significantly.