帶平衡約束矩形布局優(yōu)化問題的深度強化學習算法

摘 要： 帶平衡約束的矩形布局問題源于衛(wèi)星艙設備布局設計，屬于組合優(yōu)化問題。深度強化學習利用獎賞機制，通過數據訓練實現高性能決策優(yōu)化。針對布局優(yōu)化問題，提出一種基于深度強化學習的新算法DAR及其擴展算法IDAR。DAR用指針網絡輸出定位順序，再利用定位機制給出布局結果，算法的時間復雜度是O（n3）；IDAR算法在DAR的基礎上引入迭代機制，算法時間復雜度是O（n4），但能給出更好的結果。測試表明DAR算法具有較好的學習能力，用小型布局問題進行求解訓練所獲得的模型，能有效應用在大型問題上。在兩個大規(guī)模典型算例的對照實驗中，提出算法分別超出和接近目前最優(yōu)解，具有時間和質量上的優(yōu)勢。

關鍵詞： 布局優(yōu)化問題； 指針網絡； 強化學習； 深度學習

中圖分類號： TP181"" 文獻標志碼： A

文章編號： 1001-3695（2022）01-026-0146-05

doi：10.19734/j.issn.1001-3695.2021.05.0218

Deep reinforcement learning algorithm for rectangle layout optimization with equilibrium constraint

Xu Yichun， Wan Shuzhen， Dong Fangmin

（College of Computer amp; Information Technology， China Three Gorges University， Yichang Hubei 443002， China）

Abstract： The rectangle layout optimization problem with balance constraints is derived from the layout design of satellite module equipment. It belongs to combinatorial optimization problem. Deep reinforcement learning uses reward mechanism to realize high-performance decision optimization through data training. This paper proposed a new deep reinforcement learning algorithm DAR and its extension IDAR. The DAR algorithm output the optimized location sequence with a pointer network， and then used the positioning mechanism to give the layout results. The training of pointer network was realized by deep reinforcement learning. The time complexity of the DAR algorithm was O（n3）. The IDAR algorithm was an iteration version of DAR， which had better results but with a time complexity of O（n4）. The test results show that DAR algorithm has good lear-ning ability， and the model obtained by small layout problems can be effectively applied to large-scale problems. The results on two typical large-scaled instances show that the proposed algorithms have achieved or approached to the current best results， so that they have advantages both in time and solution quality.

Key words： layout optimization problem; pointer network; reinforcement learning; deep learning

帶平衡約束的布局優(yōu)化問題是具有NP難度的組合優(yōu)化問題，其背景是在一個返回式衛(wèi)星艙內，要求將一些給定的儀器、設備等部件進行合理的布置，使得各部件之間、部件與艙壁之間不存在干涉量，且衛(wèi)星艙在運行中易維持平衡［1］。該問題不僅在算法理論上具有重要意義，同時在工業(yè)制造上也極具價值。目前的求解算法在中小規(guī)模問題上已經解決得較好，包括擬物擬人算法［2，3］、演化算法［4］等，但是對于包含大量布局物的問題，如何減少算法的求解時間、提升結果的質量依然是研究的難點。

近年來，以神經網絡、強化學習為代表的機器學習算法在一些組合優(yōu)化問題上得到了應用，如旅行推銷員問題、背包問題、車輛調度問題等［5～8］。從原理上看，機器學習算法的優(yōu)勢是能通過訓練獲得問題求解的經驗，并將其應用到新的問題上，因此采用機器學習算法來提高求解布局優(yōu)化問題的性能具有合理性。本文針對帶平衡約束矩形布局優(yōu)化問題（rectangle layout optimization problem，RLOP）進行研究，提出一種面向該問題的深度強化學習求解算法（deep reinforcement learning algorithm for RLOP，DAR）。根據現有文獻，這是機器學習在布局優(yōu)化問題上的首次應用。首先用強化學習技術訓練一個指針網絡，然后用指針網絡獲取布局順序，再應用定位算法來得到近似最優(yōu)布局。在大規(guī)模問題上本文算法相對現有算法極具競爭力。同時，在DAR的基礎上引入迭代機制，本文還設計了一種擴展算法IDAR（iterative DAR），能給出比DAR更好的優(yōu)化結果。

1 相關工作

1.1 矩形布局優(yōu)化方法

