基于強(qiáng)化學(xué)習(xí)的旅行商問(wèn)題解構(gòu)造方法

王若愚,陳勇全

(1.深圳供電局有限公司 輸電規(guī)劃科,廣東 深圳 518001; 2.香港中文大學(xué)(深圳) 機(jī)器人與智能制造研究院,廣東 深圳 518172; 3.深圳市人工智能與機(jī)器人研究院 無(wú)人系統(tǒng)研究中心,廣東 深圳 518129)

0 概述

旅行商問(wèn)題(Traveling Salesman Problem,TSP)是一個(gè)經(jīng)典的NP-hard組合優(yōu)化問(wèn)題[1],其基本形式定義為:給定n個(gè)城市以及任意2個(gè)城市i和j之間的距離dij,要求從某個(gè)城市出發(fā),不重復(fù)訪問(wèn)每個(gè)城市,最終回到出發(fā)城市形成一個(gè)環(huán)路,并使得路徑的總長(zhǎng)度盡可能短。若對(duì)于任意2個(gè)城市i和j都有dij=dji,則稱(chēng)為對(duì)稱(chēng)TSP,否則稱(chēng)其為非對(duì)稱(chēng)TSP。

TSP在機(jī)器人路徑規(guī)劃、交通物流、生物信息和芯片設(shè)計(jì)等領(lǐng)域有廣泛的應(yīng)用背景,如電力系統(tǒng)巡檢機(jī)器人的路徑規(guī)劃問(wèn)題即可建模成TSP,滴滴、順豐、美團(tuán)等公司經(jīng)常面臨的車(chē)輛調(diào)度問(wèn)題[2]也可看作是在TSP的基礎(chǔ)上，疊加多車(chē)輛、取送貨等多種業(yè)務(wù)要求以及容量約束、時(shí)間約束、續(xù)航里程約束等約束條件。

由于TSP在理論和應(yīng)用層面的重要性,已有研究人員對(duì)其進(jìn)行持續(xù)而深入的研究,并設(shè)計(jì)出很多高性能的求解算法,主要可分為精確型算法、近似算法與啟發(fā)式算法三大類(lèi)。其中,精確型算法主要包括分支定界[3]、分支切割[4-5]等方法。在計(jì)算時(shí)間和存儲(chǔ)容量充足的前提下,精確型算法可以確保找到問(wèn)題的最優(yōu)解,但由于TSP的NP-hard屬性,問(wèn)題的解空間規(guī)模呈指數(shù)級(jí)的爆炸式增長(zhǎng)趨勢(shì),該算法所需時(shí)間往往呈現(xiàn)出指數(shù)級(jí)增長(zhǎng),這限制了其在大規(guī)模場(chǎng)景中的應(yīng)用。然而,近似算法雖然不能保證找到問(wèn)題的最優(yōu)解,但是可以在多項(xiàng)式計(jì)算復(fù)雜度內(nèi)嚴(yán)格保證所找到解的路徑長(zhǎng)度與最優(yōu)解的路徑長(zhǎng)度之間的比值不超過(guò)一定的上限,該上限被稱(chēng)為近似度,且近似度越接近1,算法的性能越好。目前,較好的TSP近似算法為Christofides算法[6],其近似度為1.5。啟發(fā)式算法與前2種算法不同,該算法不對(duì)解的優(yōu)度進(jìn)行嚴(yán)格保證,但一般可在較短的計(jì)算時(shí)間內(nèi)找到優(yōu)度可以接受的解。針對(duì)大規(guī)模算例,精確算法往往需要耗費(fèi)指數(shù)倍的時(shí)間來(lái)求解,近似算法所得解與最優(yōu)解相差甚遠(yuǎn),啟發(fā)式算法則成為兼顧算法優(yōu)度和速度的切實(shí)選擇。在該背景下,研究人員針對(duì)TSP設(shè)計(jì)出大量的啟發(fā)式算法,如遺傳算法[7]、蟻群算法[8]、粒子群算法[9]、模擬退火算法[10]、神經(jīng)網(wǎng)絡(luò)算法[11]以及混合算法[12-14]等。

