唐文秀

（華北電力大學(xué),北京 102206）

1 概述

在數(shù)學(xué)領(lǐng)域中,TSP 問題(Traveling Salesman Problem,即旅行商問題),被廣泛視作一個典型的組合優(yōu)化問題[1]。該問題一般講述的是為一個旅行商尋找最短路徑,該商人計劃在n 個不同的城市為產(chǎn)品作宣傳,并且每個城市只能經(jīng)過一次,從初始城市出發(fā),遍歷所有目的城市且不重復(fù)后,又回到初始城市。顯然,該問題屬于組合優(yōu)化問題,在生活中非常普遍,很多實際工程應(yīng)用問題的實質(zhì)就是旅行商問題,例如某旗艦店的商品物流路線、物資分配、車輛調(diào)度、電路布線、產(chǎn)品生產(chǎn)安排問題等等[2-4]。因此,研究TSP 問題不僅具有重大的實際意義,也具有相當(dāng)高的工程價值。

當(dāng)城市數(shù)量較少時,理論上可以通過窮舉法來列舉出最優(yōu)方案,然而當(dāng)城市數(shù)量較多時,所有路線之和將呈指數(shù)增加,因此求解過程非常復(fù)雜而且很難找到最優(yōu)解。目前,求解TSP 問題的算法大致可劃分為兩類,分別是確定性算法和智能優(yōu)化算法[5]。確定性算法通常是指能利用數(shù)學(xué)公式解出具體的某個數(shù)值,且該結(jié)果即為最優(yōu)解,例如線性規(guī)劃、動態(tài)規(guī)劃、完全枚舉等方法,然而該類算法只適用于小規(guī)模算例求解,因此,考慮到現(xiàn)實應(yīng)用情況,在規(guī)模較大時,人們常常選擇目前廣受關(guān)注的智能優(yōu)化算法,例如遺傳算法、粒子群算法、模擬退火算法、禁忌搜索算法、免疫算法以及人工神經(jīng)網(wǎng)絡(luò)[6-9]等等。本文主要通過遺傳算法和禁忌搜索算法兩種算法進行混合求解,結(jié)合兩種算法的優(yōu)勢,對TSP 問題進行優(yōu)化求解,提高解的質(zhì)量。

2 改進禁忌搜索算法

1986 年,Fred Glover 教授提出了禁忌搜索算法（Tabu Search,簡稱TS 算法）[10],指出該算法的局部搜索能力非常強,并且也能避免算法陷入局部最優(yōu),從而找到全局最優(yōu)解,是一種全局迭代尋優(yōu)算法。多年來,該算法也以其靈活的記憶特性和特赦準(zhǔn)則,受到了眾多學(xué)者的青睞。

所謂禁忌,是指禁止重復(fù)操作,類似于模擬人的思維模式,如果該區(qū)域已經(jīng)搜索過,則下次搜索時可以通過禁忌表來進行記錄,避免重復(fù)低效搜索,但也并非完全隔絕,對于更優(yōu)的解,也可以通過特赦準(zhǔn)則對其進行釋放,改善解的質(zhì)量,避免遺漏。

在TS 算法中,關(guān)鍵的參數(shù)主要有禁忌表、禁忌長度、特赦準(zhǔn)則、候選集、適配值函數(shù)、終止準(zhǔn)則等。禁忌表是算法的核心所在,用來記錄已經(jīng)搜索過的地方,避免在搜索中陷入循環(huán)和局部最優(yōu)。禁忌長度是指放置在禁忌表中的對象的禁忌周期,每進行一次迭代,周期就減少一次,直到周期為0 時即可解除禁忌。特赦準(zhǔn)則是指在迭代過程中,出現(xiàn)了比歷史最優(yōu)還要更優(yōu)的解,盡管此時該解對應(yīng)的對象處于禁忌表中,且禁忌長度不為0,也可以將其特赦出來,解禁該禁忌對象。候選集主要從領(lǐng)域解中產(chǎn)生,可以隨機選擇幾個領(lǐng)域解作為候選解,或者選擇表現(xiàn)較好的作為候選解。適配值函數(shù)是指對當(dāng)前搜索過程的評價,在TSP 問題中為總的行程距離大小。終止準(zhǔn)則指算法的結(jié)束條件,通常設(shè)置為算法執(zhí)行到某一個迭代次數(shù),或者目標(biāo)函數(shù)值小于某個誤差。

TS 算法的主要搜索步驟如下所示：

（1）初始化禁忌表、禁忌長度,隨機產(chǎn)生初始解,定義領(lǐng)域映射模式；

（2）判斷初始解是否滿足終止條件,若滿足,則輸出最優(yōu)解,結(jié)束搜索；若不滿足,則繼續(xù)下一步；

（3）根據(jù)當(dāng)前解的領(lǐng)域映射模式生成若干個鄰域解,并從中選出若干候選解,計算適配值,保留較好的候選解進行下一步判斷；

（4）判斷候選解是否滿足特赦準(zhǔn)則,若滿足,則將其特赦出來,并作為當(dāng)前最優(yōu)解,同時將對應(yīng)的對象放入禁忌表,并修改表中各個對象的周期長度；若不滿足,則選出在候選解中沒有被禁忌的最優(yōu)解作為當(dāng)前最優(yōu)解,對禁忌表進行重復(fù)前一步操作；