馮恩民等人［9］首次提出了RLOP，用圖論和群的方法研究布局模式的同構性和等價性，并提出了進行全局優(yōu)化的框架；翟金剛等人［10］用包絡圓半徑作為目標函數，用面積定義矩形之間的干涉量，提出不干涉遺傳算法來進行優(yōu)化求解；馮恩銘等人［11］提出了一種改進的遺傳算法；Xu等人［12，13］用距離來定義矩形之間的干涉量，并分別用粒子群算法和模擬退火算法進行優(yōu)化;劉景發(fā)等人［14］應用Wang-Landau抽樣算法進行布局優(yōu)化，并提出了解決局部最優(yōu)問題的幾個策略，改善了布局結果。在前述的RLOP優(yōu)化求解方法中，每個矩形位置有橫縱坐標及角度，從而需要在R3n空間進行搜索，對于大規(guī)模問題優(yōu)化難度較高，得到的布局質量較不理想。徐義春等人［15］提出增加矩形的正交約束，從而將變量空間縮小到2nR2n，并設計了一種直接定位方法，然后應用遺傳算法對定位順序進行尋優(yōu)，該方法給出的結果相對第一類方法，布局質量有較大提高；隨后黃振東、季美等研究人員分別設計了不同的定位方法，并應用粒子群算法［16］、蟻群算法［17］等對定位順序進行優(yōu)化；而加入了正交約束后，黎自強、劉景發(fā)等人應用直接優(yōu)化目標函數的方法也取得了較好的結果［3，18～20］。

1.2 相關的機器學習技術以及在組合優(yōu)化問題中的應用

近年來，深度神經網絡快速發(fā)展，在圖像處理、自然語言處理等方面取得很大成功［21］。Sutskever等人［22］應用LSTM循環(huán)神經網絡構建了一個seq2seq模型，將一個輸入序列X={x1，x2，…，xn}映射到輸出序列Y={y1，y2，…，ym}，當X和Y分別是不同語言的單詞時，seq2seq模型可以實現機器翻譯功能；Bahdanau等人［23］在seq2seq模型中引入了注意力機制，在輸出yi時，考慮了與不同xj之間的聯系。在前述研究的基礎上，Vinyals等人［24］提出了指針網絡模型，其輸出序列Y代表單元xi的序列位置，作為例子文獻展示了指針網絡在旅行推銷員問題上的結果，但該模型用有監(jiān)督學習方法進行訓練，需要提供訓練數據的標簽。強化學習是一種利用環(huán)境獎賞進行學習的方法［25］，無須事先提供標簽；隨后，指針網絡與強化學習結合應用到了多種組合優(yōu)化問題上。Bello等人［5］提出一種指針網絡和強化學習的框架，應用于旅行推銷員問題、背包問題等；Hu等人［6］將指針網絡和強化學習技術結合解決一種新的三維立方體貨物包裝問題；Nazari等人［7］將指針網絡應用到車輛路徑問題；最近，Lu等人［8］設計了一種迭代框架，利用強化學習方法來求解車輛路徑問題。

5 實驗與討論

本文的測試計算在一臺3.1 GHz主頻CPU、16 GB內存的機器上進行，使用Python語言編程。

5.1 實驗1 DAR算法的訓練與測試

a）訓練集。隨機生成10萬條矩形布局問題實例，每個實例的矩形數目在5～10均勻分布，每個矩形的a、b、m在1～100均勻分布。

b）測試集。獨立產生四個測試集，各含1 000條布局問題實例，測試集1的矩形數目為5～10，其他三個測試集的矩形數目分別為20、40、60，a、b、m的分布與訓練集相同，也在1～100均勻分布。

c）參數設置。指針網絡和評價網絡的嵌入層和LSTM層以及MLP第1層的cell_size都為128，Adam學習器的學習率為0.002，訓練的迭代步數T設置為40萬次，D設置為10，每批實例數B設置為100。

d）對照算法。測試的主要目的是通過統(tǒng)計測試來驗證算法的學習能力，應用兩個算法作為對照：（a）設計算法Rnd，隨機產生一個定位序列s，調用定位算法P獲得布局結果；（b）文獻［15］中的遺傳算法GA，其參數設置參照按該文獻所述。