盡管上述方法各有優(yōu)點(diǎn),但在TSP問(wèn)題上,目前世界最領(lǐng)先的啟發(fā)式算法是最為樸素的迭代局部搜索(Iterated Local Search,ILS)算法?；赥SPLIB[15]等國(guó)際標(biāo)準(zhǔn)算例集的測(cè)試結(jié)果表明,以LKH系列[16-18]為代表的ILS算法[19-20]在多數(shù)公開(kāi)算例上保持著世界最優(yōu)紀(jì)錄,充分證明了其在求解TSP時(shí)的強(qiáng)大能力。ILS算法的典型搜索過(guò)程是從構(gòu)造的初始解出發(fā),采用某些操作算子對(duì)其進(jìn)行局部變換操作,得到一系列鄰域解,并選擇其中某個(gè)改進(jìn)解用于替換當(dāng)前解[20]。迭代執(zhí)行上述過(guò)程直至整個(gè)鄰域中不存在改進(jìn)解,即得到一個(gè)局部最優(yōu)解,再構(gòu)造新的初始解,并重復(fù)上述流程直至滿足停機(jī)條件。

文獻(xiàn)[21]表明初始解的構(gòu)造方法是影響ILS性能的重要因素。一種良好的ILS初始解構(gòu)造方法需要兼顧2個(gè)方面,一方面是優(yōu)度較高,從而加快搜索速度,提高找到高質(zhì)量解的幾率。另一方面是具有足夠的多樣性,避免算法反復(fù)陷入同一個(gè)局部區(qū)域。為對(duì)比分析不同解構(gòu)造方法的性能,本文針對(duì)對(duì)稱(chēng)TSP設(shè)計(jì)并實(shí)現(xiàn)4種不同的初始解構(gòu)造方法,分別為基于距離的初始解構(gòu)造方法、基于歷史信息加以學(xué)習(xí)的全局構(gòu)造方法、基于歷史信息加以學(xué)習(xí)的局部構(gòu)造方法、基于過(guò)濾網(wǎng)絡(luò)及學(xué)習(xí)機(jī)制的初始解構(gòu)造方法。其中,第一個(gè)方法為對(duì)比基準(zhǔn)算法,僅利用算例的靜態(tài)結(jié)構(gòu)信息來(lái)構(gòu)造解,后3種方法為基于強(qiáng)化學(xué)習(xí)[22]的學(xué)習(xí)型算法,嘗試?yán)盟阉鬟^(guò)程中獲取的有用信息指引解的構(gòu)造過(guò)程。將上述4種初始解構(gòu)造方法與基于2-Opt變換的局部搜索過(guò)程相結(jié)合,得到4個(gè)不同版本的ILS算法,并利用25個(gè)國(guó)際標(biāo)準(zhǔn)算例對(duì)其進(jìn)行測(cè)試。

1 初始解構(gòu)造方法

1.1 基于距離的構(gòu)造方法(方法1)

采用逐步拓展的方式構(gòu)造解,即從起始城市(假設(shè)為1號(hào))開(kāi)始,按如下方式迭代選擇某個(gè)城市作為下一個(gè)待訪問(wèn)城市:將所有尚未被選中的城市視作候選城市集A,將各候選城市按其與當(dāng)前城市的距離從近到遠(yuǎn)排序,距離第k近的城市被選中的概率為pk=α×(1-α)k-1,其中,α∈(0,1]為控制概率分布參數(shù),且α越大,越傾向于選擇距離較近的城市,否則初始解的多樣性越強(qiáng)。距當(dāng)前城市最遠(yuǎn)的城市被選中的概率與其他候選城市被選中的概率之和為1,迭代上述過(guò)程,直至所有城市都已訪問(wèn),之后返回起始城市,即得到一個(gè)合法的TSP初始解。該方法不僅優(yōu)先考慮距離較近的候選城市,還引入了隨機(jī)性,使得每次生成的初始解具備一定的多樣性。通過(guò)調(diào)整參數(shù)α的取值,可以適當(dāng)控制所生成解的多樣性。然而，該方法僅考慮城市間的距離等靜態(tài)信息,未充分利用搜索過(guò)程中發(fā)現(xiàn)的有用信息。文獻(xiàn)[23]研究表明,對(duì)于多數(shù)TSP算例而言,局部最優(yōu)解中的邊大部分也屬于全局最優(yōu)解。為驗(yàn)證該結(jié)論,本文采用TSPLIB[15]中的25個(gè)算例進(jìn)行測(cè)試。采用方法1構(gòu)造每個(gè)算例的初始解,然后采用基于2-Opt的局部搜索方法將其優(yōu)化至局部最優(yōu)，如此重復(fù)1 000次,計(jì)算局部最優(yōu)解與全局最優(yōu)解中重合邊所占百分比。結(jié)果顯示,在25個(gè)算例上,局部最優(yōu)解中平均有80.9%的邊屬于全局最優(yōu)解,驗(yàn)證了文獻(xiàn)[23]的結(jié)論。

