求解工作量平衡多旅行商问题的改进遗传算法  

Improved Genetic Algorithm for Solving Multiple Traveling Salesman Problem with Balanced Workload

作　　者：胡士娟 鲁海燕[1,2] 黄洋 许凯波[1] HU Shijuan;LU Haiyan;HUANG Yang;XU Kaibo(School of Science, Jiangnan University, Wuxi, Jiangsu 214122, China;Wuxi Engineering Technology Research Center for Biological Computing, Wuxi, Jiangsu 214122, China)

机构地区：[1]江南大学理学院,江苏无锡214122 [2]无锡市生物计算工程技术研究中心,江苏无锡214122

出　　处：《计算机工程与应用》2019年第17期150-155,231,共7页Computer Engineering and Applications

基　　金：国家自然科学基金（No.61772013,No.61402201）;中央高校基本科研业务费专项资金项目（No.114205020513526）

摘　　要：针对工作量平衡的多旅行商问题,提出了一种融合杂草算法繁殖机制和局部优化变异算子的改进遗传算法(Reproductive mechanism and Local optimization mutation operator based Genetic Algorithm,RLGA)。该算法利用入侵杂草优化算法中以适应度为基准的繁殖机制来产生种群并进行遗传操作,以此来提高算法的搜索效率;同时提出一种混合局部优化算子作为变异算子来提高算法的局部搜索能力,从而提高收敛精度。实验结果表明,RLGA在求解工作量平衡的多旅行商问题时可以快速收敛到较优解,并且求解精度得到了很大的提高。An improved genetic algorithm which combines the reproductive mechanism of invasive weed optimization and a local optimization mutation operator, called RLGA, is proposed for solving the multiple traveling salesman problem with balanced workload. It uses the fitness-based reproductive mechanism of the invasive weed optimization algorithm to produce the population and carries out genetic operation, and thereby to improve the search efficiency of the algorithm. In addition, a new hybrid local search operator is proposed as a mutation operator to improve the local search ability of the algorithm, so as to improve the convergence precision. The experimental results show that RLGA can converge to the optimal solution quickly for the multiple traveling salesman problem with balanced workload, and the precision of the solution is greatly improved.

关 键 词：多旅行商问题 遗传算法 繁殖机制 局部优化 入侵杂草优化算法 变异算子 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]