王 娜，陳賢富

(中國科學技術大學 信息科學技術學院，安徽 合肥 230027)

0 引言

人類認知具有層次性[1]，這種層次結構性大大簡化了問題求解的復雜性，提高了認知的敏捷性與智能性?；趯哟涡哉J知以及非監(jiān)督學習等技術發(fā)展，深度學習技術近年來在數(shù)據(jù)挖掘、自然語言處理、視音頻智能信息處理等智能認知領域取得重要突破，迅速成為IT技術前沿研究熱點。

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

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

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

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

(1)

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

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

一方面，變參數(shù)動態(tài)優(yōu)化問題本身就是優(yōu)化應用領域的前沿熱點課題；另一方面，從動態(tài)變化角度研究靜態(tài)最優(yōu)化問題也不失為一種合理可行的優(yōu)化算法改進思路。鑒于這些研究考慮，本文提出并研究一種基于深度學習的層次結構與Dropout技術的變參數(shù)并行玻爾茲曼算法模型，并結合TSP優(yōu)化問題介紹具體研究思路與算法模型設計。

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

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

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

圖1 模擬退火算法流程圖

2 算法設計與實驗研究

2.1 Drop算法設計

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

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

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

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

實驗研究中，本文采用了上述策略(2)與策略(3)Drop學習技術，其算法流程圖如圖2與圖3所示。

圖2 本文算法流程圖

圖3 Dropout 具體算法流程圖

2.2 分段優(yōu)化

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

(1)隨機分段

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

(2)人機交互

人眼觀察若干較優(yōu)路徑圖，根據(jù)城市坐標的結構特征，由內到外進行局部片段的選擇。

圖4 分段算法流程圖

3 實驗結果與分析

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

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

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

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

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

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

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

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

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

eil51城市TSP: 路徑長度=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 結論

本文提出并初步研究了一種基于深度學習之層次

結構與Drop技術的變參數(shù)玻爾茲曼算法模型，并通過TSP優(yōu)化實例展示了良好的優(yōu)化性能與優(yōu)化結果。本文提出并研究的若干算法設計思路還可應用于動態(tài)TSP優(yōu)化、神經學習、聯(liá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)泉，王煦法，遺傳算法的自適應進化策略及TSP問題的遺傳優(yōu)化[J].電子學報, 1997，25(7)：111-114.

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

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

[6] 何慶, 吳意樂, 徐同偉. 改進遺傳模擬退火算法在TSP優(yōu)化中的應用[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].計算機學報，2001,24(12)：1328-1333.

[9] 標準TSP測試庫[EB/OL].[2018-02-26]http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html.

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