為充分利用上述結(jié)論,本文創(chuàng)建一個(gè)用來(lái)記錄歷史信息的n×n矩陣W,其元素wij表示邊(i,j)在局部最優(yōu)解中出現(xiàn)的次數(shù)。同時(shí),用變量Num記錄已經(jīng)得到的局部最優(yōu)解的個(gè)數(shù)(以上數(shù)值均初始化為0)。將ILS算法最開(kāi)始的T個(gè)迭代周期作為預(yù)學(xué)習(xí)過(guò)程,期間每個(gè)迭代周期仍采用基于距離的構(gòu)造方法來(lái)構(gòu)造初始解,然后采用局部搜索方法將其優(yōu)化為局部最優(yōu)解,將變量Num加1,并采用以下方法更新矩陣W:若城市i和城市j在所得局部最優(yōu)解中相鄰,則wij和wji分別加1,否則仍保持不變。

經(jīng)過(guò)預(yù)學(xué)習(xí)后,W中記錄了有用的歷史信息,可用于指導(dǎo)后續(xù)的初始解構(gòu)造過(guò)程?；诖?在ILS的后續(xù)迭代周期內(nèi)(應(yīng)用階段),可采用基于強(qiáng)化學(xué)習(xí)的方法來(lái)構(gòu)造初始解。強(qiáng)化學(xué)習(xí)的基本原理為:若某個(gè)決策的效果好,則給予其正向激勵(lì),提升該決策被采納的幾率;反之則給予其負(fù)向激勵(lì),降低該決策被采納的幾率[22]。針對(duì)對(duì)稱(chēng)TSP,本文嘗試3種基于強(qiáng)化學(xué)習(xí)的解構(gòu)造方法用于解的構(gòu)造過(guò)程。

1.2 基于歷史信息加強(qiáng)學(xué)習(xí)的全局構(gòu)造方法(方法2)

采用從初始城市出發(fā)逐步拓展的方式生成初始解,但各候選城市被選中的概率與基于距離的構(gòu)造方法不同。假設(shè)當(dāng)前城市為g,則對(duì)每個(gè)候選城市i∈A按式(1)定義一個(gè)權(quán)重系數(shù):

(1)

各個(gè)候選城市i∈A被選中的概率為:

(2)

其中,q∈[0,1]為強(qiáng)化學(xué)習(xí)所需參數(shù)，q值越大,越傾向于選擇出現(xiàn)頻次最高的邊,算法的集中性越強(qiáng),反之則算法的疏散性越強(qiáng)。通過(guò)調(diào)整q值可以靈活控制算法的集中性和疏散性。

1.3 基于歷史信息強(qiáng)化學(xué)習(xí)的局部構(gòu)造方法(方法3)

