求解旅行商問題的新型果蠅優(yōu)化算法*

姜天水，王 枚

(煙臺職業(yè)學(xué)院，山東 煙臺 264670)

1 引言

旅行商問題(Traveling Salesman Problem，簡稱TSP)是一個經(jīng)典NP-hard組合優(yōu)化問題?，F(xiàn)實中很多復(fù)雜問題都可以轉(zhuǎn)換成TSP問題的求解[1]，所以，高效的TSP求解算法一直是組合優(yōu)化領(lǐng)域的研究熱點。傳統(tǒng)的旅行商求解算法主要是包括分支定界法、線性規(guī)劃法在內(nèi)的精確算法，這類算法無法求解高維的TSP問題。而隨著人工智能的發(fā)展，許多智能優(yōu)化算法被應(yīng)用于求解TSP問題，諸如遺傳算法、蟻群算法、猴群算法、布谷鳥算法、帝國競爭算法、果蠅優(yōu)化算法(Fruit Fly Optimization Algorithm，簡稱FOA)等，并取得了不錯的效果。

FOA是一種從果蠅覓食行為中得到啟發(fā)而提出的一種智能優(yōu)化算法[2]。該算法在提出初期，主要用于求解連續(xù)的優(yōu)化問題，目前也已逐步應(yīng)用到求解組合優(yōu)化問題中。Tao等利用FOA求解多維背包問題并取得了高質(zhì)量的結(jié)果[3]；Du等將FOA用于結(jié)構(gòu)優(yōu)化設(shè)計，通過實驗驗證了FOA的尋優(yōu)能力[4]；Wang等將FOA用于生產(chǎn)作業(yè)調(diào)度優(yōu)化，有效的提高了參數(shù)[5]；Zhang等將FOA用于求解控制器設(shè)計問題，有效的協(xié)調(diào)和優(yōu)化了系統(tǒng)的參數(shù)[6]；Polo等將FOA應(yīng)用于天線結(jié)構(gòu)優(yōu)化設(shè)計，并得到了較單純形法和遺傳算法更好的結(jié)果[7]；Kanarachos等將FOA用于車輛懸架參數(shù)設(shè)計之中，并得到了較傳統(tǒng)更佳的設(shè)計方案[8]。相比于粒子群算法、蟻群算法以及魚群算法等群智能算法，F(xiàn)OA具有簡單易理解、編程易實現(xiàn)、運行時間少等優(yōu)點，但是由于FOA提出時間較晚，所以國內(nèi)外對該算法的研究還處于初級階段，算法理論還不成熟，所以有必要進(jìn)一步研究FOA在諸如TSP等問題中的應(yīng)用。

針對旅行商問題，提出了一種新型FOA，通過引入果蠅強(qiáng)化策略，加強(qiáng)對果蠅種群中的最優(yōu)個體的開發(fā)，同時，提出了果蠅轉(zhuǎn)化過程，根據(jù)解的情況自適應(yīng)的調(diào)節(jié)果蠅種群的搜索方向，以改善傳統(tǒng)FOA存在的收斂速度慢易于陷入局部最優(yōu)解的問題，提高了FOA的求解精度和尋優(yōu)速度。利用國際通用TSPLIB測試庫實例對新型FOA性能進(jìn)行測試，通過對比新型FOA的求解結(jié)果，驗證了該算法的高效性，對比新型FOA和傳統(tǒng)FOA的收斂速度和求解精度，驗證了改進(jìn)的有效性。

2 問題描述

TSP問題是指給定n個城市坐標(biāo)點，求解從某一個城市出發(fā)，訪問所有城市一次并且回到起始城市的最短路徑，其在圖論意義下又被稱為最小Hamilton圖問題。若設(shè)城市點集合為V={V1,V2,…,Vn},dij表示城市i和城市j之間的距離，為0-1變量，若由城市i到城市j的線路存在于回路路徑中則xij為1，否則為0。因而，TSP的數(shù)學(xué)模型可表示如下：

