王英聰 張 領 肖人彬

1.鄭州輕工業(yè)大學電氣信息工程學院，鄭州，4500022.華中科技大學人工智能與自動化學院，武漢，430074

0 引言

工程中存在著大量的布局(Packing)問題，它們一般要求待布物之間、待布物與容器之間互不干涉，并盡量提高容器利用率[1-2]。作為布局問題的一個典型特例，圓形Packing問題是工業(yè)生產(chǎn)中常見的問題，在衛(wèi)星艙布局[3]、卷材排樣[4]、電力電纜設計[5]等領域有著廣泛的應用。作為一個經(jīng)典的NP難問題(non-deterministic polynomial-time hard problem)，很難在確定的多項式內(nèi)得到圓形Packing問題的最優(yōu)解,因此，國內(nèi)外研究者普遍采用啟發(fā)式方法進行求解，這些方法大致可以分為構造法和優(yōu)化法兩類。

構造法首先對圓形物體排序，然后根據(jù)定位規(guī)則將圓形物體逐個置入容器中適當?shù)奈恢?，直到所有圓形物體均被放入為止。HUANG等[6]受圍棋古諺“金角銀邊草肚皮”的啟發(fā)，提出了一種基于最大穴度定位規(guī)則的占角算法；LYU等[7]采用PERM (Pruned-Enriched-Rosenbluth method)策略確定放置順序，采用最大穴度定位規(guī)則確定放置位置；黎自強等[8]利用蟻群算法優(yōu)化放置順序，利用逆時針外圍排列定位規(guī)則確定放置位置；AL-MUDAHKA等[9]利用禁忌搜索確定放置順序，利用分區(qū)技術確定放置位置；FEKETE等[10]對容器進行條帶化處理，將圓形物體放置到與矩形塊四邊相切的位置，提出一種結構化條帶定位算法；LINTZMAYER等[11]將容器網(wǎng)格化，把圓形物體逐個置入網(wǎng)格并保持相切，提出了有界空間算法和無界空間算法。

與構造法不同，優(yōu)化法首先將所有圓形物體強行放入容器，然后通過連續(xù)優(yōu)化和格局變換的方式不斷地調(diào)整圓形物體在容器內(nèi)的位置，直到所有圓形物體都滿足約束條件為止。黃文奇等[12]采用基于交換、跳躍的鄰域策略和禁忌策略進行格局變換；何琨等[13]在彈力與拉力模型的基礎上，采用基于動作空間的擬物算法優(yōu)化圓形物體的位置；ZENG等[14]設計了交換和插入兩種鄰域結構，并結合迭代禁忌搜索進行格局變換；張維等[15]直接利用遺傳模擬退火算法優(yōu)化圓形物體的位置；王英聰?shù)萚16]采用基于蟻群勞動分工的空間分配策略進行格局變換；LPEZ等[17]綜合考慮了問題的笛卡兒坐標系模型和極坐標系模型，采用非線性規(guī)劃軟件SNOPT優(yōu)化圓形物體的位置。

上述方法主要針對不等圓Packing問題提出，若將其直接用于等圓Packing問題，求解效果往往不理想。比如，構造法中常用的最大穴度定位規(guī)則在等圓問題上有一定的局限性，且對放置順序的優(yōu)化是無效的，而優(yōu)化法中常用的交換鄰域策略對等圓問題也無效。近年來，一些學者對等圓Packing問題進行了深入研究。CHEN等[18]將最大貼邊度與最大穴度相結合對圓形物體進行定位；黃文奇等[19]利用引力、斥力與彈力的共同作用調(diào)整圓形物體的位置；HE等[20]利用擬物擬人策略完成連續(xù)優(yōu)化和格局變換，并結合張弛策略完成跳坑搜索。

