朱德鑫，蔡延光

（廣東工業(yè)大學(xué)自動(dòng)化學(xué)院，廣東廣州，510006）

0 引言

旅行商問(wèn)題(Traveling Salesman Problem，TSP)是一個(gè)經(jīng)典的NP-hard組合優(yōu)化問(wèn)題。該問(wèn)題具有重要的工程應(yīng)用價(jià)值，在車(chē)間調(diào)度、物流運(yùn)輸?shù)阮I(lǐng)域都有其應(yīng)用。

蝙蝠算法(BA)是一種受啟發(fā)于蝙蝠覓食行為的算法，最早由Yang Xin-she于2010年提出。自然界中蝙蝠利用自身獨(dú)特的生物結(jié)構(gòu)，通過(guò)超聲波探測(cè)的信息定位周?chē)h(huán)境和獵物，以進(jìn)行規(guī)劃飛行路線和捕食獵物。蝙蝠算法就是模仿此類行為而創(chuàng)造的一種新型群體智能優(yōu)化算法。目前在車(chē)間調(diào)度、工程優(yōu)化等領(lǐng)域中均得到應(yīng)用。

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

1 旅行商問(wèn)題的數(shù)學(xué)模型

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

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

2 變鄰域蝙蝠算法設(shè)計(jì)

2.1 蝙蝠速度和位置更新

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

2.2 蝙蝠響度和發(fā)射頻更新

當(dāng)蝙蝠最優(yōu)解更新時(shí)，調(diào)整蝙蝠個(gè)體響度A和發(fā)射頻r：

2.3 變鄰域策略

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

（1）2-opt策略

（2）exchange策略

（3）insert策略

在變鄰域蝙蝠算法的迭代過(guò)程中，為使局部搜索性能更優(yōu)，搜索空間更為多樣性，將同時(shí)使用以上三種策略，在對(duì)當(dāng)前某個(gè)蝙蝠個(gè)體的解Xi使用某一鄰域搜索后產(chǎn)生新解Xnew，若新解比原解更優(yōu)則替換掉原解且在當(dāng)前鄰域中繼續(xù)搜索，否則保留原解進(jìn)入下一個(gè)鄰域搜索，達(dá)到設(shè)定的迭代次數(shù)后，停止鄰域搜索并保留鄰域搜索最優(yōu)解。

2.4 慣性權(quán)重

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

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

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

2.5 算法步驟

在蝙蝠算法中加入三種變鄰域優(yōu)化策略和慣性權(quán)重后，VNBA算法步驟如下：

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

Step2：通過(guò)計(jì)算個(gè)體適應(yīng)值找出蝙蝠種群中的最優(yōu)蝙蝠蝙蝠，并記錄對(duì)應(yīng)個(gè)體的位置及其適應(yīng)度值。

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

Step4：隨機(jī)生成一個(gè)隨機(jī)數(shù)R1，若R1大于ri，則將全局搜索的最優(yōu)蝙蝠個(gè)體進(jìn)行三種變鄰域搜索，否則保留原來(lái)的最優(yōu)蝙蝠個(gè)體。

Step5：再隨機(jī)生成一個(gè)隨機(jī)數(shù)R2，若該數(shù)R2小于當(dāng)前蝙蝠個(gè)體的響度Ai且新個(gè)體的適應(yīng)度優(yōu)于原個(gè)體的適應(yīng)度時(shí)，則接受Step4中的個(gè)體解。同時(shí)更新個(gè)體i的響度A以及其脈沖發(fā)射率ri，否則不對(duì)其響度以及脈沖發(fā)射率進(jìn)行更新。

Step6：計(jì)算全部個(gè)體對(duì)應(yīng)的適應(yīng)度值并作對(duì)比排序，尋找到當(dāng)代全局最優(yōu)解。

Step7：重復(fù)步驟Step3到Step6，直到迭代次數(shù)超過(guò)最大迭代次數(shù)時(shí)停止迭代，并且輸出全局最優(yōu)解。

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

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

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

表1 各算法性能對(duì)比分析

圖1 VNBA優(yōu)化后的Oliver30路徑圖

圖2 VNBA優(yōu)化后的Att48路徑圖