改進(jìn)的模擬退火算法及其在裝填問題中的應(yīng)用

羅娜

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

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

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

1 概述

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

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

2 問題的描述

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

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

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

2.2 裝填問題介紹

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

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

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

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

[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個(gè)圓為有彈性的光滑的圓形物體，將它們隨機(jī)的放入這個(gè)矩形容器內(nèi)，若物體間兩兩無擠壓，則得到問題的解，否則根據(jù)彈性力學(xué)，受擠壓的圓間將產(chǎn)生積壓彈性力，并在此力的作用下產(chǎn)生一系列恢復(fù)原本形狀的運(yùn)動(dòng)，直到物體間沒有擠壓則得到此問題的解，這樣通過擬物的方法可以轉(zhuǎn)化為一個(gè)勢(shì)能函數(shù)的優(yōu)化問題，根據(jù)彈性力學(xué)原理就可以得出勢(shì)能函數(shù)。以下是勢(shì)能函數(shù)的求得過程：

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

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

5 改進(jìn)的模擬退火算法

5.1 挑圓策略

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

5.2 空白點(diǎn)放置策略

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

下面是空白點(diǎn)放置策略描述：

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

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

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

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

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

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

5.4 改進(jìn)的模擬退火算法步驟

改進(jìn)的模擬退火算法步驟如下：

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

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

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

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

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

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

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

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

進(jìn)行模擬退火算法的退溫操作，T=T*k。

如果溫度T<0.01，算法失敗停機(jī)。

6 結(jié)論

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

參考文獻(xiàn)：

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

[2] 邢文訓(xùn).現(xiàn)代優(yōu)化計(jì)算方法[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é)報(bào)，1979，2（2）：176-180.

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

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