本文針對等圓Packing問題提出一種柔性位置選擇算法，該算法屬于構造法范疇。由于等圓Packing問題中所有圓形物體的半徑相同，所以此時構造法不涉及定序過程。由于圓形物體在容器內(nèi)的可行位置通常不止一個，定位過程的本質(zhì)就是從多個可行位置中選擇一個恰當?shù)奈恢梅胖脠A形物體，因此，當采用構造法求解等圓Packing問題時，所面臨的是一個位置選擇問題。在蟻群等社會性昆蟲中，個體經(jīng)常會面臨對族群任務的選擇，表現(xiàn)為勞動分工[21]。勞動分工的智能性體現(xiàn)在個體無需全局信息和中心控制，僅通過局部相互作用就能選擇出符合族群需求的恰當任務。本文借鑒群智能勞動分工的任務選擇實現(xiàn)等圓Packing問題的位置選擇，提出一種柔性位置選擇算法。對國內(nèi)外55個公開算例的計算結果表明，本文算法是求解等圓Packing問題的一種有效算法。

1 選擇視角下的等圓Packing問題分析

1.1 問題描述

等圓Packing問題可描述為[18]：給定一個半徑R盡可能小的圓形容器，要求將n個半徑為1的單位圓互不干涉地放置在這個圓形容器內(nèi)。假設圓形容器c0的圓心固定在原點(0,0)，將第i個單位圓ci的圓心坐標記為(xi,yi)，則等圓Packing問題就轉(zhuǎn)化為尋找一種放置(布局)方案X=(x1,y1,x2,y2,…,xn,yn)，使得

(1)

(2)

(3)

i,j=1,2,…,ni≠j

1.2 選擇特性分析

構造法在求解Packing問題時將待布物逐個置入容器中恰當?shù)奈恢?。這一過程包含定序和定位兩部分，其中定序就是確定待布物的放置順序，定位就是確定待布物在容器內(nèi)的放置位置。由于等圓Packing問題中所有圓形物體大小相同，故此時構造法的求解過程特指定位過程。由于圓形物體在容器內(nèi)的放置位置通常不止一個，因而定位過程可以看成是一個位置選擇過程。在構造法的求解框架下，每當新的圓形物體置入容器時就會形成新的格局。下面將結合格局和可行位置的概念，進一步分析等圓Packing問題在定位過程中的選擇特性。

定義1格局假設某一時刻圓形容器內(nèi)已經(jīng)互不干涉地放置了m(m≥1)個圓形物體，容器外還有n-m個圓形物體等待放置，稱這種狀態(tài)為一個格局Cm。初始格局時，容器內(nèi)只有一個圓形物體且與容器邊緣相切。當所有圓形物體都已放入容器中時，此時的終止格局為合法格局。當容器外的圓形物體無法再放入時，此時的終止格局稱為非法格局。

圖1 可行位置示意圖Fig.1 The sketch of the feasible positions

(a)c5的可行位置 (b)選擇

(c)選擇選擇圖2 位置選擇特性Fig.2 The position selection characteristics

結合上述分析，等圓Packing問題的位置選擇特性可以歸納如下：①在同一格局下，圓形物體在容器內(nèi)的可行位置通常不止一個；②選擇不同的可行位置，將形成不同的格局；③格局的差異體現(xiàn)在已布局空間和未布局空間兩個方面；④可行位置對已布局空間的影響體現(xiàn)在緊湊性上，可通過圓形物體在可行位置處與已布局圓形物體之間的距離關系來描述；⑤可行位置對未布局空間的影響體現(xiàn)在完整性上，可通過圓形物體在可行位置處所形成的新可行位置的數(shù)量和質(zhì)量來描述；⑥不同格局下的可行位置之間有重合，也就是說有一部分可行位置是固定的。

2 基于勞動分工的位置選擇算法

2.1 相似性分析

在蟻群等社會性昆蟲中，族群為了維持生存需要完成各種各樣的任務，比如尋找食物、哺育幼蟲、維護巢穴、抵御外敵等。勞動分工從宏觀上表現(xiàn)為不同的個體執(zhí)行不同的任務，是個體在局部簡單規(guī)則作用下涌現(xiàn)產(chǎn)生的一種智能行為[21]。社會性昆蟲勞動分工的智能性表現(xiàn)為：在無需全局信息和中心控制的情況下，執(zhí)行不同任務的個體的比率會隨環(huán)境自適應調(diào)整，而且該比率下的分工恰好滿足族群對各項任務的需求。也就是說，在群智能勞動分工的作用下，個體僅通過局部作用就能選擇出符合族群需求的恰當任務，因此，群智能勞動分工可以看成是昆蟲個體對族群任務的選擇。

