基于改進的烏鴉搜索算法求解旅行商問題

孟范立

關鍵詞：旅行商；烏鴉優化算法；運算符；消除機制

中圖分類號：TP18 文獻標識碼：A

文章編號：1009-3044（2023）12-0022-04

旅行商問題（TSP）是指求解經過多個城市的最短路徑問題，適用于許多工程應用，如計算機網絡、硬件設計、交通路線設計、基因排序和電子控制系統等。例如解決n個城市在內的一個TSP問題的求解空間是n的階乘，因此TSP問題是一個典型的NP難問題。

TSP問題解決方案主要分為兩類：一種是精確求解法，可以確保獲得最優解，如分支界定法[1]。然而，隨著城市數量增加，這些方法求解時間呈指數增長。因此，精確求解法僅適用于解決小規模問題。另一種是近似求解法，雖不能保證獲得最優解但能夠在較短時間內求得近似解。如蟻群優化算法[2]、遺傳算法[3] 等算法。這些方法適用于解決大規模TSP問題。

一般來說，影響求解TSP問題近似算法的主要因素有兩個方面，一是對搜索求解空間的擴展能力，二是算法收斂到最優解的收斂能力。在研究了各種群體智能算法并對其測試結果進行評估后，發現烏鴉優化算法模擬了烏鴉追隨覓食的過程，涌現出了較好的全局搜索能力。但是，原始烏鴉算法[4]的追隨過程易于使算法陷入局部最優。因此，本文提出了基于消除機制的烏鴉優化算法[5]求解TSP 問題（ECSA）。在ECSA中，消除機制增加了種群的多樣性，避免算法陷入局部最優，使得ECSA提高了算法的擴展能力和融合能力。通過對TSPLIB中的標準測試集進行實驗，與其他算法相比，ECSA結果較好，能夠在較短的時間內搜索到更好的解。

1 烏鴉優化算法

CSA 是伊朗學者Askarzadeh 根據烏鴉智能行為于2016年提出的一種新群體智能優化算法[6]。烏鴉的智能行為表現為將多余的食物存放在藏身地方，并在需要食物時將其收回。烏鴉由于貪婪而相互追隨，以獲得更好的食物源。尋找其他烏鴉隱藏食物來源并不容易，因為如果一只烏鴉發現另一只在跟隨它，就會嘗試通過其他位置來欺騙烏鴉。與粒子群優化算法（PSO），蟻群算法（ACO）等群智能優化算法相比，該算法具有易于理解和實現簡單優點。步驟如下：

步驟1：初始化種群大小，算法迭代的最大次數和種群的原始位置；

步驟2：初始化每個烏鴉的記憶；

步驟3：評估每個烏鴉所在位置的食物質量；

步驟4：隨機選擇其中一只烏鴉；

步驟5：按照認知概率，追隨這只烏鴉；

步驟6：迭代優化。

在步驟5中，其他烏鴉個體將直接飛向最佳個體。意味著在這之后，該群體中所有個體將達到最佳個體。所以步驟5很容易導致算法陷入局部最優，導致低優化精度。

2 基于消除機制的烏鴉優化算法

在文中，對烏鴉覓食行為增加了消除機制。即淘汰種群中一些較差個體，同時在烏鴉覓食過程中產生一些新個體。既提高算法收斂性，又增加種群多樣性，從而提高算法搜索空間，同時減少運行時間和陷入局部最優概率。

基于消除的烏鴉優化算法步驟如下：

步驟1：初始化定義烏鴉種群大小，最大迭代次數和種群的初始位置，飛行長度和認知概率。

步驟2：初始化烏鴉的記憶，即為種群初始位置。

步驟3：評估每個烏鴉所在位置食物質量。

圖1和圖2給出了原始烏鴉算法和改進烏鴉算法在Berlin52等數據集的迭代過程結果。其中，藍線表示ECSA，而紅線代表CSA。可以看出，在改進的烏鴉算法中，40次迭代后Y軸值沒有改變，而原始版本中的值即使經過100次迭代也在變化。最后藍色曲線低于紅色曲線。這表明，改進算法可以在40次迭代之后即可找到最優解，而原始算法則需要100次迭代，因此在求解TSP問題時前者比后者能夠得到更高精度。這是由于ECSA更加重視烏鴉搜索行為的追隨行為，并為CSA增加了消除機制，可以加快收斂速度。

圖3和圖4給出的是改進的烏鴉搜索算法獲得的優化結果和理論最優值之間的比較結果（其中每項數據對比中，左側為紅色柱條，右側為藍色柱條）。其中，紅色表示理論值，而藍色表示ECSA得到的優化結果。可以看出，改進的烏鴉優化算法所得的優化值和理論值幾乎沒有差別，并且在數據集Berlin52，Eil51，St70，KroA100和Lin105上改進算法均達到了理論值。

表2給出了使用基于消除機制的烏鴉優化算法和其他群智能算法的比較結果。在每個數據集中，各算法求得結果中最小值標記為紅色。通過分析，改進算法得到的結果為7542.00，427.53， 677.26， 1237.20，62.05，與數據集Berlin52，Eil51，St70，Rat99，Eil101和Ch150上的其他優化算法相比，優化效果最好。對于數據集Eil76，Kroa100，Krob100和Lin105，盡管獲得最優結果的算法分別是CGAS，DWIO，DWIO 和改進RABNET，ECSA所得的結果與其他三種算法的差異很小。例如，在數據集Krob100 上，最好的結果是22336.20，而ECSA 的結果為22355.00，差別小于0.1％。通過比較看出，ECSA結果更加精確，也提高了優化精度。

5 結論

本文在烏鴉搜索算法中加入了一種消除機制，其覓食行為更加注重烏鴉的追索搜索能力，避免了算法被局部優化的困擾。此方法不僅可以幫助烏鴉不斷追隨其他烏鴉飛行，而且可以提高收斂速度及算法優化精度。最后，測試了TSPLIB中的10個數據集以驗證此文方法，結果表明，本文所闡述的方法比其他方法具有更好的優化精度和穩定性。