关键词:
旅行商问题
多任务优化
智能水滴算法
动态生灭
遗传算法
模拟退火
摘要:
针对基本智能水滴(IWD)算法求解旅行商问题(TSP)时易陷入局部最优的缺陷,文章对IWD算法进行了改进,设计了一种动态虚拟多任务智能水滴(DVMIWD)算法。首先,根据多任务优化思想,在IWD算法中引入了主辅种群,构建虚拟多任务环境,增强种群多样性。然后,在主种群中将IWD算法结合遗传算法,辅助种群中将IWD算法结合带2-opt的模拟退火(SA)算法来跳出局部最优。最后,针对辅助种群由于停滞进化而无法辅助主种群进化的现象,引入动态生灭策略重新生成辅助种群。实验结果表明,在基本IWD算法未能收敛至最优解的部分中低维TSP测试实例中,DVMIWD算法均可收敛至最优,而在高维测试实例中DVMIWD算法结果提升了约1.15%。