基于獵人獵物優(yōu)化算法求解TSP問(wèn)題

王 芬，楊 媛

(寧夏師范學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,寧夏 固原 756099)

旅行商問(wèn)題(Traveling Salesman Problem，TSP)是工程、離散數(shù)學(xué)、計(jì)算和運(yùn)籌學(xué)等領(lǐng)域中重要的研究課題之一[1].近年來(lái)有很多群體智能算法被用于解決TSP問(wèn)題.TSP問(wèn)題不難理解，但很難解決，這一問(wèn)題自提出以來(lái)，就引起了許多研究人員的興趣，但是一直沒(méi)有找到有效地解決辦法.解決這一問(wèn)題有兩類方法，一類是傳統(tǒng)的方法，一類是智能優(yōu)化算法.傳統(tǒng)的TSP求解算法結(jié)果并不理想，所以學(xué)者們?cè)噲D用群體智能算法來(lái)解決這一NP難問(wèn)題.粒子群算法(PSO)，麻雀優(yōu)化算法(SSA)等都是群體智能算法，是模擬鳥(niǎo)群或麻雀等覓食行為產(chǎn)生的算法.雖然這些算法不能在有限的時(shí)間內(nèi)得到最優(yōu)解，但可以在一定時(shí)間范圍內(nèi)得到比較滿意的解.目前，大多使用啟發(fā)式算法解決這類NP難問(wèn)題，例如遺傳算法[2]、麻雀優(yōu)化算法[3]和粒子群算法[4]等.獵人獵物優(yōu)化算法是2022年提出的一種新型智能優(yōu)化算法，該算法通過(guò)模擬動(dòng)物獵食的過(guò)程對(duì)問(wèn)題進(jìn)行尋優(yōu)，具有收斂速度快，尋優(yōu)能力強(qiáng)的特點(diǎn).故本文用該算法求解TSP問(wèn)題.

1 旅行商問(wèn)題

旅行商問(wèn)題被定義為一個(gè)推銷員在所有城市的旅行，以最低的成本回到最初的城市.TSP問(wèn)題的計(jì)算規(guī)模隨著城市節(jié)點(diǎn)的增多呈指數(shù)增大，能否以合理的成本找到理想解決方案是非常重要的.該問(wèn)題由一組N個(gè)城市節(jié)點(diǎn)組成，任意兩個(gè)城市節(jié)點(diǎn)之間的間距已知.推銷員從一個(gè)節(jié)點(diǎn)開(kāi)始，每個(gè)節(jié)點(diǎn)經(jīng)過(guò)且經(jīng)過(guò)一次(起始節(jié)點(diǎn)除外)使總移動(dòng)距離最小的方式返回到起始節(jié)點(diǎn).

TSP問(wèn)題可以用圖形G=(V,E) 表示，其中 V={1,2,…,N}是城市節(jié)點(diǎn)的集合，E 是邊的集合.每個(gè)邊都有一個(gè)表示距離的值，該距離表示與其關(guān)聯(lián)的各城市之間的距離.推銷員旅行到N個(gè)城市(或節(jié)點(diǎn))時(shí)，他只去每個(gè)城市一次，并以最短的旅行距離結(jié)束.令dji為第j個(gè)城市與第i個(gè)城市之間的距離.TSP問(wèn)題可以化為如下模型

xjk,?j,k∈V&j≠k，

(1)

(2)

(3)

(4)

如果推銷員從城市j到城市i，則xji=1，否則xji=0.

上述模型可以簡(jiǎn)化為確定一個(gè)城市序列(x1,x2,…,xN,x1)，該序列使(5)式最小的.

(5)

2 獵人獵物優(yōu)化算法原理

獵人獵物優(yōu)化算法[5](Hunter-prey optimizer，HPO)是2022年提出的一種新的基于種群的優(yōu)化算法.該算法模擬豹子、獅子等食肉動(dòng)物捕食鹿和羚羊等獵物的行為而產(chǎn)生的.

2.1 初始化

獵食者種群由(6)式隨機(jī)初始化位置.

xi=rand(1,d)*(u-l)+l,

(6)

其中，xi是獵食的位置，l是最小值(下界)，u是最大值(上界)，d是問(wèn)題變量的數(shù)量(維度).

2.2 獵食者搜索

公式(7)是獵食者的搜索機(jī)制.

xi,j(t+1)=xi,j(t)+0.5[(2CZPpos(j)-xi,j(t))+(2(1-C)Zγ(j)-xi,j(t))],

(7)

其中，xi,j(t)是獵食者當(dāng)前位置，xi,j(t+1)是獵食者下一次的位置，Ppos是獵物的位置，γ是所有位置的平均值，Z是自適應(yīng)參數(shù)，由公式(9)計(jì)算得

P=R1

(8)

Z=R2?IDX+R3?(～I(xiàn)DX)，

(9)

其中，R1和R3是[0,1]內(nèi)的隨機(jī)向量，P是R1

(10)

其中，i是當(dāng)前迭代次數(shù)，M是最大迭代次數(shù).

公式(7)中的γ為

(11)

計(jì)算歐幾里得距離為

(12)

根據(jù)狩獵場(chǎng)景，當(dāng)獵食者捕獲獵物時(shí)，獵物會(huì)死亡，下一次，獵食者會(huì)移動(dòng)到新的獵物位置.為了解決這個(gè)問(wèn)題，考慮一種遞減機(jī)制，如(13)式所示.

k=round(C×N)，

(13)