由1.2節(jié)的分析可知，等圓Packing問題在構造法求解框架下可轉(zhuǎn)化成一個位置選擇問題。圖3描述了位置選擇與任務選擇之間的相似性。對圓形物體而言，定位過程就是從多個可行位置中選擇一個恰當?shù)奈恢?。對昆蟲個體而言，勞動分工就是從族群任務中選擇一個恰當?shù)娜蝿?。如果將圓形物體看成昆蟲個體，可行位置看成族群任務，那么利用任務選擇就可以實現(xiàn)位置選擇。由于構造法是在逐步完善Packing解，在每一階段的定位過程中只能利用當前格局的局部信息，而當前格局下的最優(yōu)位置不一定是符合全局的最佳位置，這也是定位過程的難點所在。在群智能勞動分工作用下，昆蟲個體僅利用局部信息就能選擇出符合全局的恰當任務。群智能勞動分工的這一特點恰好滿足構造法對定位過程的要求，這為本文算法的提出提供了理論依據(jù)。

圖3 位置選擇與任務選擇之間的對比Fig.3 The comparison between position selection and task selection

2.2 勞動分工機制

刺激-響應是群智能勞動分工的一種內(nèi)部機制，可簡要描述如下[21]：族群中的每個任務都對應著一個刺激，刺激強度描述了任務的緊急程度；昆蟲個體對應每個任務都存在一個閾值，閾值大小反映了昆蟲個體執(zhí)行任務的傾向性；當任務的刺激強度高于昆蟲個體的響應閾值時，其選擇任務的概率高，反之，選擇任務的概率低。BONABEAU等[22]給出了刺激-響應機制的一種量化形式：令S表示任務的刺激，θ表示昆蟲個體的閾值，則昆蟲個體選擇任務的概率P=Sq/(Sq+θq)，其中q為控制響應函數(shù)曲線形狀的常量，一般取2。THERAULAZ等[23]進一步指出昆蟲個體還具有學習(獎勵)和遺忘(懲罰)能力：當昆蟲個體執(zhí)行(或成功執(zhí)行)某項任務時，對應的閾值在學習(獎勵)的作用下會減??；當昆蟲個體未執(zhí)行(或未成功執(zhí)行)某項任務時，對應的閾值在遺忘(懲罰)的作用下會增大。通過刺激和閾值的相互作用，以及閾值的自適應調(diào)整，昆蟲個體能夠靈活地選擇族群任務。

2.3 柔性位置選擇算法

本節(jié)利用群智能勞動分工的任務選擇實現(xiàn)等圓Packing問題的位置選擇，提出一種柔性位置選擇算法(flexible position selection algorithm, FPSA)。根據(jù)群智能勞動分工機制，F(xiàn)PSA主要包含刺激和閾值兩部分。結合等圓Packing問題的位置選擇特性，刺激和閾值的設計可從格局定義下的已布局空間和未布局空間兩個方面來考慮。

2.3.1刺激

圓形物體選擇不同的位置將形成不同的格局，格局的差異可從未布局空間來描述。未布局空間內(nèi)可放置的圓形物體越多，說明未布局空間越完整。放置圓形物體時，一般會優(yōu)先選擇使未布局空間更加完整(即潛在位置多)的位置。根據(jù)刺激-響應勞動分工機制，刺激越大，個體選擇任務的概率越大，因此，可將未布局空間的完整度看作圓形物體選擇位置時的刺激。

假設格局Cm下共有u個可行位置，將圓形物體試放到第k個位置上形成新格局Cm+1。若在新格局下有nk個可行位置，且其中有pk對可行位置之間互相重疊，則與第k個位置對應的未布局空間的完整度定義如下：

Ik=nk-0.1pk

(4)

(5)

2.3.2閾值

圓形物體選擇不同的位置將形成不同的格局，格局的差異可從已布局空間來描述。已布局空間中圓形物體之間的距離越短，說明已布局空間越緊湊。放置圓形物體時，一般會優(yōu)先考慮使已布局空間更加緊湊(即彼此距離短)的位置。根據(jù)刺激-響應勞動分工機制，閾值越小，個體選擇任務的概率越大。由此，可將已布局空間的緊密度看作圓形物體選擇位置時的閾值。