3 求解TSP問題的新型果蠅優(yōu)化

3.1 傳統(tǒng)FOA算法

FOA是2011年臺灣學(xué)者潘文超博士從果蠅覓食行為中得到啟發(fā)而提出的一種群智能優(yōu)化算法，其主要算法過程描述如下：

步驟1：設(shè)定果蠅種群規(guī)模Sizepop和最大迭代次數(shù)Maxgen，并隨機(jī)初始化果蠅群體位置；

步驟2：設(shè)定果蠅個體嗅覺搜索食物的隨機(jī)方向與距離；

步驟3：計算味道濃度判定值Si，并帶入味道濃度判定函數(shù)，求出果蠅個體i的味道濃度Smelli；

步驟4：找出果蠅群體中味道濃度最佳的果蠅(最優(yōu)個體)；

步驟5：記錄并保留最佳味道值以及最優(yōu)個體的位置，果蠅群體利用視覺搜索向該位置飛去；

步驟6：判斷是否滿足終止條件，若滿足，則結(jié)束搜索，否則跳回步驟3。

3.2 新型FOA算法

分析上述傳統(tǒng)FOA的算法流程，可以發(fā)現(xiàn)嗅覺搜索過程和視覺搜索過程都沒有對果蠅群體中的最優(yōu)個體進(jìn)行開發(fā)，而對種群中優(yōu)秀個體的開發(fā)往往會得出更優(yōu)解，所以引入了果蠅強(qiáng)化策略，通過對果蠅種群中的優(yōu)秀個體采取專門的開發(fā)操作，以改善果蠅優(yōu)化算法的求解精度，同時，為了避免算法陷入局部最優(yōu)解，引入了果蠅轉(zhuǎn)化策略，根據(jù)具體的求解情況改變果蠅種群的搜索方向。下面具體描述新型FOA的方法步驟。

3.2.1 編碼

由問題分析可知，設(shè)城市集合為V={V1,V2,…,Vn}，則TSP問題中的一條可行路徑可表示為有序序列W={W1,W2,…,Wn},Wi∈V(i=1,2,…,n)，而且?Wi≠Wj,i≠j。所以為了方便FOA的求解，設(shè)編碼所表示的是8個城市的一個解，具體的編碼方式即城市訪問順序描述為：7-3-2-5-8-6-1-4。

3.2.2 嗅覺搜索和視覺搜索

FOA通過嗅覺搜索過程找出果蠅群體中的最優(yōu)個體，然后整個果蠅群體通過視覺搜索向最優(yōu)個體靠攏，所以可知果蠅群體的視覺搜索是算法收斂的關(guān)鍵。取城市數(shù)目為m，xbest表示果蠅種群中的最優(yōu)個體，x表示視覺搜索前的果蠅，x*表示視覺搜索后生成的新果蠅。新型FOA的視覺搜索過程主要分為以下5步：

步驟1：隨機(jī)生成一串長度為m的0到1之間的隨機(jī)數(shù)串δ={δ1,δ2,…,δm}；

步驟2：若位置i處的隨機(jī)數(shù)δi≤ρ，則視覺搜索后的新果蠅位置i處的編碼x*取果蠅種群中的最優(yōu)個體對應(yīng)位置的編碼xbest；

步驟3：對于位置i處的隨機(jī)數(shù)δi≤ρ時，若xi在搜索后的果蠅中沒有出現(xiàn)，則x*取xi；

步驟4：其余視覺搜索后的果蠅中未存在的城市編碼，按照搜索前果蠅中的相對位置依次插入x*中的空缺位置；

步驟5：生成視覺搜索后的新果蠅x*。

其中ρ是一個反應(yīng)視覺搜索步長的閾值，通過大量實驗，取0.5對求解最為有效。具體的視覺搜索過程如圖1所示，其中ρ取0.5。

圖1 視覺搜索過程示意圖

