动态虚拟多任务智能水滴算法求解TSP问题

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

关键词：旅行商问题；多任务优化；智能水滴算法；动态生灭；遗传算法；模拟退火

中图分类号：TP391 文献标识码：A

文章编号：1009-3044（2025）06-0015-07开放科学（资源服务）标识码（OSID）：

0 引言

智能水滴（Intelligent Water Droplet，IWD）算法作为一种模拟自然界水滴在地形上流动和沉积的过程来寻找最优解的群体智能算法[1]，因其在处理组合优化类型问题时展现出了显著优势而受到广泛关注。然而，与其他群体智能算法类似，IWD算法也存在因种群多样性缺失而容易陷入局部最优的缺陷。为解决该问题，马龙等[2]将具有较强全局搜索能力的鸽群算法引入IWD中，以扩大IWD算法的搜索范围；王涛等[3]对IWD算法中的泥土更新方式进行了改进，并在此基础上引入了启发式因子和遗传算法的选择、交叉及重组算子，以增强IWD算法的种群多样性；吴中华等[4]重新定义了传统IWD算法中的泥沙量，并引入距离启发因子，使得水滴更加依赖路径质量，避免IWD 算法早熟收敛；Hesar A S[5]在IWD算法中引入局部搜索策略，使得IWD算法能快速逼近全局最优解。

多任务优化是指挖掘群体智能算法的潜在并行特征，并基于多因子优化（Multifactorial Optimization，MFO）[6] 和多种群演化（Multi-population Evolution，MPE）[7]信息共享框架，达到同时处理多个任务的目的。然而，信息负迁移会遏制干扰多任务优化性能，这也是目前多任务优化领域尚未完全解决的难题之一。受同时处理相似任务能显著加速任务收敛速度的启发，徐江等[8]构造虚拟多任务环境，引入多个辅助种群协助主种群，在降低主种群优化难度的同时，也加快了主种群的进化速度。然而，在实际应用中，辅助种群也存在因早熟收敛从而无法协助主种群进化的现象，为解决该问题，本文构造动态虚拟多任务环境，引入两个辅助种群协助主种群进化，当辅助种群连续多代停滞进化而无法协助主种群时，基于达尔文“适者生存、不适者淘汰”原则淘汰掉该辅助种群，并基于精英解信息库重新生成一个同等规模的辅助种群，从而加速辅助种群对主种群的优化进度。

旅行商问题（Travelling Salesman Problem，TSP）作为一个经典的组合优化问题，在现实生活中得到了广泛的应用。魏志刚等[9]基于AutoLISP编程生成TSP路线，利用TSP路线实现电气施工图中最短路径自动布线；芮宏斌等[10]在求解机器人巡检规划问题时，采用TSP模型来确定巡检顺序，通过将巡检点视为城市、路径距离或代价作为边权重，将巡检任务转化为经典路径优化问题；胡蓉等[11]通过分解技术将多车场多车型绿色车辆路径问题转化为一系列TSP问题后简化求解；董玮明等[12]基于TSP问题结合排队等待、道路拥挤度、出口选择设计TOTRP模型并采用粒子群遗传混合算法进行求解。

这些实际应用都可以通过转变为TSP问题来解决，然而随着问题规模增大，计算难度激增，越来越多的方法被提出用以求解TSP问题。其中多任务优化在求解TSP问题[13]时性能已得到较好证明，而IWD算法中水滴流动寻找最优路径的过程与TSP问题寻找最短路径的过程相似，通常能很快找到一个近似解。因此，本文以IWD算法为基础，引入主辅种群，模拟多任务优化，设计动态虚拟多任务智能水滴（DynamicVirtual Multi-tasking IWD，DVMIWD）算法，并将其应用于TSP问题中。

本文主要创新点如下。

1）基于IWD算法优秀的并行性，在IWD算法中引入虚拟多任务优化思想，在IWD算法设置主辅种群，辅助种群通过优秀解信息库向主种群迁移信息辅助主种群寻找最优解。