以平均包絡半徑作為評價指標，Rnd、GA與本文強化學習算法DAR的實驗結果如表1所示。表1的結果表明，雖然DAR算法是在n=5～10的矩形集上完成的模型訓練，但應用在更大規(guī)模的布局例上依然有效。在四個測試集上，DAR算法的包絡半徑結果要好于Rnd算法和GA，相對于Rnd算法平均有6.8%的提升，相對于GA平均有6.5%的提升。Mann Whitney U檢驗的結果證實在顯著性水平為0.01的情況下，DAR算法與Rnd和GA算法存在顯著的性能差異，進一步強化了前述結論。

由于Rnd和GA都應用了定位技術，所以測試集上的結果能夠說明DAR算法的性能并不僅是定位算法導致，DAR算法確實進行了有效學習。

5.2 實驗2 大規(guī)模算例上的結果

本領域文獻目前是以典型算例的方式進行實驗結果展示。通過文獻［3，14］中公布的兩個各包括100個布局物的大型公開算例對DAR和IDAR進行測試計算，其中DAR算法使用實驗1中訓練好的模型。

對照算法包括模擬退火算法SA［13］、壓縮算法CA_PSLS［12］、Wang-Landau抽樣算法HWL［14］、遺傳算法GA［15］、蟻群優(yōu)化算法ACO［18］、擬物擬人算法IBF［3］。其中SA、CA_PSLS和HWL是建立能量函數并用梯度下降法結合局部優(yōu)化處理機制的方法，這三個算法沒有使用正交策略；GA和ACO應用正交策略，采用定位法結合演化算法進行全局尋優(yōu);IBF算法屬于采用梯度下降并結合正交策略的方法。

表2中給出了對照實驗的結果，對比項包括包絡半徑、計算時間。雖然算法所用的硬軟件平臺不一樣，但是并沒有數量級的差別，所以表2中直接給出原始時間值以供參考。

1）算例1的結果分析

在算例1上，相對于比較的六種算法，DAR算法的半徑值排名第2，僅落后于另一個以定位算法為基礎的ACO算法，半徑值的差異僅4%；DAR領先于SA、CA_PSLS、HWL較多，因為這三個算法沒有使用正交策略，難以應付對大規(guī)模問題。從計算時間上看，DAR算法相比其他算法快了100倍以上。以上結果說明，對于大規(guī)模的問題，強化學習算法能夠應用學習到的布局經驗，在更快的時間內給出良好的布局解。

加入了迭代機制的IDAR算法，其優(yōu)化計算能力有了進一步提升，半徑排名上升為第一；另一方面，引入迭代后計算時間有了相應的增加，但仍優(yōu)于排名第二的ACO算法。

2）算例2的結果分析

與其他算法相比，DAR算法還是排名第二，超出SA、CA_PSLS和GA較多，僅落后于IBF算法約1.7%；同時DAR的時間性能表現出極大的優(yōu)勢，比其他算法快500倍以上。加入迭代機制后，IDAR算法的半徑值提高了一個百分點，與IBF已經非常接近，僅差0.7%，可以說性能相當，但是時間更快。

在以上兩個大型算例上的實驗結果表明，相對于現有算法，強化學習算法性能處于前列，能用更快的時間給出良好的布局解。圖5和6是IDAR算法給出的兩個算例的布局結果。

5.3 進一步的分析

通過實驗1和2的結果和分析，相對于傳統(tǒng)的搜索算法，本文提出的深度強化學習算法在求解時間和解的質量上都具有優(yōu)勢。本節(jié)進一步指出以下兩點以說明所提出算法的先進性：

a）傳統(tǒng)的搜索算法（如GA）進行布局問題求解時，都是從隨機解開始，通過各種搜索算子逐步收斂到優(yōu)化解，而面臨下一個新問題時，所有的工作需要重新開始。而本文深度強化學習算法能“記憶”以前的求解經驗，建立了問題和解之間的聯系，從而迅速地給出質量良好的解。

b）從圖5和6可以看出，本文算法在布局時較大的矩形多數靠近中心，而較小或者較窄的矩形自動排布在邊緣。雖然這種布局經驗也可能依靠人工總結得到，但是如果直接結合到算法中缺乏靈活性。而深度強化學習是將經驗體現在參數中，通過大數據訓練獲得，比較靈活，還可以通過數據更新。

6 結束語

