Abstract: 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.

Key words: multiple traveling salesman problem, genetic algorithm, reproductive mechanism, local optimization, invasive weed optimization algorithm, mutation operator

摘要： 针对工作量平衡的多旅行商问题，提出了一种融合杂草算法繁殖机制和局部优化变异算子的改进遗传算法（Reproductive mechanism and Local optimization mutation operator based Genetic Algorithm，RLGA）。该算法利用入侵杂草优化算法中以适应度为基准的繁殖机制来产生种群并进行遗传操作，以此来提高算法的搜索效率；同时提出一种混合局部优化算子作为变异算子来提高算法的局部搜索能力，从而提高收敛精度。实验结果表明，RLGA在求解工作量平衡的多旅行商问题时可以快速收敛到较优解，并且求解精度得到了很大的提高。

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