基于迭代局部搜索（ILS）的啟發(fā)式算法是目前最為先進(jìn)的旅行商問題求解算法,在多數(shù)國際公開算例上保持著世界最優(yōu)紀(jì)錄。解構(gòu)造方法是影響ILS性能的重要因素,為此,提出4種不同的解構(gòu)造方法。解構(gòu)造方法1為基準(zhǔn)算法,其僅利用城市間的距離等靜態(tài)結(jié)構(gòu)信息來構(gòu)造初始解,解構(gòu)造方法2～解構(gòu)造方法4則嘗試?yán)盟阉鬟^程中積累的歷史數(shù)據(jù),通過強(qiáng)化學(xué)習(xí)挖掘有用信息,用于引導(dǎo)解的構(gòu)造過程。在25個國際公開算例上的測試結(jié)果表明,基于歷史信息的強(qiáng)化學(xué)習(xí)方法可有效優(yōu)化構(gòu)造解的質(zhì)量,提升ILS整體性能。 

【文章來源】：計算機(jī)工程. 2020,46(11)北大核心CSCD

【文章頁數(shù)】：8 頁

【部分圖文】：

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

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

在TSP上,2-Opt是一個被廣泛使用的操作算子,其基本思想是從當(dāng)前解中刪除2條邊,然后再添加2條不同的邊將其重新連接成合法解。采用2-Opt操作對解進(jìn)行一次變換的過程如圖3所示。如圖3所示,給定2個不相鄰的城市i和j,刪除邊(i,i+1)和(j,j+1)后,添加邊(i,j)和(i+1,j+1)是讓其重新成為合法解的唯一方式,所對應(yīng)的變換操作即為一個2-Opt操作,其操作復(fù)雜度為O(1)。不難發(fā)現(xiàn),給定一個具有n個城市的環(huán)路,總共有O(n2)個可能的2-Opt操作。為降低總計算復(fù)雜度,選定城市i后,將城市j限定為與城市i距離最近的前10個城市,從而將可能的2-Opt操作數(shù)量控制在O(n)之內(nèi),通過犧牲優(yōu)度來大幅提升計算速度。

【參考文獻(xiàn)】：
期刊論文
[1]基于文化混合優(yōu)化算法的旅行商問題求解[J]. 馬晗,常安定,陳童,李江杰.  計算機(jī)工程與科學(xué). 2019(07)
[2]求解旅行商問題的近似骨架分段蟻群優(yōu)化算法[J]. 王飛鵬,譚旭杰.  計算機(jī)工程與設(shè)計. 2019(04)
[3]求解旅行商問題的搜尋者遺傳算法[J]. 張立毅,高楊,費(fèi)騰,王玉婧.  數(shù)學(xué)的實踐與認(rèn)識. 2019(07)
[4]基于離散粒子群優(yōu)化算法的含權(quán)旅行商問題新解法[J]. 錢真坤.  計算機(jī)應(yīng)用與軟件. 2019(01)
[5]基于模擬退火的自適應(yīng)離散型布谷鳥算法求解旅行商問題[J]. 張子成,韓偉,毛波.  電子學(xué)報. 2018(08)
[6]一種混合局部搜索算法的遺傳算法求解旅行商問題[J]. 宗德才,王康康.  計算機(jī)應(yīng)用與軟件. 2015(03)
[7]求解TSP問題的多級歸約算法[J]. 鄒鵬,周智,陳國良,顧鈞.  軟件學(xué)報. 2003(01)



本文編號：3280020