動(dòng)態(tài)虛擬多任務(wù)智能水滴算法求解TSP問題

摘要：針對(duì)基本智能水滴（IWD）算法求解旅行商問題（TSP）時(shí)易陷入局部最優(yōu)的缺陷，文章對(duì)IWD算法進(jìn)行了改進(jìn)，設(shè)計(jì)了一種動(dòng)態(tài)虛擬多任務(wù)智能水滴（DVMIWD）算法。首先，根據(jù)多任務(wù)優(yōu)化思想，在IWD算法中引入了主輔種群，構(gòu)建虛擬多任務(wù)環(huán)境，增強(qiáng)種群多樣性。然后，在主種群中將IWD算法結(jié)合遺傳算法，輔助種群中將IWD算法結(jié)合帶2-opt 的模擬退火（SA）算法來跳出局部最優(yōu)。最后，針對(duì)輔助種群由于停滯進(jìn)化而無法輔助主種群進(jìn)化的現(xiàn)象，引入動(dòng)態(tài)生滅策略重新生成輔助種群。實(shí)驗(yàn)結(jié)果表明，在基本IWD算法未能收斂至最優(yōu)解的部分中低維TSP測(cè)試實(shí)例中，DVMIWD算法均可收斂至最優(yōu)，而在高維測(cè)試實(shí)例中DVMIWD算法結(jié)果提升了約1.15%。

關(guān)鍵詞：旅行商問題；多任務(wù)優(yōu)化；智能水滴算法；動(dòng)態(tài)生滅；遺傳算法；模擬退火

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2025）06-0015-07開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

0 引言

智能水滴（Intelligent Water Droplet，IWD）算法作為一種模擬自然界水滴在地形上流動(dòng)和沉積的過程來尋找最優(yōu)解的群體智能算法[1]，因其在處理組合優(yōu)化類型問題時(shí)展現(xiàn)出了顯著優(yōu)勢(shì)而受到廣泛關(guān)注。然而，與其他群體智能算法類似，IWD算法也存在因種群多樣性缺失而容易陷入局部最優(yōu)的缺陷。為解決該問題，馬龍等[2]將具有較強(qiáng)全局搜索能力的鴿群算法引入IWD中，以擴(kuò)大IWD算法的搜索范圍；王濤等[3]對(duì)IWD算法中的泥土更新方式進(jìn)行了改進(jìn)，并在此基礎(chǔ)上引入了啟發(fā)式因子和遺傳算法的選擇、交叉及重組算子，以增強(qiáng)IWD算法的種群多樣性；吳中華等[4]重新定義了傳統(tǒng)IWD算法中的泥沙量，并引入距離啟發(fā)因子，使得水滴更加依賴路徑質(zhì)量，避免IWD 算法早熟收斂；Hesar A S[5]在IWD算法中引入局部搜索策略，使得IWD算法能快速逼近全局最優(yōu)解。

多任務(wù)優(yōu)化是指挖掘群體智能算法的潛在并行特征，并基于多因子優(yōu)化（Multifactorial Optimization，MFO）[6] 和多種群演化（Multi-population Evolution，MPE）[7]信息共享框架，達(dá)到同時(shí)處理多個(gè)任務(wù)的目的。然而，信息負(fù)遷移會(huì)遏制干擾多任務(wù)優(yōu)化性能，這也是目前多任務(wù)優(yōu)化領(lǐng)域尚未完全解決的難題之一。受同時(shí)處理相似任務(wù)能顯著加速任務(wù)收斂速度的啟發(fā)，徐江等[8]構(gòu)造虛擬多任務(wù)環(huán)境，引入多個(gè)輔助種群協(xié)助主種群，在降低主種群優(yōu)化難度的同時(shí)，也加快了主種群的進(jìn)化速度。然而，在實(shí)際應(yīng)用中，輔助種群也存在因早熟收斂從而無法協(xié)助主種群進(jìn)化的現(xiàn)象，為解決該問題，本文構(gòu)造動(dòng)態(tài)虛擬多任務(wù)環(huán)境，引入兩個(gè)輔助種群協(xié)助主種群進(jìn)化，當(dāng)輔助種群連續(xù)多代停滯進(jìn)化而無法協(xié)助主種群時(shí)，基于達(dá)爾文“適者生存、不適者淘汰”原則淘汰掉該輔助種群，并基于精英解信息庫重新生成一個(gè)同等規(guī)模的輔助種群，從而加速輔助種群對(duì)主種群的優(yōu)化進(jìn)度。

旅行商問題（Travelling Salesman Problem，TSP）作為一個(gè)經(jīng)典的組合優(yōu)化問題，在現(xiàn)實(shí)生活中得到了廣泛的應(yīng)用。魏志剛等[9]基于AutoLISP編程生成TSP路線，利用TSP路線實(shí)現(xiàn)電氣施工圖中最短路徑自動(dòng)布線；芮宏斌等[10]在求解機(jī)器人巡檢規(guī)劃問題時(shí)，采用TSP模型來確定巡檢順序，通過將巡檢點(diǎn)視為城市、路徑距離或代價(jià)作為邊權(quán)重，將巡檢任務(wù)轉(zhuǎn)化為經(jīng)典路徑優(yōu)化問題；胡蓉等[11]通過分解技術(shù)將多車場(chǎng)多車型綠色車輛路徑問題轉(zhuǎn)化為一系列TSP問題后簡(jiǎn)化求解；董瑋明等[12]基于TSP問題結(jié)合排隊(duì)等待、道路擁擠度、出口選擇設(shè)計(jì)TOTRP模型并采用粒子群遺傳混合算法進(jìn)行求解。

這些實(shí)際應(yīng)用都可以通過轉(zhuǎn)變?yōu)門SP問題來解決，然而隨著問題規(guī)模增大，計(jì)算難度激增，越來越多的方法被提出用以求解TSP問題。其中多任務(wù)優(yōu)化在求解TSP問題[13]時(shí)性能已得到較好證明，而IWD算法中水滴流動(dòng)尋找最優(yōu)路徑的過程與TSP問題尋找最短路徑的過程相似，通常能很快找到一個(gè)近似解。因此，本文以IWD算法為基礎(chǔ)，引入主輔種群，模擬多任務(wù)優(yōu)化，設(shè)計(jì)動(dòng)態(tài)虛擬多任務(wù)智能水滴（DynamicVirtual Multi-tasking IWD，DVMIWD）算法，并將其應(yīng)用于TSP問題中。

本文主要?jiǎng)?chuàng)新點(diǎn)如下。

1）基于IWD算法優(yōu)秀的并行性，在IWD算法中引入虛擬多任務(wù)優(yōu)化思想，在IWD算法設(shè)置主輔種群，輔助種群通過優(yōu)秀解信息庫向主種群遷移信息輔助主種群尋找最優(yōu)解。