3.2.3 果蠅強(qiáng)化

果蠅強(qiáng)化策略是通過對果蠅群體進(jìn)行專門的開發(fā)，以提高求解質(zhì)量和收斂速度。具體的果蠅強(qiáng)化策略分為以下3步：

步驟1：復(fù)制最優(yōu)果蠅的解，隨機(jī)選擇最優(yōu)果蠅中的兩個城市，將兩者之間的城市反序排列，生成新解，計算該新解的濃度，若優(yōu)于該最優(yōu)果蠅，則替換原最優(yōu)個體，否則不進(jìn)行替換；

步驟2：復(fù)制最優(yōu)果蠅的解，隨機(jī)選擇最優(yōu)果蠅中兩個片段S1和S2，交換兩個片段，生成新解，計算該新解的濃度，若優(yōu)于該最優(yōu)果蠅，則替換原最優(yōu)個體，否則不進(jìn)行替換；

步驟3：復(fù)制最優(yōu)果蠅的解，隨機(jī)選擇最優(yōu)果蠅中的兩個城市，交換兩個城市的位置，生成新解，計算該新解的濃度，若優(yōu)于該最優(yōu)果蠅，則替換原最優(yōu)個體，否則不進(jìn)行替換。

3.2.4 果蠅轉(zhuǎn)化

果蠅轉(zhuǎn)化是為了改善算法易于陷入局部最優(yōu)解而引入的新過程。定義δ為果蠅開發(fā)因子，具體的果蠅轉(zhuǎn)化過程分為以下3步：

步驟1：取果蠅開發(fā)因子δ，判斷種群中最優(yōu)個體是否在δ代內(nèi)沒有發(fā)生變化，若不是則跳到步驟3；

步驟2：若種群中最優(yōu)個體在δ代內(nèi)沒有發(fā)生變化，則保留該最優(yōu)解，同時在果蠅群體中尋找次優(yōu)個體代替最優(yōu)個體；

步驟3：結(jié)束果蠅轉(zhuǎn)化。

通過果蠅轉(zhuǎn)化過程可以看出，該過程的引入可以避免果蠅群體對一個局部最優(yōu)解進(jìn)行過度的開發(fā)，進(jìn)而可以有效的改善果蠅算法易于陷入局部最優(yōu)解的問題，提高算法全局搜索能力。

3.2.5 算法流程

改進(jìn)后果蠅優(yōu)化算法的框圖流程如圖2所示。

圖2 改進(jìn)后果蠅優(yōu)化算法流程圖

針對上述描述，下面以偽代碼的形式對改進(jìn)后新型果蠅算法FOA的算法流程進(jìn)行描述。

7if ?smell(x**)≤best_smell8best_smell ← smell(x**)9xbest ← x**10x ← x**11else12H ← x**13end if14xbest ← transformation(xbest,δ)15end for

4 實驗結(jié)果與分析

利用國際通用TSPLIB測試實例庫對新型FOA性能進(jìn)行測試，利用Matlab2015b編程實現(xiàn)并運行于具有4.0G RAM 2.20 GHz的計算機(jī)上。

4.1 測試實例和比較算法

為了驗證引入果蠅強(qiáng)化策略和果蠅轉(zhuǎn)化策略對TSP算法整體性能的改進(jìn)優(yōu)勢，采用了2種試驗測試方法進(jìn)行比較。

①新型FOR算法與傳統(tǒng)FOR算法進(jìn)行比較。方法是選擇了10組國際通用TSPLIB測試實例，分別對傳統(tǒng)FOR和新型FOR進(jìn)行測試，2種算法的初始果蠅數(shù)均設(shè)置為100只，迭代次數(shù)均為100 000次。新型FOR和傳統(tǒng)FOR算法的測試結(jié)果見表1。

表1 傳統(tǒng)FOA與新型FOA對比結(jié)果

