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

Improved partheno-genetic algorithm for solving addressable multiple traveling salesman problem

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

Multiple Traveling Salesman Problem(MTSP)is a generalized Traveling Salesman Problem(TSP).Compared to TSP,MTSP is more common in real-life applications.In this paper,in order to solve the minmax MTSP with non-prespecified single depot and closed path,we propose an addressable improved partheno-genetic algorithm with the reproductive mechanism of invasive weed optimization,called RAIPGA.In RAIPGA,a new encoding method is designed to generate individuals with random depot in the population initialization,and the reproductive mechanism is used to generate offspring to accelerate the convergence speed;then the improved partheno-genetic algorithm is employed to optimize the path,and finally a mixed selection operator is used to avoid premature convergence of the algorithm.In order to verify the effectiveness of RAIPGA,several instances of different sizes in the TSPLIB database was simulated using MATLAB.The experimental results show that RAIPGA has good performance in finding the best depot and the shortest path and can find good application in the problem of tourism route planning.