羅娜

摘要：NP難度問題一直是計算機科學(xué)研究的一個重要問題，具有很高的理論和實用價值。這篇文章主要研究利用模擬退火算法解決具有NP難度的裝填問題，它的求解目標(biāo)是尋求多個圓在一個矩形內(nèi)的優(yōu)良布局，使得這些圓兩兩互不嵌入地放置。通過將模擬退火算法與梯度法相結(jié)合，并且融入一些啟發(fā)式的格局更新策略，提出了改進的模擬退火算法。計算結(jié)果顯示，該算法對于解決圓形裝填問題具有很高的效率。

關(guān)鍵詞：模擬退火算法；裝填問題；NP難度；梯度法

中圖分類號：TP18 文獻標(biāo)識碼：A 文章編號：1009-3044（2016）06-0181-03

1 概述

裝填問題研究的是一組小物體在大區(qū)域內(nèi)互相不重疊的布局方式，要求盡可能地提高空間或物體的利用率，并達到某些最優(yōu)指標(biāo)[1-3]，從而減少浪費。在物體堆放、運輸以及原材料下料等領(lǐng)域有著廣泛的應(yīng)用，有效地解決這個問題可以增加資源的利用率，從而帶來不可估量的經(jīng)濟效益。由于裝填問題通常是NP難度的問題，所以目前學(xué)術(shù)界沒有算法能保證在有效時間內(nèi)求出其精確解，順著應(yīng)用行業(yè)的迫切要求，出現(xiàn)了很多有效的搜索策略來解決這一問題。

本文在模擬退火算法的基礎(chǔ)上，提出了一個改進的模擬退火算法，它是在模擬退火算法能夠有效地逃離局部最小值陷阱策略的基礎(chǔ)上，又結(jié)合了梯度算法和空白點放置策略，有效地提高了算法的效率。

2 問題的描述

2.1 NP問題和NP完全問題介紹

首先我們來看下NP問題的定義，所謂N也就是Non-Deterministic，即不確定性，P則是多項式算法問題，所以NP就叫做非確定性多項式算法問題，有些多項式問題沒有一套完整的求解公式，只能使用確定性的猜測的方法和驗證的方法來求解，對于這一類求解的問題我們都可以叫它NP問題，如果來求解NP問題，我們一般使用一個合理的算法來對NP問題進行猜測和驗證

如果以上的NP問題可以用一個多項式算法得到這個NP問題的最優(yōu)解，就叫做NP完全問題的解，但是這個難度是很大的，也是目前世界數(shù)學(xué)界的難題。本文研究的是對于NP問題的相對最優(yōu)解，采用改進模擬退火算法來對布局進行優(yōu)化，從而得到優(yōu)質(zhì)的計算結(jié)果。

2.2 裝填問題介紹

裝填問題所探討的是一組小物體放在一個大區(qū)域內(nèi)并且讓它們互相不重疊的布局方案，要求盡可能地提高空間和物體的利用率，并達到某些最優(yōu)指標(biāo)，從而減少浪費。下面來看下本文研究的裝填問題的說明。

給定一個矩形區(qū)域和N個不同規(guī)格的圓，圓形裝填問題就是問能否將這些圓互不重疊地放到矩形容器中，此問題更形式化的描述如下：

將二維笛卡爾坐標(biāo)的原點取在矩形區(qū)域的左下角，如圖1所示：

記矩形容器的長寬分別為L與W，圓i的圓心坐標(biāo)為（xi， yi），半徑為Ri，圓j的圓心坐標(biāo)為（xj，yj） ， 半徑為Rj，問是否存在2n個實數(shù)x1，y1，…，xn，yn滿足以下兩個約束條件：

[Ri≤xi≤L-Ri， Ri≤yi≤W-Ri（xi-xj）2+（yi-yj）2≥Ri+Rj]

如果存在，則給出一組合乎條件的解（x1，y1，…，xn，yn），這里i， j=1，2，…，N， and i≠j。

3 問題的轉(zhuǎn)化