與方法2不同,方法3不通過(guò)從頭開(kāi)始逐步拓展的方式構(gòu)建一個(gè)初始解,而是在上一輪局部搜索所得解的基礎(chǔ)上,通過(guò)局部變換得到一個(gè)新的初始解。假如上一輪局部搜索所得局部最優(yōu)解為S(環(huán)路),在S中隨機(jī)選擇一段子路徑(起始城市隨機(jī)選擇,路徑長(zhǎng)度為[n/6,n/4]之間的隨機(jī)整數(shù)),將該子路徑上的邊全部刪除,S中其余的邊保持不變。從刪除子路徑的起始城市出發(fā),采用與基于歷史信息加強(qiáng)學(xué)習(xí)的全局構(gòu)造方法類(lèi)似過(guò)程進(jìn)行迭代,按概率選擇候選城市直至重新形成一個(gè)環(huán)路為止,并作為新一輪局部搜索的初始解。

以TSPLIB[15]中的eil51(包含51個(gè)城市)為例,圖1展示了采用方法3構(gòu)造初始解的示例過(guò)程。其中,圖1(c)中的虛線為添加的邊。

圖1 采用方法3構(gòu)造初始解的示例過(guò)程

1.4 基于過(guò)濾網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)的構(gòu)造方法(方法4)

與方法3相似,方法4也在上一輪局部搜索所得局部最優(yōu)解S的基礎(chǔ)上,通過(guò)局部變換的方式得到一個(gè)初始解。兩者的區(qū)別在于,方法4不再刪除一段連續(xù)的子路徑,而是通過(guò)一個(gè)過(guò)濾網(wǎng)絡(luò),基于頻次矩陣W中的信息,過(guò)濾掉S中的若干條邊。S中的每條邊(i,i+1)被刪除的概率為(1-wi,i+1)/Num,在局部最優(yōu)解中出現(xiàn)頻次越低的邊,被刪除的概率越大。按該方式過(guò)濾后,S將變成由若干段子路徑或者孤立點(diǎn)組成的集合。在該基礎(chǔ)上,通過(guò)逐步增加邊的方式將其修復(fù)成完整的環(huán)路。為此,將所有度小于2的城市作為候選城市集A(包括每段子路徑的端點(diǎn)以及所有孤立點(diǎn)),然后從A中任選一個(gè)城市作為出發(fā)城市,并迭代執(zhí)行以下過(guò)程:若當(dāng)前城市的下一個(gè)城市已確定(在過(guò)濾時(shí)未被刪除),則將下一個(gè)城市作為當(dāng)前城市,否則采用與方法2類(lèi)似的規(guī)則,按概率從A中選擇某個(gè)候選城市作為下一個(gè)城市,并用其替換當(dāng)前城市。迭代上述過(guò)程,直至形成完整的環(huán)路,并得到一個(gè)新的初始解。

圖2為采用方法4構(gòu)造初始解的示例過(guò)程(以eil51為例)。

圖2 采用方法4構(gòu)造初始解的示例過(guò)程

值得注意的是,按方法2、方法3與方法4生成初始解后,都需采用局部搜索方法(詳見(jiàn)下節(jié))將其優(yōu)化至局部最優(yōu),然后采用與預(yù)學(xué)習(xí)階段相同的方法更新矩陣W中的元素及變量Num的值,從而實(shí)現(xiàn)持續(xù)學(xué)習(xí)。

2 迭代局部搜索算法流程

在TSP上,2-Opt是一個(gè)被廣泛使用的操作算子,其基本思想是從當(dāng)前解中刪除2條邊,然后再添加2條不同的邊將其重新連接成合法解。采用2-Opt操作對(duì)解進(jìn)行一次變換的過(guò)程如圖3所示。

圖3 采用2-Opt操作對(duì)解進(jìn)行一次變換的過(guò)程

如圖3所示,給定2個(gè)不相鄰的城市i和j,刪除邊(i,i+1)和(j,j+1)后,添加邊(i,j)和(i+1,j+1)是讓其重新成為合法解的唯一方式,所對(duì)應(yīng)的變換操作即為一個(gè)2-Opt操作,其操作復(fù)雜度為O(1)。不難發(fā)現(xiàn),給定一個(gè)具有n個(gè)城市的環(huán)路,總共有O(n2)個(gè)可能的2-Opt操作。為降低總計(jì)算復(fù)雜度,選定城市i后,將城市j限定為與城市i距離最近的前10個(gè)城市,從而將可能的2-Opt操作數(shù)量控制在O(n)之內(nèi),通過(guò)犧牲優(yōu)度來(lái)大幅提升計(jì)算速度。