假設格局Cm下共有u個可行位置，第k個位置由已布局圓形物體cv和cw(其中一個可能是圓形容器c0)計算得到。將圓形物體試放到第k個位置上，計算它與其他圓形物體cj(排除cv和cw)之間的距離dj，則與第k個位置對應的已布局空間的緊密度定義如下：

Tk=mindjcj∈Cm∪{c0},cj≠cv,cw

(6)

這里對緊密度的計算與文獻[6]中的穴度相似。最后，對u個可行位置的緊密度作歸一化處理，將圓形物體選擇第k個位置時的閾值定義為

(7)

在群智能勞動分工中，閾值還會隨著個體成功(失敗)執(zhí)行任務而減小(增大)，使得社會性昆蟲的任務選擇具有很強的適應性。由可行位置的定義及等圓Packing問題的位置選擇特性可知，圓形物體在容器內(nèi)的可行位置是離散的、固定的。據(jù)此，對閾值設計如下自適應調(diào)整策略：分別用位置集合Lb和Lw存儲最優(yōu)布局和最差布局中所有圓形物體的放置位置，若第k個位置(xk,yk)出現(xiàn)在最優(yōu)位置集合Lb中，則減小對應的閾值θk，以提高其選擇概率；若第k個位置(xk,yk)出現(xiàn)在最差位置集合Lw中，則增大對應的閾值θk，以降低其選擇概率；否則閾值θk保持不變。具體更新公式如下：

(8)

式中，δ、μ分別為獎勵和懲罰系數(shù)，δ<1，μ>1。

2.3.3選擇概率

根據(jù)刺激-響應機制，圓形物體選擇第k個位置的概率

(9)

最終，圓形物體按照概率大小以輪盤賭的方式確定放置位置。

2.3.4算法流程

綜合以上內(nèi)容，本文柔性位置選擇算法的流程圖見圖4，具體步驟如下：

(1)初始化參數(shù)，包括測試算例的圓形物體個數(shù)n、容器半徑R、閾值獎勵系數(shù)δ、閾值懲罰系數(shù)μ和終止運行時間t。

(2)將容器的圓心置入原點(0,0)，首個圓形物體置入容器底部位置(0,1-R)與容器相切，形成初始格局。

(3)計算當前格局下的可行位置，若可行位置個數(shù)為零則轉(zhuǎn)步驟(7)。

(4)根據(jù)式(4)和式(6)計算與每個可行位置所對應的未布局空間的完整度和已布局空間的緊密度，根據(jù)式(5)和式(7)計算圓形物體選擇每個可行位置時的刺激和閾值，根據(jù)式(8)自適應調(diào)整各個閾值。

(5)根據(jù)式(9)計算各可行位置的選擇概率，并確定圓形物體的最終放置位置。

(6)更新當前格局，若所有圓形物體都置入容器則成功退出，否則轉(zhuǎn)步驟(3)。

(7)本次迭代結束，將所得布局結果與當前最優(yōu)布局和最差布局進行比較，更新位置集合Lb和Lw。

(8)判斷算法是否達到終止條件，是則失敗退出，否則轉(zhuǎn)步驟(2)進行下一次迭代。

圖4 FPSA流程圖Fig.4 Flow diagram of FPSA

3 實驗與分析

本文采用Java實現(xiàn)FPSA算法，并在主頻2.4 GHz、內(nèi)存4 GB的計算機上進行三組實驗。第一組實驗旨在設置FPSA算法的參數(shù)值，第二組實驗的目的是評價FPSA算法的性能，第三組實驗則是為了驗證刺激-響應選擇機制的優(yōu)越性。本節(jié)采用廣泛使用的Benchmark算例進行實驗[18,20]。

3.1 參數(shù)設置

選取Benchmark算例中n分別取值50、60、70、80、90的算例進行實驗，容器半徑R設置為當前已知最小值，最長計算時間t設置為3600 s。這里主要討論閾值獎勵系數(shù)δ和閾值懲罰系數(shù)μ的取值對布局效率d的影響(布局效率采用置入容器內(nèi)所有圓形物體面積之和與容器面積的比值來度量)，從而確定參數(shù)的取值。具體方法參照文獻[24]中的對比實驗取值法，即固定算法中的其他參數(shù)，對某一參數(shù)隨機取值，通過觀察平均布局效率確定其較優(yōu)取值。實驗中每個算例獨立運行5次。

