求解TSP的變鄰域蝙蝠算法

朱德鑫，蔡延光

（廣東工業大學自動化學院，廣東廣州，510006）

0 引言

旅行商問題(Traveling Salesman Problem，TSP)是一個經典的NP-hard組合優化問題。該問題具有重要的工程應用價值，在車間調度、物流運輸等領域都有其應用。

蝙蝠算法(BA)是一種受啟發于蝙蝠覓食行為的算法，最早由Yang Xin-she于2010年提出。自然界中蝙蝠利用自身獨特的生物結構，通過超聲波探測的信息定位周圍環境和獵物，以進行規劃飛行路線和捕食獵物。蝙蝠算法就是模仿此類行為而創造的一種新型群體智能優化算法。目前在車間調度、工程優化等領域中均得到應用。

本文提出一種變鄰域蝙蝠算法(VNBA)，在傳統蝙蝠算法上混合三種變鄰域策略改善算法局部特性，同時加入慣性權重平衡算法前期的全局搜索和后期的局部搜索，改善傳統算法易陷入局部最優的困境。

1 旅行商問題的數學模型

旅行商問題可以描述為：一名銷售員需要去往N個城市進行銷售，已知各個城市的具體位置以及城市與城市間的具體距離，現需要規劃一條路線，使得該路線能夠經過每一個城市，且每個城市僅被經過一次，并最終回到出發點，同時總行程最短。假設遍歷所有城市后形成的路線為：，則最短路徑的求解為：

其中，式（1）表示最小化路程，式（2）表示兩個城市間的距離。

2 變鄰域蝙蝠算法設計

2.1 蝙蝠速度和位置更新

蝙蝠算法的速度、位置更新公式如式(3)(4)(5)所示。其中β∈[0, 1]是從均勻分布中抽取的隨機量。fmin和fmax代表種群脈沖頻率上下限，fi代表第i只蝙蝠個體的脈沖頻率，x*則代表當前代數下全局最優的蝙蝠所處位置，表示t+1時刻下蝙蝠個體的位置和速度。

2.2 蝙蝠響度和發射頻更新

當蝙蝠最優解更新時，調整蝙蝠個體響度A和發射頻r：

2.3 變鄰域策略

雖然在求解較為復雜的組合優化問題上，蝙蝠算法具有較好的全局搜索能力，但在求解后期時，蝙蝠算法容易出現收斂精度較低和陷入局部極值的問題，為此加入三個鄰域策略，以提高算法的搜索性能。

（1）2-opt策略

（2）exchange策略

（3）insert策略

在變鄰域蝙蝠算法的迭代過程中，為使局部搜索性能更優，搜索空間更為多樣性，將同時使用以上三種策略，在對當前某個蝙蝠個體的解Xi使用某一鄰域搜索后產生新解Xnew，若新解比原解更優則替換掉原解且在當前鄰域中繼續搜索，否則保留原解進入下一個鄰域搜索，達到設定的迭代次數后，停止鄰域搜索并保留鄰域搜索最優解。

2.4 慣性權重

由蝙蝠算法速度更新公式可知，當蝙蝠算法的速度更新時，會將當前蝙蝠與全局蝙蝠對比更新以此達到加快收斂速度的目的，但這也容易讓蝙蝠算法陷入局部最優，為了平衡好算法的全局和局部的搜索能能力，使得蝙蝠算法能夠在算法搜索的前期能有更好的全局尋優能力，在算法搜索的后期能有更好的局部尋優能力，此處在蝙蝠速度更新中加入慣性權重ω，加入慣性權重后的公式如式(8)：

其中ω的設置為了契合旅行商問題，將其離散化，具體權重ω如式(9)：

其中，t為算法當前迭代次數，T為全局最大迭代次數。由式子可知，在算法前期，慣性權重較小，增強全局搜索能力，后期慣性權重大，使得與上一代蝙蝠的關聯性增大，提升局部搜索能力。

2.5 算法步驟

在蝙蝠算法中加入三種變鄰域優化策略和慣性權重后，VNBA算法步驟如下：

Step1：初始化變鄰域蝙蝠算法種群。

Step2：通過計算個體適應值找出蝙蝠種群中的最優蝙蝠蝙蝠，并記錄對應個體的位置及其適應度值。

Step3：根據公式(1)(9)(3)更新每一只蝙蝠的脈沖頻率fi、速度vi和位置xi，求解當前每只蝙蝠對應的適應度值，并與上一代的適應度值做比較，保留更優的個體。

Step4：隨機生成一個隨機數R1，若R1大于ri，則將全局搜索的最優蝙蝠個體進行三種變鄰域搜索，否則保留原來的最優蝙蝠個體。

Step5：再隨機生成一個隨機數R2，若該數R2小于當前蝙蝠個體的響度Ai且新個體的適應度優于原個體的適應度時，則接受Step4中的個體解。同時更新個體i的響度A以及其脈沖發射率ri，否則不對其響度以及脈沖發射率進行更新。

Step6：計算全部個體對應的適應度值并作對比排序，尋找到當代全局最優解。

Step7：重復步驟Step3到Step6，直到迭代次數超過最大迭代次數時停止迭代，并且輸出全局最優解。

3 實驗仿真及分析

實驗選取5組TSP標準算例作為實驗算例，并與遺傳算法(GA)和蟻群算法(ACO)作對比。VNBA算法參數為：種群大小N=100，脈沖頻率fmin=0，fmax=1、脈沖響度A=0.9、脈沖發射率ri=0.9、常數α=0.9，γ=0.9、慣性權重ωmin=0.2，ωmax=1；GA算法參數為：種群大小N=100，變異概率Pm=0.05、交叉概率Pc=0.95、代溝GGAP=0.9；ACO算法參數參數為：種群大小N=100，信息素因子α=1，啟發函數因子β=5，信息素揮發因子ρ=0.1，信息素釋放總量Q=1。每組算例測試20次。

由表1可知，VNBA算法Oliver30和Att48能找出最優解，其優化后的路徑如圖1、2所示。在求解50個點以上的TSP算例時，VNBA也能尋找到較優的解，且誤差都在5%以內。同時VNBA的在各個算例的最優解都要優于GA、ACO算法的解，證明VNBA在求解TSP問題時的全局尋優性能更優。同時VNBA在各個算例中的平均解也更優，且平均解和最優解的差距較小，證明了VNBA算法也有較好的求解穩定性。

表1 各算法性能對比分析

圖1 VNBA優化后的Oliver30路徑圖

圖2 VNBA優化后的Att48路徑圖