王 娜，陳賢富

(中國(guó)科學(xué)技術(shù)大學(xué) 信息科學(xué)技術(shù)學(xué)院，安徽 合肥 230027)

0 引言

人類認(rèn)知具有層次性[1]，這種層次結(jié)構(gòu)性大大簡(jiǎn)化了問題求解的復(fù)雜性，提高了認(rèn)知的敏捷性與智能性。基于層次性認(rèn)知以及非監(jiān)督學(xué)習(xí)等技術(shù)發(fā)展，深度學(xué)習(xí)技術(shù)近年來在數(shù)據(jù)挖掘、自然語(yǔ)言處理、視音頻智能信息處理等智能認(rèn)知領(lǐng)域取得重要突破，迅速成為IT技術(shù)前沿研究熱點(diǎn)。

從計(jì)算機(jī)理看，機(jī)器學(xué)習(xí)可看成特征參量關(guān)系模型的擬合與優(yōu)化過程，優(yōu)化與學(xué)習(xí)的機(jī)制機(jī)理是相通的，聯(lián)想、優(yōu)化本質(zhì)上也是一種學(xué)習(xí)。為此，本文將深度學(xué)習(xí)Dropout等技術(shù)與模擬退火算法相結(jié)合，提出一種變參數(shù)深度玻爾茲曼計(jì)算模型，并主要針對(duì)復(fù)雜TSP優(yōu)化問題開展了具體算法研究與實(shí)驗(yàn)研究。

TSP問題是典型NP_Hard型問題，其可行解空間規(guī)模為n!/2。鑒于TSP問題的組合爆炸性質(zhì)，除極小規(guī)模TSP問題外，一般情形只能采用啟發(fā)式智能算法進(jìn)行搜索優(yōu)化求解。流行實(shí)用的TSP全局優(yōu)化算法主要有模擬生物演化、模擬熱處理退火及各種混合型算法。其中，模擬生物演化型算法又可分為基因重組型(遺傳算法、進(jìn)化策略等)與集群智能型(蟻群算法[4]、鳥群算法、魚群算法等)兩大類，在求解TSP問題中主要存在基因型重組與表現(xiàn)型評(píng)估矛盾、空間復(fù)雜度較高、遺傳支配、早熟收斂、有序問題的遺傳操作設(shè)計(jì)、局部搜索與全局優(yōu)化矛盾等問題。為解決粗粒度全局搜索與細(xì)粒度局部?jī)?yōu)化之間的矛盾，分層混合算法結(jié)構(gòu)雖已成為一種流行的改進(jìn)思路，但有序問題編碼設(shè)計(jì)及其遺傳操作問題、空間復(fù)雜度較高、遺傳支配個(gè)體壟斷群體更新策略等原因?qū)е碌脑缡焓諗康葐栴}仍然存在，規(guī)模效應(yīng)問題依然突出。

模擬退火算法[5-6]是一種細(xì)粒度的基于表現(xiàn)型評(píng)估的全局搜索優(yōu)化算法，也是公認(rèn)的解決TSP問題較合適的算法之一。理論上說，模擬退火是一標(biāo)準(zhǔn)馬爾可夫過程，在充分搜索、合理選擇、緩慢降溫等條件下以概率1收斂于全局最優(yōu)解。實(shí)際上，由于無(wú)法滿足理想的充分搜索、緩慢降溫等條件，模擬退火算法設(shè)計(jì)依然只能在全局搜索與局部?jī)?yōu)化、較好的優(yōu)化效果與較快的搜索效率之間進(jìn)行權(quán)衡，其隨機(jī)搜索軌跡由初態(tài)與一系列轉(zhuǎn)移概率矩陣確定:

π=π0*[p1]n*[p2]n*[pk]n

(1)

其中π0為初始狀態(tài)，[pk]為一步轉(zhuǎn)移概率矩陣。

模擬退火算法搜索優(yōu)化性能由初始狀態(tài)與一步轉(zhuǎn)移概率矩陣決定，其中決定一步轉(zhuǎn)移概率矩陣參數(shù)的除了溫度、玻爾茲曼模型參數(shù)外，還與所需求解具體問題的參量分布密切相關(guān)。流行的模擬退火算法研究主要集中于SA模型參數(shù)的變化與初始狀態(tài)的選擇策略方面，對(duì)問題參數(shù)擾動(dòng)所產(chǎn)生的影響尚缺乏充分研究考量。

