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

来源：计算机科学与探索杂志2021年第9期北京时间：

作者：陈斌, 刘卫国

单位：1. 中南大学 自动化学院，长沙 4100832. 中南大学 计算机学院，长沙 410083

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

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