根據(jù)上面的問題描述，我們按照擬物方法[10， 11]，假設(shè)這N個圓為有彈性的光滑的圓形物體，將它們隨機的放入這個矩形容器內(nèi)，若物體間兩兩無擠壓，則得到問題的解，否則根據(jù)彈性力學(xué)，受擠壓的圓間將產(chǎn)生積壓彈性力，并在此力的作用下產(chǎn)生一系列恢復(fù)原本形狀的運動，直到物體間沒有擠壓則得到此問題的解，這樣通過擬物的方法可以轉(zhuǎn)化為一個勢能函數(shù)的優(yōu)化問題，根據(jù)彈性力學(xué)原理就可以得出勢能函數(shù)。以下是勢能函數(shù)的求得過程：

第一種情況，第i個圓和第j個圓相互嵌入時，這時嵌入深度的是它們半徑之和減去圓心的距離；當(dāng)兩圓不嵌入時，則[dij]為0，見圖2所示：

因此圓i與圓j的擠壓深度為：

5 改進的模擬退火算法

5.1 挑圓策略

當(dāng)模擬退火算法陷入局部最小值陷阱后，我們需要挑出一個圓重新放置來使算法跳出陷阱從而繼續(xù)尋求最優(yōu)解，那么選擇挑出哪一個圓將是一個待解決的問題。我們借鑒黃文奇等人的擬人策略來解決這一問題，在熱鬧擁擠的公交車中，受擠壓最甚者總能設(shè)法改變自己的位置，而處境寬松者往往也會讓出一部分空間給予別人。所以當(dāng)陷入局部最小值陷阱時，我們可以挑出受擠壓最嚴重的圓餅，將它重新放置到矩形容器的某個地方去，也可以跳出那個擠壓最寬松的圓放到矩形容器的某個地方去，擠壓的嚴重程度我們可以用圓的勢能與其半徑比來表示，我們可以將挑出勢能半徑比最大的圓的策略稱之為壓力解除策略，將挑出勢能半徑比最小的圓的策略稱之為資源讓與策略。此兩個策略統(tǒng)稱為挑圓策略。

5.2 空白點放置策略

通過上面介紹的挑圓策略可以確定應(yīng)該重新放置的圓，那么將這個圓放置在矩形容器的什么位置就成了新的問題，原來的策略往往是將這個圓隨機的放置在矩形容器內(nèi)的一個位置從而獲得一個新的格局，可是這種方法來尋求全局最優(yōu)解效率是很低的，空白點放置就是將所挑出的圓放入一個空白位置，并且得到多個空白位置，再從這些空白點中選擇一個放入后使系統(tǒng)勢能最小值的空白點來放置。

下面是空白點放置策略描述：

（1） 在矩形容器內(nèi)隨機產(chǎn)生一個點，判斷該點是否是空白點，即要滿足在矩形的內(nèi)部，也要滿足不在其他小圓的內(nèi)部，如果是空白點，則記錄下其位置，然后繼續(xù)尋找空白點，直到找到100個空白點。

（2） 將選擇的圓分別放入選擇出的100個空白點中，分別計算它們的系統(tǒng)勢能。

（3） 選出系統(tǒng)勢能最小的空白點放置圓，即設(shè)置為該圓的坐標(biāo)。

（4） 如果循環(huán)需找500次也沒能找到100個空白點，為了避免陷入死循環(huán)則結(jié)束空白點的搜索。

5.3 局部最優(yōu)判斷策略

上文已經(jīng)多次提到，當(dāng)算法運行時，可能陷入局部最小值而無法自拔，挑圓策略與空白點放置策略用來解決這一問題，但是前提是怎么樣判斷系統(tǒng)已經(jīng)陷入局部最小值，我們知道算法陷入局部最小值時，系統(tǒng)的勢能的變化已經(jīng)非常小了，我們可以用新格局勢能值比上新的格局勢能值與原來格局勢能值的差的絕對值來判斷系統(tǒng)是否處于局部最小值狀態(tài)，如果比值大于10000，我們可以認為處于局部最小值狀態(tài)，然后就使用挑圓策略與空白點放置策略。

5.4 改進的模擬退火算法步驟

改進的模擬退火算法步驟如下：