一方面，變參數(shù)動(dòng)態(tài)優(yōu)化問題本身就是優(yōu)化應(yīng)用領(lǐng)域的前沿?zé)狳c(diǎn)課題；另一方面，從動(dòng)態(tài)變化角度研究靜態(tài)最優(yōu)化問題也不失為一種合理可行的優(yōu)化算法改進(jìn)思路。鑒于這些研究考慮，本文提出并研究一種基于深度學(xué)習(xí)的層次結(jié)構(gòu)與Dropout技術(shù)的變參數(shù)并行玻爾茲曼算法模型，并結(jié)合TSP優(yōu)化問題介紹具體研究思路與算法模型設(shè)計(jì)。

1 變參數(shù)玻爾茲曼算法模型設(shè)計(jì)

鑒于TSP問題的可行解空間規(guī)模為n!/2，規(guī)模較大的TSP局部?jī)?yōu)化問題實(shí)際上也是較復(fù)雜的全局性搜索問題。根據(jù)式(1)，通過選擇合適的初始狀態(tài)，模擬退火算法模型參數(shù)的合理設(shè)計(jì)以及問題參量的擾動(dòng)等手段，進(jìn)一步提高模擬退火算法的優(yōu)化質(zhì)量。

有鑒如此，變參數(shù)分層玻爾茲曼優(yōu)化算法模型框架主要由三部分組成。其一為全局優(yōu)化，可采用模擬退火或模擬演化等全局優(yōu)化算法模型實(shí)現(xiàn)，初步獲取若干高質(zhì)量全局較優(yōu)可行解，為進(jìn)一步分層優(yōu)化、變參數(shù)優(yōu)化提供基本參考數(shù)據(jù)。本文采用常規(guī)SA算法產(chǎn)生初步全局可行解，具體算法流程如圖1所示。其二，為克服SA算法陷入局部陷阱，擬采用深度學(xué)習(xí)中的Dropout、Dropin等策略，實(shí)現(xiàn)變參數(shù)擾動(dòng)。Dropout等深度學(xué)習(xí)技術(shù)[7]可用于防止過擬合學(xué)習(xí)、簡(jiǎn)化模型結(jié)構(gòu)以及降低算法復(fù)雜度等方面?？紤]到TSP問題與神經(jīng)網(wǎng)絡(luò)存在結(jié)構(gòu)相似性、機(jī)理相關(guān)性，故在TSP優(yōu)化過程中，使較優(yōu)可行解上某相鄰兩個(gè)城市間的距離擴(kuò)大到一定值，使該條路徑成為不經(jīng)之路(dropout)，或使某相鄰兩個(gè)城市間的距離縮小到一定值，使該條路徑成為必經(jīng)路徑(dropin)，運(yùn)用變參數(shù)動(dòng)態(tài)優(yōu)化策略以期跳出局部陷阱。其三，鑒于大規(guī)模TSP問題優(yōu)化的復(fù)雜度高，其局部片段優(yōu)化也是全局性較高的優(yōu)化子問題，可采用分段優(yōu)化策略[8]，進(jìn)一步提高優(yōu)化質(zhì)量。

圖1 模擬退火算法流程圖

2 算法設(shè)計(jì)與實(shí)驗(yàn)研究

2.1 Drop算法設(shè)計(jì)

Drop邊的選擇策略可采取以下幾種方式：

(1)隨機(jī)選擇路徑中某條邊進(jìn)行縮放，該策略盲目性較大，算法復(fù)雜度過高。

(2)從若干較優(yōu)路徑中選擇某一公共邊或不同邊進(jìn)行縮放，可使算法兼顧搜索效率與優(yōu)化效果。

(3)人機(jī)交互，人眼觀察若干較優(yōu)路徑圖，運(yùn)用人類智慧選取某條邊進(jìn)行縮放。

實(shí)驗(yàn)研究中，本文采用了上述策略(2)與策略(3)Drop學(xué)習(xí)技術(shù)，其算法流程圖如圖2與圖3所示。

圖2 本文算法流程圖

圖3 Dropout 具體算法流程圖

2.2 分段優(yōu)化

為進(jìn)一步提高優(yōu)化質(zhì)量，在獲得原問題的一個(gè)高質(zhì)量可行解后，再通過分段優(yōu)化算法進(jìn)行局域精細(xì)優(yōu)化，具體算法流程如圖4所示，其中分段選擇的策略如下：

(1)隨機(jī)分段

隨機(jī)選擇路徑中某一起點(diǎn)，該起點(diǎn)后的若干城市作為一個(gè)局部片段進(jìn)行優(yōu)化。

(2)人機(jī)交互

人眼觀察若干較優(yōu)路徑圖，根據(jù)城市坐標(biāo)的結(jié)構(gòu)特征，由內(nèi)到外進(jìn)行局部片段的選擇。

圖4 分段算法流程圖

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

