基于SAC模型的改进遗传算法求解TSP问题

摘要：

遗传算法(GA)的全局搜索能力强,易于操作,但其收敛速度慢,易陷入局部最优值.针对以上问题,利用深度强化学习模型SAC对遗传算法进行改进,并将其应用至旅行商问题(TSP)的求解.改进算法将种群作为与智能体(agent)交互的环境,引入贪心算法对环境进行初始化,使用改进后的交叉与变异运算作为agent的动作空间,将种群的进化过程视为一个整体,以最大化种群进化过程的累计奖励为目标,结合当前种群个体适应度情况,采用基于SAC的策略梯度算法,生成控制种群进化的动作策略,合理运用遗传算法的全局和局部搜索能力,优化种群的进化过程,平衡种群收敛速度与遗传操作次数之间的关系.对TSPLIB实例的实验结果表明,改进的遗传算法可有效地避免陷入局部最优解,在提高种群收敛速度的同时,减少寻优过程的迭代次数.

关键词：强化学习;遗传算法(GA);旅行商问题(TSP);深度策略梯度;soft actor-critic(SAC)模型

所属期刊栏目：15

分类号：TP18;TP301.6(自动化基础理论)

资助基金：国家自然科学基金61073187

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

页数：共14页

页码：1680-1693