②新型FOR算法與較先進(jìn)的TSP算法比較。方法是選擇近期其他作者提出的較先進(jìn)的不同的TSP算法[9-12]，隨機(jī)采用6組實例進(jìn)行測試比較，測試結(jié)果見表2。如圖3所示是新型FOR算法求解的其中幾組實例所得路徑情況，如圖4所示是依據(jù)測試實例獲得的新型FOR與傳統(tǒng)FOR算法收斂曲線。

表2 新型FOA與其他4種算法對比

圖3 新型FOA求解所得路徑情況

圖4 新型FOA與傳統(tǒng)FOA收斂曲線

4.2 實驗結(jié)果與結(jié)果分析

測試實驗中已知最優(yōu)解來自TSPLIB標(biāo)準(zhǔn)庫，定義偏差率為所求最優(yōu)解與已知最優(yōu)解的差與已知最優(yōu)解的比值。由于編程測試時全為浮點型運算，而TSPLIB提供的已知最優(yōu)解不全為浮點型，偏差率在之內(nèi)的結(jié)果，均可認(rèn)為接近已知最優(yōu)解。進(jìn)行測試的實例均運行20遍，統(tǒng)計最優(yōu)解與平均解，其中若所求最優(yōu)解優(yōu)于已知最優(yōu)解時，偏差率用“—”表示。

分析表1新型FOA與傳統(tǒng)FOA算法測試結(jié)果，在選擇的10個實例中，新型FOA有3個實例中的最優(yōu)解優(yōu)于傳統(tǒng)FOA的求解結(jié)果，除dantzig42新型FOA所得平均解與傳統(tǒng)FOA一致以外，其余9組實例新型FOA所求的平均解均優(yōu)于傳統(tǒng)FOA，進(jìn)而可以看出引入果蠅強(qiáng)化和果蠅轉(zhuǎn)化策略提高了算法的求解精度與求解效率。繼續(xù)對比新型FOA所求的最優(yōu)解與已知最優(yōu)解，可以看到，新型FOA有1組最優(yōu)解優(yōu)于目前已知最優(yōu)解，1組最優(yōu)解與已知最優(yōu)解一致，還有6組最優(yōu)解的偏差率小于1%，即接近最優(yōu)解，進(jìn)而驗證新算法在求解TSP上的優(yōu)異性能。

分析表2新型FOR與其他4種算法測試結(jié)果對比，選擇的是近期其他作者提出的4種求解TSP性能較先進(jìn)算法,新型FOA與其他4種算法的對比結(jié)果可以看到，新型FOA在列出的6組對比實例中，有4組實例所求的最優(yōu)解優(yōu)于其余4種算法，其余2組dantzig42、eil51的求解結(jié)果與最優(yōu)結(jié)果也相差不大，進(jìn)而驗證了新型FOA求解的高效性。

圖4是新型FOA與傳統(tǒng)FOA在Ch130、Pr107兩組實例上的收斂曲線圖，其中Ch130選擇前2 000代的情況，Pr107選擇了前5 000代的情況。觀察分析新型FOA與傳統(tǒng)FOA的收斂曲線可以看出，新型FOA的收斂速度與求解精度均優(yōu)于傳統(tǒng)的FOA，進(jìn)一步證明了新算法的有效性。

5 結(jié)論

果蠅強(qiáng)化和果蠅轉(zhuǎn)化策略的新型果蠅優(yōu)化算法，通過對果蠅種群中的最優(yōu)個體的開發(fā)，既顯著提高算法的求解精度，同時根據(jù)求解的具體情況能夠自適應(yīng)的調(diào)整果蠅種群的搜索方向，進(jìn)而解決了傳統(tǒng)算法易于陷入局部最優(yōu)解的難題。算法通過實驗進(jìn)行的性能測試表明，該算法具有求解精度高、求解收斂速度快的特點。實驗數(shù)據(jù)表明，新型果蠅優(yōu)化算法具有優(yōu)異的求解能力，對求解旅行商問題具有重要的實用價值。