為驗(yàn)證算法的有效性，選用了國(guó)際上通用的TSP測(cè)試庫(kù)[9]TSPLIB中多個(gè)實(shí)例進(jìn)行測(cè)試。實(shí)驗(yàn)環(huán)境為Inter(R) Core(TM)i5-4590 CPU @3.30 GHz、Windows 7、Visual Studio 2010。

本文對(duì)TSPLIB中eil50、eil51、eil75、eil76實(shí)例進(jìn)行了實(shí)驗(yàn)，其中eil50、eil51、eil75、pr1002城市TSP均搜索到迄今已知最優(yōu)路徑[10]，其中eil51城市，本算法搜索到了新的、比迄今已知最優(yōu)解更優(yōu)的TSP路徑(浮點(diǎn)計(jì)算)，實(shí)驗(yàn)結(jié)果和路徑圖如表1和圖5～9所示。

表1 TSPLIB提供的路徑值與本文算法所得最優(yōu)路徑比較表

圖5 本文算法得到的eil51實(shí)例最優(yōu)路徑圖d=428.329

圖6 TSPLIB提供的eil51實(shí)例最優(yōu)路徑圖d=429.983

圖7 本文算法得到的eil76實(shí)例最優(yōu)路徑圖d=544.369

圖8 TSPLIB提供的eil76實(shí)例最優(yōu)路徑圖d=545.388

圖9 pr1002實(shí)例經(jīng)過本文算法得到的最優(yōu)路徑圖d=259 066.663

本文算法所得城市TSP最優(yōu)路徑如下：

eil51城市TSP: 路徑長(zhǎng)度=428.328 712

(30,48) (38,46) (37,52) (42,57) (49,49) (52,41) (56,37) (52,33) (48,28) (45,35) (40,30) (42,21) (36,16) (39,10) (46,10) (59,15) (51,21) (58,27) (61,33) (62,42) (58,48) (57,58) (62,63) (63,69) (52,64) (43,67) (37,69) (27,68) (31,62) (25,55) (21,47) (16,57) (17,63) (5,64) (8,52) (12,42) (7,38) (5,25) (10,17) (5,6) (13,13) (21,10) (30,15) (32,22) (27,23) (20,26) (17,33) (25,32) (31,32) (32,39) (30,40)

4 結(jié)論

本文提出并初步研究了一種基于深度學(xué)習(xí)之層次

結(jié)構(gòu)與Drop技術(shù)的變參數(shù)玻爾茲曼算法模型，并通過TSP優(yōu)化實(shí)例展示了良好的優(yōu)化性能與優(yōu)化結(jié)果。本文提出并研究的若干算法設(shè)計(jì)思路還可應(yīng)用于動(dòng)態(tài)TSP優(yōu)化、神經(jīng)學(xué)習(xí)、聯(lián)想記憶等其他領(lǐng)域，具體算法模型有待進(jìn)一步探索研究。

[1] MASLOW A H.A theory of human motivation[J]. PsychologicalReview,1943,50(8):370-396.

[2] GAREY M R, JOHNSON D S. Computers and intractability:a guide to the theory of NP-completeness [M]. San Francisco: Freeman W H, 1979.

[3] 陳賢富，莊鎮(zhèn)泉，王煦法，遺傳算法的自適應(yīng)進(jìn)化策略及TSP問題的遺傳優(yōu)化[J].電子學(xué)報(bào), 1997，25(7)：111-114.

[4] 許凱波, 魯海燕, 程畢蕓, 等. 求解TSP的改進(jìn)信息素二次更新與局部?jī)?yōu)化蟻群算法[J]. 計(jì)算機(jī)應(yīng)用, 2017, 37(6): 1686-1691.

[5] 張盛意，蔡之華，占志剛.基于改進(jìn)模擬退火的遺傳算法求解0-1背包問題[J].微電子學(xué)與計(jì)算機(jī)，2011，28(2)：61-64.

[6] 何慶, 吳意樂, 徐同偉. 改進(jìn)遺傳模擬退火算法在TSP優(yōu)化中的應(yīng)用[J]. 控制與決策, 2018,33(2):219-225.

[7] SRIVASTAVA N, HINTON G E, KRIZHEVSKY A, et al. Dropout: a simple way to prevent neural networks from overfitting[J].Journal of Machine Learning Research, 2014,15(1):1929-1958.

[8] 吳斌，史忠植.一種基于蟻群算法的TSP問題分段求解算法[J].計(jì)算機(jī)學(xué)報(bào)，2001,24(12)：1328-1333.

[9] 標(biāo)準(zhǔn)TSP測(cè)試庫(kù)[EB/OL].[2018-02-26]http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html.

[10] 標(biāo)準(zhǔn)TSP路徑歷史最優(yōu)解[EB/OL].[2018-02-26]http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/STSP.html.