為驗(yàn)證2-Opt操作的優(yōu)化能力,實(shí)驗(yàn)仍采用TSPlib中的25個(gè)算例進(jìn)行測(cè)試。對(duì)每個(gè)算例,使用方法1構(gòu)造出初始解,再使用基于2-Opt操作的局部搜索算法對(duì)其進(jìn)行優(yōu)化,直至達(dá)到局部最優(yōu)解,并循環(huán)執(zhí)行1 000次。實(shí)驗(yàn)結(jié)果表明,初始解的總路徑長(zhǎng)度與全局最優(yōu)解的總路徑長(zhǎng)度之間的平均偏差為47.7%,經(jīng)過(guò)2-Opt操作優(yōu)化后平均偏差減小至8.8%,說(shuō)明2-Opt操作可有效優(yōu)化初始解。雖然采用k-Opt(k>2)或者LK[16]等更為復(fù)雜的操作算子有希望取得進(jìn)一步的改進(jìn),但由于本文的重點(diǎn)是研究初始解的構(gòu)造方法而非局部?jī)?yōu)化方法,因此本文不采用上述復(fù)雜的操作算子。

在此基礎(chǔ)上,為對(duì)比4種初始解構(gòu)造方法對(duì)ILS算法性能的影響,將其分別與基于2-Opt操作的局部搜索過(guò)程相結(jié)合,得到4個(gè)不同版本的ILS算法。各版本ILS算法的框架相同,且統(tǒng)一如算法1所示,唯一的區(qū)別在于各版本ILS算法構(gòu)造初始解的方法各不相同(算法1中的步驟2)。

算法1ILS算法

輸入無(wú)向圖G=(V,E)

輸出TSP的合法解

步驟1將矩陣W中的各元素及變量Num初始化為0。

步驟2構(gòu)造初始解S,預(yù)學(xué)習(xí)階段統(tǒng)一采用方法1構(gòu)造初始解,預(yù)學(xué)習(xí)階段結(jié)束后分別采用方法1～方法4構(gòu)造初始解。

步驟3對(duì)每一個(gè)候選的2-Opt操作,若執(zhí)行該操作后所得解比當(dāng)前解S更優(yōu),則執(zhí)行該2-Opt操作,否則嘗試下一個(gè)候選的2-Opt操作。

步驟4重復(fù)上述局部?jī)?yōu)化過(guò)程,直至通過(guò)2-Opt操作無(wú)法得到改進(jìn)解,即得到一個(gè)局部最優(yōu)解。

步驟5利用所得局部最優(yōu)解的信息更新矩陣W中各元素的值,并令變量Num增加1。

步驟6若滿足停機(jī)條件(迭代周期達(dá)到上限),返回搜索到的最優(yōu)解,否則跳轉(zhuǎn)至步驟2。

3 實(shí)驗(yàn)結(jié)果與分析

為對(duì)比分析不同初始解構(gòu)造方法的效果,按上述方法得到4個(gè)版本的ILS算法,分別命名為ILS-V1、ILS-V2、ILS-V3、ILS-V4。從國(guó)際公開(kāi)算例庫(kù)TSPLIB[15]中選擇25個(gè)具有代表性的算例作為測(cè)試集,對(duì)比分析4個(gè)版本ILS算法的性能。

3.1 參數(shù)設(shè)置

3種強(qiáng)化學(xué)習(xí)方法依賴(lài)于2個(gè)重要的參數(shù),即控制預(yù)學(xué)習(xí)迭代周期數(shù)量的參數(shù)T,以及控制強(qiáng)化學(xué)習(xí)集中性和疏散性的參數(shù)q。為合理設(shè)置參數(shù)值,從25個(gè)測(cè)試算例中選取6個(gè)具有代表性的算例(城市數(shù)量分別為51、152、200、264、318及442),然后對(duì)比不同的參數(shù)取值在這6個(gè)算例上的表現(xiàn)結(jié)果,具體步驟為:

