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

孟范立

關(guān)鍵詞：旅行商；烏鴉優(yōu)化算法；運算符；消除機制

中圖分類號：TP18 文獻標(biāo)識碼：A

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

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

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

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

1 烏鴉優(yōu)化算法

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

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

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

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

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

步驟5：按照認(rèn)知概率，追隨這只烏鴉；

步驟6：迭代優(yōu)化。

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

2 基于消除機制的烏鴉優(yōu)化算法

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

基于消除的烏鴉優(yōu)化算法步驟如下：

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

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

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

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

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

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

5 結(jié)論

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