改进快速单亲遗传算法解均衡多旅行商问题

摘要：

均衡多旅行商问题(Balanced Multiple Traveling Salesman Problem,BMTSP)被广泛应用在诸如多人协作、任务分担等情形中.针对该问题提出一种改进快速单亲遗传算法(Improved Fast Partheno-Genetic Algorithm,IFPGA)进行求解.首先,基于图论知识完善了BMTSP问题的数学模型;其次,强化和改进了单亲遗传变异策略,将四种常用变异算子"移位、倒序、左移、右移"与随机插入操作相结合,以此大幅增加种群多样性和迭代后期的局部寻优能力;经过精英策略优选后,基于最近邻点策略对种群每一个个体中路程最长的旅行商回路进行局部优化,增强了算法的全局寻优能力.实验结果表明,IFPGA算法设置的策略对算法的性能提升明显,求解算例时IFPGA算法的收敛速度和求解精度得到了很大的提高.

关键词：多旅行商问题、数学模型、单亲遗传算法、最近邻点策略、局部优化

所属期刊栏目：34

分类号：TP301(计算技术、计算机技术)

资助基金：四川省教育厅自然科学基金重点项目;四川省科技计划;西华师范大学英才基金资助项目

在线出版日期：2022-08-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：96-105