1)由于2個(gè)參數(shù)相關(guān)性較小,因此分別對(duì)其進(jìn)行設(shè)置。首先調(diào)試參數(shù)T,令q=0.8且保持不變,令T從20開(kāi)始,以步長(zhǎng)為20逐步增大至500,得到25個(gè)不同的T值。在每個(gè)T值下,針對(duì)每個(gè)測(cè)試算例,分別采用ILS-V2、ILS-V3、ILS-V4迭代執(zhí)行1 000個(gè)周期,并統(tǒng)計(jì)每次迭代所得的平均路徑長(zhǎng)度。實(shí)驗(yàn)結(jié)果表明,在總共18個(gè)測(cè)試場(chǎng)景下(6個(gè)算例,每個(gè)算例運(yùn)行3種算法),T為[60,200]時(shí),總體表現(xiàn)較好,參數(shù)T=100時(shí)，其中8個(gè)場(chǎng)景下的平均路徑長(zhǎng)度最小(具體數(shù)據(jù)可掃描首頁(yè)OSID二維碼,查閱附件2),整體表現(xiàn)最好。因此,本文設(shè)置T值為100。

2)類(lèi)似地,為合理設(shè)置參數(shù)q,令T保持為100,令q從0.65開(kāi)始,以步長(zhǎng)為0.05逐步增大至0.95,得到7個(gè)不同的q值。針對(duì)每個(gè)q值,采用上述類(lèi)似方法測(cè)試ILS-V2、ILS-V3、ILS-V4在6個(gè)算例上的平均路徑長(zhǎng)度。實(shí)驗(yàn)結(jié)果表明,最優(yōu)q值與算例規(guī)?？傮w呈負(fù)相關(guān)關(guān)系。在18個(gè)測(cè)試場(chǎng)景下,q=0.8時(shí)，其中7個(gè)場(chǎng)景下所得的平均路徑長(zhǎng)度最小(具體數(shù)據(jù)可掃描首頁(yè)OSID二維碼,查閱附件3),整體表現(xiàn)最好。因此,本文設(shè)置q值為0.8。

綜上所述,各版本ILS算法涉及參數(shù)及其取值如表1所示。

表1 各版本ILS算法涉及參數(shù)及其取值

3.2 實(shí)驗(yàn)結(jié)果

確定參數(shù)取值后,對(duì)于25個(gè)算例中的每個(gè)算例,采用4個(gè)版本的ILS算法分別迭代運(yùn)行1 000個(gè)周期(計(jì)算平臺(tái)統(tǒng)一為2.5 GHz CPU和8.0 GB內(nèi)存),計(jì)算結(jié)果如表2所示。在表2中,第1列為算例名稱(chēng),第2列為其全局最優(yōu)解(記為Vopt),第3列～第7列為各算法的結(jié)果,且最優(yōu)結(jié)果加粗表示,若與已知最優(yōu)解持平,則用“*”標(biāo)注。第4列和第5列為各種算法進(jìn)行1 000次局部搜索所得最短路徑長(zhǎng)度(Vbest)及對(duì)應(yīng)的最小偏差,第6列和第7列為各算法進(jìn)行1 000次局部搜索得到的平均路徑長(zhǎng)度(Vavg)及對(duì)應(yīng)的平均偏差。最小偏差和平均偏差計(jì)算方法為:

(3)

(4)

表2 4個(gè)版本ILS算法在25個(gè)測(cè)試算例上的計(jì)算結(jié)果

續(xù)表

續(xù)表

從表2可以看出,在25個(gè)測(cè)試算例上,從最短路徑長(zhǎng)度Vbest角度而言,4個(gè)版本的ILS算法分別在1個(gè)、3個(gè)、14個(gè)、21個(gè)算例上表現(xiàn)最佳(部分并列最佳),且其對(duì)應(yīng)的最小偏差的平均值(在25個(gè)算例上取平均)分別為2.11%、1.43%、0.56%、0.48%;從平均路徑長(zhǎng)度Vavg角度而言,4個(gè)版本的ILS算法分別在0個(gè)、0個(gè)、0個(gè)、25個(gè)算例上表現(xiàn)最好(ILS-V4在所有算例上均表現(xiàn)最佳),且其對(duì)應(yīng)的平均偏差的平均值分別為8.83%、6.63%、4.09%、2.29%。

