基于交叉算子改进的遗传算法求解TSP问题

摘要

遗传算法容易产生早熟现象以及局部寻优能力较差的缺陷.针对遗传算法的这一缺点,就遗传算法的交叉算子进行改进,并应用于求解旅行商问题.传统的交叉算子操作方法寻优效率低,并易陷入局部最优,就顺序交叉方法进行改进.改进后的交叉算子是在随机选择交叉区域和交叉片断长度后.对重复节点和前后节点的路径长度进行比较后.再删除路径长的重复节点,有效地提高了算法的寻优效率,优化了解的质量.为了验证算法的有效性,对TSPLIB库中的两个公共实际事例eil51和gr202以及安徽省17个城市的数据进行了仿真实验,结果表明改进后的算法是有效的.