針對帶平衡約束的矩形布局優(yōu)化問題，本文提出了一個深度強化學習算法DAR， 通過在大量的5～10個矩形的問題集上進行求解訓練，算法可進行有效學習，在20、40、60個矩形的更大規(guī)模的問題集上表現依然很好。與現有算法相比，在求解大型問題時在計算時間和結果質量上都具有優(yōu)勢。通過引入迭代機制后的IDAR算法，給出的結果質量進一步提升。

下一步的工作可從IDAR的迭代機制入手，如應用演化算法的各種搜索策略以降低獲得滿意解的迭代時間。另外，本文的計算框架還可嘗試推廣到其他的非約束的布局問題中，如bin-packing問題等。

參考文獻：

[1]Teng Hongfei， Sun Shoulin， Ge Wenhai， et al. Layout optimization for the dishes installed on a rotating table the packing problem with equilibrium behavioural constraints［J］.Science in China （Series A），1994，37（10）：1272-1280.

［2]何琨，楊辰凱，黃夢龍，等.動作空間帶平衡約束圓形Packing問題的擬物求解算法［J］.軟件學報，2016，27（9）：2218-2229.（He Kun， Yang Chenkai， Huang Menglong， et al. Quasi-physical algorithm based on action space for solving the circles packing problem with equilibrium constraints［J］.Journal of Software，2016，27（9）：2218-2229. ）

［3]Liu Jingfa， Li Jian， Lyu Zhipeng， et al. A quasi-human strategy-based improved basin filling algorithm for the orthogonal rectangular packing problem with mass balance constraint［J］.Computers amp; Industrial Engineering，2017，107（5）：196-210.

［4]王英聰，肖人彬．求解衛(wèi)星艙布局問題的蟻群勞動分工優(yōu)化算法［J］.控制與決策，2021，36（7）：1637-1646.（Wang Yingcong， Xiao Renbin. Ant colony labor division optimization algorithm for satellite module layout design［J］.Control and Decision，2021，36（7）：1637-1646.）

［5]Bello I， Pham H， Le Q V， et al. Neural combinatorial optimization with reinforcement learning［EB/OL］.（2017-01-12）.https：//arxiv.org/pdf/1611.09940.pdf.

［6]Hu Haoyuan， Zhang Xiaodong， Yan Xiaowei， et al. Solving a new 3D bin packing problem with deep reinforcement learning method［EB/OL］.（2017-08-20）.https：//arxiv.org/pdf/1708.05930.pdf.

［7]Nazari M R， Oroojlooy A， Snyder L， et al. Reinforcement learning for solving the vehicle routing problem［C］//Advances in Neural Information Processing Systems. Cambridge， MA： MIT Press， 2018.

［8]Lu Hao， Zhang Xingwen， Yang Shuang. A learning-based iterative method for solving vehicle routing problems［C］ // Proc of International Conference on Learning Representation.2020.

［9]馮恩民，王錫祿，王秀梅，等.帶性能約束布局問題的全局優(yōu)化算法［J］.高校應用數學學報：A輯，1999，14（1）：98-104.（Feng Enmin， Wang Xilu， Wang Xiumei， et al. A global optimization algorithm for layout problems with behavior constraints［J］.Applied Mathematics： A Journal of Chinese Universities，1999，14（1）：98-104.）

［10]翟金剛，馮恩民，李振民，等.帶性能約束布局問題的不干涉遺傳算法［J］.大連理工大學學報，1999，39（3）：352-357.（Zhai Jin-gang， Feng Enmin， Li Zhenmin， et al. .Noninterference genetic algorithm with performance constrained layout problem［J］.Journal of Dalian University of Technology，1999，39（3）：352-357.）

［11]馮恩民，宮召華，劉重陽，等.帶性能約束的衛(wèi)星艙布局問題改進遺傳算法［J］.大連理工大學學報，2005，45（3）：459-463.（Feng Enmin， Gong Zhaohua， Liu Chongyang， et al. Improved GA for artificial satellite module layout problem with performance constraints［J］.Journal of Dalian University of Technology，2005，45（3）：459-463.）

［12]Xu Yichun， Xiao Renbin， Amos M. Particle swarm algorithm for weighted rectangle placement［C］//Proc of the 3rd International Conference on Natural Computation. Washington DC： IEEE Computer Society，2007：728-732.

［13]Xu Yichun， Xiao Renbin， Amos M. Simulated annealing for weighted polygon packing［EB/OL］.（2008-09-29）.https：//arxiv.org/pdf/0809.5005.pdf.