在矩形容器中隨機生成N個圓的圓心坐標(biāo)，得到初始格局解X=（x1，y1，…，xi，yi，…，xn，yn），設(shè)置初始溫度T為10N（N為小圓數(shù)量），溫度下降系數(shù)k設(shè)置為0.92。

計算所有小圓的勢能半徑比，記下勢能半徑比最大的小圓的序號，記下此時的勢能U（X1）。最后備份當(dāng)前格局X1。

使用空白點放置策略把勢能半徑比最大的圓放入空白點中，從而得到新的格局X。

用梯度法進行計算，令每個圓按其梯度方向進行移動，得到新的格局X2，記下此時的勢能U（X2），如果U（X2） <10-10則接受X2格局，算法成功停機，否則繼續(xù)進行第5步。

判斷是否是局部最優(yōu)解。

如果是局部最優(yōu)解，則使用挑圓策略挑出一個勢能半徑比最小的圓利用空白點放置策略放入空白點中轉(zhuǎn)第4步，如果不是則轉(zhuǎn)（2）。

如果不是局部最優(yōu)解，則使用梯度法前的格局勢能U（X1）與使用梯度法后的格局勢能U（X2）來比較，取它們的差△E=U（X1）-U（X2）；如果勢能有所下降，那么我們接受這個格局，令X1=X2；如果勢能增加了，那么我們以一定的概率exp（-△E）/T）去接受產(chǎn)生的新解，如果沒有接受惡化解則還原第2步驟中備份的格局。

如果在溫度T下系統(tǒng)的勢能沒有達到穩(wěn)定，則轉(zhuǎn)第2步驟，否則轉(zhuǎn)7。

進行模擬退火算法的退溫操作，T=T*k。

如果溫度T<0.01，算法失敗停機。

6 結(jié)論

大規(guī)模組合優(yōu)化問題和NP難度問題是現(xiàn)代計算機科學(xué)的難點問題， 并且這類問題的有效解決將會帶來計算機科學(xué)上的巨大理論突破，同時也會帶來巨大的經(jīng)濟效益，因此，也是現(xiàn)代計算機科學(xué)的熱點問題，本文的圓形Packing問題的研究涉及物理、數(shù)學(xué)、哲學(xué)、計算機科學(xué)、計算智能、優(yōu)化理論等多個學(xué)科領(lǐng)域，并且在布局優(yōu)化和運籌學(xué)等方面有著十分重要的應(yīng)用。預(yù)計在未來的若干年內(nèi)，將帶來巨大的經(jīng)濟實用價值。

參考文獻：

[1] 王大志，汪定偉，閆楊.一類多旅行商問題的計算及仿真分析[J].系統(tǒng)仿真學(xué)報，2009（20）.

[2] 邢文訓(xùn).現(xiàn)代優(yōu)化計算方法[M].2版.北京：清華大學(xué)出版社，2006.

[3] 王萬森.人工智能原理及其應(yīng)用[M].2版 .北京：電子工業(yè)出版社，2007.

[4] 梁艷春.群智能優(yōu)化算法理論與應(yīng)用[M]，北京：科學(xué)出版社，2009.

[5] Ingber L，Rosen B.Genetic algorithms and fast simulated annealing：A comparison.Mathematic Computer Modeling.1992，16（Ⅱ）：87-100

[6] A Lodi，S Martello，M Monaci.Tow-dimensional packing problems：A survey[J].European Journal of Operational Research.2002，141（2）：241-252

[7] J Leung，T Tam，C S Wong，et al.Packing squares into square[J].Journal of Parallel and Distributed Computing.1990，10（3）：271-275

[8] 黃文奇，詹叔浩.求解Packing問題的擬物方法[J].應(yīng)用數(shù)學(xué)學(xué)報，1979，2（2）：176-180.

[9] 康立山，謝云，羅祖華.非數(shù)值并行算法——模擬退火算法[M].北京：科學(xué)出版社，1997.

[10] 康燕 黃文奇.基于禁忌搜索的啟發(fā)式算法求解圓形packing問題[J].計算機研究與發(fā)展學(xué)報，2004，（9）：1555-1558.