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

作者：陈斌; 刘卫国^*

来源：计算机科学与探索, 2021, 15(09): 1680-1693.

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

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

• 单位
  中南大学; 自动化学院