（5）當(dāng)滿足終止準(zhǔn)則時,例如迭代次數(shù)已達(dá)到最大,此時結(jié)束搜索,輸出最短路線。流程如圖1 所示。

圖1 禁忌搜索算法流程圖

雖然TS 算法具備著強大的局部搜索能力和記憶功能,但是也存在一些不足,例如,該算法對初始解具有很大的依賴性,即當(dāng)初始解較好時,能夠迅速找到最優(yōu)解,當(dāng)初始解不好時,則直接制約了禁忌搜索的速度,因此,為了克服該問題,本文提出結(jié)合遺傳算法進行改進,首先利用遺傳算法產(chǎn)生較好的初始解之后,再把該解作為禁忌搜索算法的初始解來進行迭代尋優(yōu),而非隨機產(chǎn)生初始解。

遺傳算法的主要步驟為：第一步進行初始化操作,計算每條路線的適應(yīng)度值及路徑長度；第二步,以概率的方式來選擇新的路線方案；第三步,對選擇的路線進行交叉操作,隨機交叉某兩座城市的坐標(biāo),確保每個城市有且僅經(jīng)過一次；第四步,進行變異操作,即隨機交換某一條路線的一對城市坐標(biāo),得到新的路線,然后再進行下一次迭代尋優(yōu)；最后判斷是否滿足終止條件,若滿足則結(jié)束搜索,輸出最優(yōu)路徑及最短距離,若不滿足,則繼續(xù)進行迭代尋優(yōu)。遺傳算法流程圖如圖2 所示。

圖2 遺傳算法流程圖

3 算例仿真

3.1 改進前結(jié)果

假設(shè)城市規(guī)模N=31,每座城市坐標(biāo)如表1 所示。設(shè)置禁忌長度L=22,候選解的個數(shù)M=200,求出任意兩個城市的間隔矩陣,定義領(lǐng)域映射模式為2-opt,開始禁忌搜索操作,直到滿足終止條件。

表1 31 座城市的坐標(biāo)

圖3 31 座城市分布

在該問題中,分別設(shè)置迭代次數(shù)為100、300、500、800 和1000,在不同的迭代次數(shù)下,重復(fù)運行5 次程序,得到的結(jié)果如表2 所示。

表2 不同迭代次數(shù)的實驗結(jié)果

從仿真結(jié)果可以看到,當(dāng)?shù)螖?shù)逐漸增大時,計算的結(jié)果逐漸減小,并逐漸趨于優(yōu)化最短距離,在該案例中,當(dāng)未加入遺傳算法進行改進時,在迭代次數(shù)為1000 時,優(yōu)化最短距離為16126,最優(yōu)路徑和適應(yīng)度進化曲線如圖4、5 所示。

圖4 改進前優(yōu)化最短距離

圖5 改進前適應(yīng)度進化曲線

3.2 改進后結(jié)果

先通過遺傳算法進行求解,設(shè)置群體數(shù)量NP=200,染色體基因維數(shù)N=31,最大進化迭代次數(shù)G=1000,產(chǎn)生初始種群,計算每個個體的適應(yīng)度值和最短距離,再通過選擇、交叉、變異操作進行下一次遺傳,直到迭代次數(shù)達(dá)到最大值,將此時得到的最短路線方案作為初值傳給禁忌搜索算法。在實驗中,分別設(shè)置迭代次數(shù)為100、500 和1000,在不同的迭代次數(shù)下,重復(fù)運行5 次程序,得到的結(jié)果如表3 所示。

表3 改進后結(jié)果

在加入遺傳算法后,可以看到,結(jié)果得到了極大的改善。當(dāng)?shù)螖?shù)為1000 時,此時遺傳算法已經(jīng)越來越接近最優(yōu)值,再結(jié)合禁忌搜索算法進行尋優(yōu)時,可以看到改進后的結(jié)果明顯優(yōu)于改進前的結(jié)果,此時得到的最短距離為15382,相比于改進前,縮短了744,路線方案如圖6 所示,適應(yīng)度進化曲線如圖7 所示,藍(lán)色的線條表示僅采用禁忌搜索算法求解的結(jié)果,紅色的線條表示結(jié)合遺傳算法進行改進后的結(jié)果,可以看出,改進后的適應(yīng)度值明顯低于改進前的值,說明了算法的有效性。

圖6 改進后優(yōu)化最短距離

圖7 適應(yīng)度進化曲線對比

4 結(jié)論

本文簡要闡述了禁忌搜索算法的基本思想、求解步驟以及實現(xiàn)過程等,基于MATLAB 編程了改進前的禁忌搜索算法和改進后的禁忌搜索算法,并對比了兩種方式對TSP 問題的求解的結(jié)果,實驗結(jié)果表明,改進前的禁忌搜索算法能夠找到相對最優(yōu)解,但需要較大的迭代次數(shù),且初始解較差時,求解速度緩慢,結(jié)果不夠穩(wěn)定。通過遺傳算法進行改進后,結(jié)果有了較大的提高,從實驗數(shù)據(jù)可以看出,在改進前,當(dāng)?shù)螖?shù)為1000 時,優(yōu)化最短距離為16126,改進以后,優(yōu)化最短距離為15382,縮短了總的行程距離,得到了更優(yōu)的路線方案,實驗結(jié)果得到了明顯的改善,算法有效并且可行。