為檢驗(yàn)各種算法之間是否存在顯著統(tǒng)計(jì)性差異,對(duì)其最小偏差和平均偏差分別采用Wilcoxon檢驗(yàn),得到兩兩之間的p-value,具體如表3、表4所示。由表3、表4可以看出,從最小偏差的角度而言,ILS-V1與ILS-V2的表現(xiàn)無(wú)顯著差異,ILS-V3與ILS-V4的表現(xiàn)較為接近,但前兩者與后兩者之間存在顯著統(tǒng)計(jì)性差異;從平均偏差的角度而言,4個(gè)版本的ILS算法之間都存在顯著統(tǒng)計(jì)性差異。

表3 各版本ILS算法基于最小偏差的p-value

表4 各版本ILS算法基于平均偏差的p-value

從25個(gè)測(cè)試算例中選取5個(gè)算例(城市數(shù)量分別為51、152、264、318、442)深入分析各版本算法的搜索過(guò)程。針對(duì)每個(gè)算例,分別記錄各版本ILS算法在每個(gè)迭代周期結(jié)束時(shí)(總共1 000個(gè)周期)所得到的最短路徑和平均路徑,并給出其迭代收斂結(jié)果,具體如圖4所示。

圖4 各版本ILS算法在8個(gè)典型算例上的最短路徑及平均路徑的迭代收斂結(jié)果

從圖4可以看出,在上述5個(gè)測(cè)試算例上,3種基于強(qiáng)化學(xué)習(xí)的ILS算法在收斂速度上明顯優(yōu)于ILS-V1,尤其是在平均路徑長(zhǎng)度維度上,隨著迭代周期的增加,各版本ILS算法得到的平均路徑長(zhǎng)度均呈現(xiàn)逐漸降低的趨勢(shì),且ILS-V4的下降速度明顯快于其他算法，這說(shuō)明了過(guò)濾網(wǎng)絡(luò)在構(gòu)造初始解上的有效性,其主要原因有:1)相比于僅基于靜態(tài)距離信息的ILS-V1,過(guò)濾網(wǎng)絡(luò)可充分利用歷史累積的有用信息,從而引導(dǎo)初始解的構(gòu)造過(guò)程；2)相比于ILS-V2和ILS-V3,基于過(guò)濾網(wǎng)絡(luò)的算法ILS-V4可識(shí)別出一定比例的潛力較小的邊并將其過(guò)濾掉,同時(shí)保留大部分潛力較大的候選邊,該篩選機(jī)制可在不嚴(yán)重破壞當(dāng)前解結(jié)構(gòu)的前提下,進(jìn)一步優(yōu)化新構(gòu)造的解,從而提升構(gòu)造解的質(zhì)量。

4 結(jié)束語(yǔ)

本文針對(duì)TSP提出4種不同的解構(gòu)造方法,包括一個(gè)僅利用算例結(jié)構(gòu)等靜態(tài)信息的基準(zhǔn)方法和3種基于歷史信息的強(qiáng)化學(xué)習(xí)方法,并將其與2-Opt操作相結(jié)合得到ILS算法。實(shí)驗(yàn)結(jié)果表明,通過(guò)學(xué)習(xí)和利用搜索過(guò)程中的有用信息,可有效提升ILS算法的整體性能,且基于過(guò)濾網(wǎng)絡(luò)的強(qiáng)化學(xué)習(xí)方法整體表現(xiàn)最佳。后續(xù)嘗試將基于強(qiáng)化學(xué)習(xí)的初始解構(gòu)造方法與Lin-Kernighan[17]等經(jīng)典局部搜索方法相結(jié)合,以得到性能更佳的ILS算法。