求解寻址多旅行商问题的改进单亲遗传算法

作者：胡士娟; 鲁海燕^*; 黄洋; 许凯波

来源：东北师大学报(自然科学版), 2019, 51(04): 49-56.

DOI：10.16163/j.cnki.22-1123/n.2019.04.010

• 多旅行商问题
• 单亲遗传算法
• 寻址
• 繁殖机制
• 选择算子
• 旅游路径规划

为了解决非预先指定起点的单起点、闭回路且目标函数最长、路径最短的多旅行商问题,提出一种融合杂草算法繁殖机制的可寻址混合单亲遗传算法.该算法首先给出了一种新的编码方式,可在种群初始化时产生含有随机配送中心的个体,同时算法采用杂草算法的繁殖机制产生子代,从而加快收敛速度;然后采用改进的单亲遗传操作对路径进行寻优;最后采用混合选择算子对群体进行求解精度选择,避免算法陷入早熟收敛.为验证所提出的改进算法的有效性,采用Matlab对TSPLIB数据库中若干不同规模的实例进行仿真.实验结果表明,该算法在寻找最佳配送中心和最短路径方面具有良好的性能,且能在旅游路径规划问题上得到良好的应用.

• 单位
  江南大学