［14]劉景發(fā)，劉思妤.帶靜不平衡約束的矩形裝填問題的啟發(fā)式算法［J］.軟件學報，2018，29（2）：283-298.（Liu Jingfa， Liu Siyu. Heuristic algorithm for the rectangular packing problem with static non-equilibrium constraint［J］.Journal of Software，2018，29（2）：283-298.）

［15]徐義春，董方敏，劉勇，等.帶平衡約束矩形布局優(yōu)化問題的遺傳算法［J］.模式識別與人工智能，2010，23（6）：794-801.（Xu Yichun， Dong Fangmin， Liu Yong， et al. Genetic algorithm for rectangle layout optimization with equilibrium constraints［J］.Pattern Re-cognition and Artificial Intelligence，2010，23（6）：794-801.）

［16]黃振東，肖人彬.求解帶平衡約束矩形布局問題的混合算法［J］.華中科技大學學報：自然科學版，2011，39（3）：96-99.（Huang Zhendong， Xiao Renbin. Hybrid algorithm for the rectangular packing problem with constraints of equilibrium［J］.Journal of Huazhong University of Science amp; Technology： Natural Science，2011，9（3）：96-99.）

［17]季美，肖人彬.基于蟻群算法的帶平衡約束矩形布局問題的啟發(fā)式求解［J］.計算機應用，2010，30（11）：2898-2901，2905.（Ji Mei， Xiao Renbin. Ant colony optimization and heuristic algorithms for rectangle layout optimization problem with equilibrium constraints［J］.Journal of Computer Applications，2010，30（11）：2898-2901，2905.）

［18]Li Ziqiang， Wang Xianfeng， Tan Jiyang， et al. A quasiphysical and dynamic adjustment approach for packing the orthogonal unequal rectangles in a circle with a mass balance： satellite payload packing［J］.Mathematical Problems in Engineering，2014，2014（3）：article ID 657170.

［19]Liu Jingfa，Zhou Ziling，Liu Zhaoxia，et al. Improved Tabu search algorithm for the rectangle packing problem with equilibrium constraints［J］.Journal of Information and Computational Science，2012，9（18）：5831-5839.

［20]劉景發(fā)，張振，薛羽，等.帶靜不平衡約束的正交矩形布局問題的啟發(fā)式模擬退火算法［J］.模式識別與人工智能，2015，28（7）：626-632.（Liu Jingfa， Zhang Zhen， Xue Yu， et al. Heuristic simulated annealing algorithm for orthogonal rectangle packing problem with static non-equilibrium constraints［J］.Pattern Recognition and Artificial Intelligence，2015，28（7）：626-632.）

［21]Dong Shi， Wang Ping， Abbas K. A survey on deep learning and its applications［J］.Computer Science Review，2021，40（1）：100379.

［22]Sutskever I， Vinyals O， Le Q V. Sequence to sequence learning with neural networks［C］//Proc of the 27th International Conference on Neural Information Processing Systems.Cambridge，MA：MIT Press，2014：3104-3112.

［23]Bahdanau D， Cho K H， Bengio Y. Neural machine translation by jointly learning to align and translate［EB/OL］.（2016-05-19）.https：//arxiv.org/pdf/1409.0473.pdf.

［24]Vinyals O， Fortunato M， Jaitly N. Pointer networks［EB/OL］.（2017-01-02）.https：//arxiv.org/pdf/1506.03134v2.pdf.

［25]Sutton R S， Barto A G. Reinforcement learning： an introduction［M］. Cambridge. MA： MIT Press， 2018.

［26]Parisi S， Tangkaratt V， Peters J， et al. TD-regularized actor-critic methods［J］.Machine Learning，2019，108（8-9）：1467-1501.

［27]胡尚民，沈惠璋.基于強化學習的電動車路徑優(yōu)化研究［J］.計算機應用研究，2020，37（11）：3232-3235.（Hu Shangmin， Shen Huizhang. Research on electric vehicle routing problem based on reinforcement learning［J］.Application Research of Computers，2020，37（11）：3232-3235.）

［28]Luong M T， Pham H， Manning C D. Effective approaches to a attention-based neural machine translation［EB/OL］.（2015-09-20）.https：//arxiv.org/pdf/1508.04025.pdf.