由閾值的定義可知，δ<1，μ>1。實驗發(fā)現(xiàn)，隨著δ的取值從1開始減小，布局效率大致呈先增大后減小的變化趨勢。這是因為：當δ取值較大時，對閾值的獎勵程度較小，此時不能有效利用前期搜索所得的一些有價值的位置信息；當δ取值較小時，對閾值的獎勵程度較大，此時會過度優(yōu)先選擇前期發(fā)現(xiàn)的較好位置，導致搜索容易陷入局部最優(yōu)。隨著μ的取值從1開始增大，布局效率大致呈先增大后減小的變化趨勢。這是因為：當μ取值較小時，對閾值的懲罰力度較小，此時會無視一些較差的位置，從而降低搜索效率；當μ取值較大時，對閾值的懲罰力度較大，此時會過度摒棄一些較差的位置；當μ取值恰當時，可以一定程度地接收一些較差的位置，從而增大跳出局部最優(yōu)解的機會。

考慮篇幅，選取δ和μ的10種組合取值來描述它們對布局效率的影響，從圖5中也能基本觀察到上述變化趨勢。由圖5還可以看出，(δ,μ)的取值對布局效率有較大的影響。隨著(δ,μ)取值的變化，五個算例的平均布局效率約從72%變化到77%。其中，參數(shù)取值為(0.8,1.2)時的布局效率較高。獎勵系數(shù)δ的意義在于提高迄今為止最優(yōu)布局中可行位置的選擇概率，懲罰系數(shù)μ的意義在于降低迄今為止最差布局中可行位置的選擇概率。綜合來看，當獎勵和懲罰的力度較大時，算法搜索的多樣性減弱，導致布局結果易于陷入局部最優(yōu)；當獎勵和懲罰的力度較小時，算法搜索不能充分利用之前的有效信息，導致算法的收斂速度降低。

圖5 不同(δ,μ)取值下的平均布局效率Fig.5 Average layout efficiencies against different values of(δ,μ)

3.2 計算結果

為了充分測試FPSA的性能，選取目前已知的最新算法貪婪啟發(fā)式算法(greedy heuristic algorithm,GHA)[18]和擬物擬人算法(quasi-physical quasi-human algorithm,QPQHA)[20]進行對比實驗。實驗中容器半徑R設置為當前已知最小值，最長計算時間t設置為4 h，(δ,μ)設置為(0.8,1.2)。對于每個算例，獨立運行FPSA 10次，記錄其中的最優(yōu)布局和對應的平均計算時間。

表1給出了本文FPSA算法與GHA算法的結果比較，二者都屬于構造法。FPSA算法采用基于緊密度和完整度的定位規(guī)則，GHA算法采用基于穴度和貼邊度的定位規(guī)則。其中，緊密度與穴度的定義相似，完整度和貼邊度都是對未布局空間的一種度量(完整度主要考慮潛在可行位置的個數(shù)，貼邊度只計算與容器邊緣的距離)。由表1可以看出，對于不同n取值的19個測試算例，F(xiàn)PSA算法在5個算例上的計算結果與GHA算法持平，在剩余14個算例上找到了更好的布局。在改進的14個算例上，F(xiàn)PSA算法的布局效率平均提高了0.66%，其中在算例n=100上的布局效率提高最大，為1.86%，在算例n=63上的布局效率提高最小，為0.16%。GHA算法所用機器的CPU主頻為3.6 GHz(高于FPSA算法運行環(huán)境的CPU頻率)，內(nèi)存為4 GB，用C++語言編程實現(xiàn)。由于算法運行的硬件環(huán)境和實現(xiàn)語言不同，故一般不直接比較計算時間，但是由表1可以看出，F(xiàn)PSA算法和GHA算法的計算時間在同一數(shù)量級上。與GHA算法相比，F(xiàn)PSA算法在整體上取得了更好的求解效果。

表1 FPSA與GHA的計算結果比較