其中，N是搜索種群的數(shù)量.在算法開(kāi)始時(shí)，k的值等于N.最后一個(gè)距離搜索個(gè)體的平均位置γ最遠(yuǎn)的搜索個(gè)體被選擇為獵物，并被獵食者捕獲.假設(shè)最佳安全位置是全局最佳位置，因?yàn)檫@將使獵物有更好的生存機(jī)會(huì)，獵食者可能會(huì)選擇另一個(gè)獵物.(14)式用于更新獵物位置.

xi,j(t+1)=Tpos(j)+CZcos(2πR4)×[Tpos(j)-xi,j(t)]，

(14)

其中，xi,j(t)是獵物的當(dāng)前位置，xi,j(t+1)是獵物的下一次迭代位置，Tpos(j)是全局最優(yōu)位置，Z是由式(9)計(jì)算的自適應(yīng)參數(shù)，R4是[ 0， 1 ]內(nèi)的隨機(jī)數(shù)，C是探索和開(kāi)發(fā)之間的平衡參數(shù)，其值在算法的迭代過(guò)程中減小，并由式(10)計(jì)算，cos函數(shù)及其輸入?yún)?shù)允許下一個(gè)獵物位置在不同半徑和角度的全局最優(yōu)位置.為了選擇獵食者和獵物，結(jié)合式(7)和(14)提出了下式.

xi(t+1)=xi(t)+0.5[(2CZPpos(j)-xi(t))+(2(1-C)Zγ(j)-xi(t))],

(15)

xi(t+1)=Tpos+CZcos(2πR4)×(Tpos-xi(t))，

(16)

其中，R4是[ 0， 1 ] 范圍內(nèi)的隨機(jī)數(shù)，β是一個(gè)調(diào)節(jié)參數(shù)，本文設(shè)置為0.1.如果R5<β，搜索種群將被視為獵人，搜索下一個(gè)位置將用式(15)更新；否則，搜索種群將被視為獵物，搜索下一個(gè)位置將用式(16)更新.

算法具體步驟如下.

步驟1 初始化種群；

步驟2 設(shè)置算法相關(guān)參數(shù)；

步驟3 計(jì)算適應(yīng)度值，并記錄最優(yōu)位置；

步驟4 根據(jù)公式(9)和公式(10)更新C和N；

步驟5 根據(jù)R4的值更新位置；

步驟6 計(jì)算適應(yīng)度值；

步驟7 判斷是否滿足停止條件，如果滿足則輸出最優(yōu)解，否則轉(zhuǎn)向步驟4.

算法流程圖如圖1所示.

圖1 算法流程圖

3 實(shí)驗(yàn)仿真及分析

實(shí)驗(yàn)用MATLAB進(jìn)行編程.為驗(yàn)證提出算法的有效性，用本文提出的獵食者算法與麻雀搜索算法、粒子群算法進(jìn)行仿真對(duì)比實(shí)驗(yàn).實(shí)驗(yàn)分兩組，第一組實(shí)驗(yàn)中城市的坐標(biāo)由隨機(jī)產(chǎn)生，城市個(gè)數(shù)為20.第二組實(shí)驗(yàn)采用TSPLIB中的 att48、eil51和rat99的 TSP 數(shù)據(jù)對(duì)獵食者算法與麻雀搜索算法、粒子群算法結(jié)果進(jìn)行對(duì)比.設(shè)置的初始參數(shù)為種群個(gè)數(shù)為 100，最大迭代次為2000.

3.1 初始數(shù)據(jù)隨機(jī)產(chǎn)生

隨機(jī)產(chǎn)生的20個(gè)城市的坐標(biāo)如圖2所示.三種算法的收斂曲線圖如圖3所示.

圖2 隨機(jī)產(chǎn)生的城市坐標(biāo) 圖3 各算法適應(yīng)度曲線

由圖2可以看出，在求解TSP問(wèn)題時(shí)， HPO算法與SSA算法和PSO算法相比時(shí)間更短，收斂速度更快.

三種算法的路徑規(guī)劃圖如圖4所示.

圖4 三種算法路徑規(guī)劃圖

從圖4可以直觀地看出，HPO算法的路徑規(guī)劃比SSA算法和PSO算法更合理.

3.2 TSPLIB數(shù)據(jù)

采用TSPLIB中的att48、eil51和rat99的TSP數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，各算法30次獨(dú)立實(shí)驗(yàn)的最優(yōu)值、平均值、迭代次數(shù)如表1所示.

表1 三種算法的比較

從表1的實(shí)驗(yàn)結(jié)果可以看出，HPO算法在求解TSP 問(wèn)題時(shí),與SSA算法和PSO算法相比，得到的最優(yōu)解相對(duì)更好.體現(xiàn)出HPO算法具有收斂速度快，尋優(yōu)能力強(qiáng)的特點(diǎn)，且在求解TSP問(wèn)題時(shí)具有一定的優(yōu)越性.

4 結(jié)論

旅行商問(wèn)題是經(jīng)典的組合優(yōu)化 NP 問(wèn)題,有重要的現(xiàn)實(shí)研究意義.文章對(duì)獵食者算法的原理，更新策略，算法流程進(jìn)行分析，并將他應(yīng)用到解決TSP問(wèn)題中.通過(guò)對(duì)比實(shí)驗(yàn)驗(yàn)證該算法的全局搜索能力與收斂性，結(jié)果表明該算法的性能優(yōu)于其他算法，驗(yàn)證了獵食者算法有效性.