表2給出了FPSA算法與QPQHA算法的結果比較。QPQHA算法屬于優(yōu)化法，是目前已知的最優(yōu)算法。QPQHA算法通過擬物策略，將n個圓形物體的布局求解轉(zhuǎn)化為2n維的連續(xù)函數(shù)優(yōu)化問題，并采用高效的擬牛頓法進行求解， 布局效果良好。對于這51個測試算例，F(xiàn)PSA算法在49個算例上的計算結果與QPQHA算法持平，在剩余2個算例上找到了更好的布局。QPQHA算法用C++語言編程實現(xiàn)，在8核8 GB的阿里云平臺運行。QPQHA算法運行的硬件環(huán)境優(yōu)于FPSA算法，雖然不直接比較計算時間，但與QPQHA算法相比，F(xiàn)PSA算法的計算時間在可接受的范圍內(nèi)。從問題求解的角度來看，F(xiàn)PSA算法充分考慮了等圓Packing問題的特點，QPQHA算法則將等圓Packing問題泛化為數(shù)值優(yōu)化問題。從算法框架來看，F(xiàn)PSA算法和QPQHA算法是兩種完全不同的求解模式。FPSA算法在整體上表現(xiàn)出了與QPQHA算法相當?shù)那蠼庑Ч?。圖6給出了FPSA算法在算例n=82和n=100上的最優(yōu)布局。

3.3 分析討論

FPSA算法設計了完整度和緊密度兩個位置評價標準，并通過刺激-響應機制確定圓形物體的放置位置。為了進一步測試刺激-響應選擇(stimulus-response-selection, SRS)的優(yōu)越性，設計如下三種選擇方式進行對比實驗：隨機選擇(random-selection, RS)、最小緊密度選擇(minimum-tightness-selection, MTS)和最大完整度選擇(maximum-integrity-selection, MIS)，其中RS指從可行位置中隨機選擇放置位置；MTS指選擇具有最小緊密度的可行位置，若這樣的位置有多個，則從中隨機選擇一個；MIS指選擇具有最大完整度的可行位置，若這樣的位置有多個，則從中隨機選擇一個。

隨機選取Benchmark算例中n為54,67,88,95的算例進行對比實驗，參數(shù)設置與上節(jié)相同。對于每個算例，四種選擇方式獨立運行10次的布局效率分布情況如圖7所示(采用MATLAB R2012a繪制)。由圖7可以看出，SRS的求解效率最高，MTS與MIS的求解效率次之，RS的求解效率最低。在社會性昆蟲中，個體通過刺激-響應機制就能選擇出符合族群需求的恰當任務，而且個體的任務選擇還會隨著環(huán)境自適應變化，也就是說，SRS是一種柔性選擇方式，能夠適應格局/布局環(huán)境的變化，在不同算例下都取得了較好的結果。MTS和MIS屬于貪婪選擇，只選擇當前格局下的最優(yōu)位置，導致搜索容易陷入局部最優(yōu)。RS無差別地選擇放置位置，具有很大的盲目性，導致搜索結果差且不穩(wěn)定。

表2 FPSA與QPQHA的計算結果比較

(a)n=82 (b)n=100圖6 FPSA最優(yōu)布局方案Fig.6 The best layouts found by FPSA

(a)n=54

(b)n=67

(c)n=88

(d)n=95圖7 四種選擇方式求解不同算例的布局效率分布情況Fig.7 The density of different instances solved by four selection methods

4 結論

針對等圓Packing問題，構造法將圓形物體逐個置入容器，這一過程本質(zhì)上就是從眾多可行位置中確定圓形物體的放置位置。由于圓形物體大小相同，構造過程不涉及圓形物體放置順序的確定，因此，等圓Packing問題就轉(zhuǎn)化為位置選擇問題。借鑒任務選擇實現(xiàn)位置選擇的思路，本文提出一種柔性位置選擇算法(FPSA)。FPSA以刺激-響應的方式實現(xiàn)位置選擇，在55個代表性算例上的計算結果表明了FPSA的有效性，同時與隨機選擇和貪婪選擇的對比結果驗證了刺激-響應選擇方式的優(yōu)越性。目前已知的群智能勞動分工主要有兩種模式：一種是個體與環(huán)境交互的勞動分工，其內(nèi)部機制以刺激-響應為典型代表；一種是個體與個體交互的勞動分工，其內(nèi)部機制以激發(fā)-抑制為典型代表。下一步將研究激發(fā)-抑制機制在圓形Packing問題上的應用。