王英聰，張 領(lǐng)，肖人彬

(1.鄭州輕工業(yè)大學(xué) 電氣信息工程學(xué)院，河南 鄭州 450002；2.華中科技大學(xué) 人工智能與自動(dòng)化學(xué)院，湖北 武漢 430074)

0 引言

圓形布局 (circle packing) 問題研究如何將一組半徑任意給定的圓形物體互不重疊地放入一個(gè)半徑盡可能小的圓形容器內(nèi)，從而使得容器的空間利用率盡可能高[1]。圓形布局問題具有很強(qiáng)的工程應(yīng)用背景。例如，在電纜行業(yè)中，需要將成束的電線聚集成一根電纜，電纜直徑越小，需要的絕緣材料越少。在石油產(chǎn)業(yè)中，需要在運(yùn)輸管道中布置柴油、汽油等不同類型的輸油管，管徑越小，成本越低。此外，圓形布局問題在板材加工、設(shè)備布局、航空航天、輪船運(yùn)輸?shù)阮I(lǐng)域也有著廣泛的應(yīng)用[2-4]。與傳統(tǒng)的裝箱(bin packing)問題主要研究矩形物體和矩形容器不同，圓形布局問題主要研究圓形物體和圓形容器。傳統(tǒng)的bin packing問題的求解方法以定序定位法為主，圓形布局問題的求解方法主要分為全裝填法和定序定位法，且兩者算法框架截然不同。作為一個(gè)經(jīng)典的NP難度問題，圓形布局問題的難點(diǎn)在于如何從一些新的研究視角提出高效的求解方法。

(1)全裝填法用容器內(nèi)的物理格局描述布局解，并通過某些策略在容器內(nèi)移動(dòng)圓形物體，其搜索的是整個(gè)布局。具體的，全裝填法首先將所有圓形物體強(qiáng)行放入容器(不考慮約束條件)，然后不斷調(diào)整各圓形物體的位置，直到所有圓形物體都滿足約束條件，進(jìn)而找到布局解。全裝填法綜合考慮了圓形布局問題的連續(xù)特征和組合特征，主要包含連續(xù)優(yōu)化和格局變換兩個(gè)階段。對(duì)連續(xù)優(yōu)化和格局變換的不同設(shè)計(jì)可形成不同的求解方法，比如文獻(xiàn)[4]通過刺激—響應(yīng)機(jī)制執(zhí)行固定、平移、交換、跳躍等占位動(dòng)作完成格局變換，通過擬物法進(jìn)行連續(xù)優(yōu)化。文獻(xiàn)[5]采用鄰域搜索過程生成新格局，采用擬物方法進(jìn)行連續(xù)優(yōu)化。文獻(xiàn)[6]直接利用人工蜂群算法優(yōu)化圓形物體的位置，這一過程同時(shí)包含格局變換和連續(xù)優(yōu)化。文獻(xiàn)[7]采用啟發(fā)式格局更新策略產(chǎn)生新格局，利用基于自適應(yīng)步長的梯度法進(jìn)行連續(xù)優(yōu)化，并結(jié)合模擬退火準(zhǔn)則接收新格局。文獻(xiàn)[8-9]采用基于痛苦度的格局更新策略和基于勢能曲面變平法的格局接收準(zhǔn)則，在連續(xù)優(yōu)化方面則分別使用了稀疏非線性優(yōu)化器(Sparse Nonlinear Optimizer，SNOPT)和梯度法。文獻(xiàn)[10-11]在格局變換方面采用基于禁忌搜索的鄰域結(jié)構(gòu)，在連續(xù)優(yōu)化方面采用擬牛頓法(LBFGS)。全裝填法允許圓形物體之間、圓形物體與容器之間存在重疊，其將問題解空間變大，導(dǎo)致其中包含很多不可行的布局解。此外，全裝填法中圓形物體的合法位置需要通過連續(xù)優(yōu)化才能得到，計(jì)算時(shí)間較長。

(2)定序定位法通過放置規(guī)則構(gòu)造布局解，并用圓形物體之間的放置序列描述布局解，其搜索的是放置序列。具體的，定序定位法首先對(duì)圓形物體排序，然后按照此順序，根據(jù)放置規(guī)則逐個(gè)確定圓形物體的位置，當(dāng)最后一個(gè)圓形物體的位置確定時(shí)就得到一個(gè)布局解。定序定位法主要考慮了布局問題的組合特征，包括確定放置順序和放置位置兩部分。對(duì)放置序列的優(yōu)化和放置規(guī)則的設(shè)計(jì)可形成不同的求解方法，如文獻(xiàn)[12]通過遍歷法搜索放置順序，采用最大穴度規(guī)則確定放置位置。文獻(xiàn)[13]利用樹搜索進(jìn)行定序，基于占角動(dòng)作進(jìn)行定位。文獻(xiàn)[14-15]分別采用相切定位原則和外圍逆時(shí)針排列定位原則，并采用蟻群算法搜索放置順序。文獻(xiàn)[16-17]在最大穴度定位規(guī)則的基礎(chǔ)上采用集束搜索算法搜索放置順序。文獻(xiàn)[18]采用遍歷法搜索放置順序，通過局部最優(yōu)位置進(jìn)行定位。文獻(xiàn)[19]采用禁忌搜索確定放置順序，通過分割策略確定放置位置。定序定位法通過放置規(guī)則將問題解空間縮小為離散解集，從解空間移除的部分解集中可能包含全局最優(yōu)解和一些較好的局部最優(yōu)解。此外，定序定位法中圓形物體的合法位置可利用放置規(guī)則直接得到，計(jì)算時(shí)間很短。

定序定位法中的定序就是對(duì)圓形物體排序，這是一個(gè)典型的組合優(yōu)化問題，可以采用很多啟發(fā)式方法(如蟻群算法、模擬退火算法、遺傳算法)進(jìn)行求解。定序定位法中的定位就是確定圓形物體在容器內(nèi)的擺放位置，而這樣的位置通常不止一個(gè)。定位就是從多個(gè)可行位置中選擇一個(gè)恰當(dāng)?shù)奈恢梅胖脠A形物體，因而定位可以看作是一個(gè)位置選擇問題。定位規(guī)則的設(shè)計(jì)既要滿足布局的約束條件，又要蘊(yùn)含目標(biāo)函數(shù)的優(yōu)化信息，是定序定位法的關(guān)鍵所在。同時(shí)，由于定序定位法是在逐步構(gòu)造布局解，每個(gè)階段位置的選擇只能依據(jù)當(dāng)前的布局信息，而當(dāng)前布局下的最優(yōu)位置不一定是符合最終布局的最佳位置。因此，如何根據(jù)局部信息選擇恰當(dāng)?shù)姆胖梦恢檬嵌ㄎ灰?guī)則的設(shè)計(jì)難點(diǎn)。

蟻群勞動(dòng)分工是一種典型的群智能行為，經(jīng)常被認(rèn)為是蟻群生態(tài)成功的首要原因[20]。在蟻群中，族群需要完成覓食、哺育、防御等任務(wù)。螞蟻在無中心控制和缺乏全局信息的情況下，僅通過局部信息的相互作用就能選擇出符合族群需求的恰當(dāng)任務(wù)，這種現(xiàn)象叫做勞動(dòng)分工[21]。在蟻群勞動(dòng)分工中，螞蟻對(duì)任務(wù)的選擇還能夠隨著環(huán)境變化進(jìn)行自適應(yīng)調(diào)整。圓形布局的定位過程可以看作是圓形物體對(duì)放置位置的選擇，而蟻群勞動(dòng)分工可以看作是螞蟻對(duì)族群任務(wù)的選擇。作為選擇問題，蟻群勞動(dòng)分工對(duì)圓形布局的定位過程具有啟發(fā)意義。更重要的是，蟻群勞動(dòng)分工的特點(diǎn)恰好滿足圓形布局對(duì)定位規(guī)則的設(shè)計(jì)要求。本文借鑒蟻群勞動(dòng)分工的任務(wù)選擇實(shí)現(xiàn)圓形布局定位過程中的位置選擇，提出一種蟻群勞動(dòng)分工算法。對(duì)于圓形物體的放置順序，本文采用經(jīng)典的蟻群優(yōu)化算法進(jìn)行求解。最后，對(duì)國內(nèi)外公開的24個(gè)代表性算例進(jìn)行了計(jì)算。實(shí)驗(yàn)結(jié)果表明，本文算法是求解圓形布局問題的一種快速而有效的算法。

1 選擇視角下的圓形布局問題

1.1 問題描述

圓形布局問題的一般描述如下：給定n個(gè)半徑分別為Ri(i=1,2,…,n)的圓形物體，將這些圓形物體互不重疊地放入一個(gè)半徑R盡可能小的圓形容器內(nèi)。如圖1所示，如果將圓形容器的圓心固定在原點(diǎn)(0, 0)，將第i個(gè)圓形物體ci的坐標(biāo)記為(xi,yi)，則圓形布局問題就轉(zhuǎn)換為尋找一個(gè)布局方案X=(x1,y1,x2,y2,…,xn,yn)，使得

(1)

(2)

(3)

其中:目標(biāo)式(1)是使放置n個(gè)圓形物體的圓形容器半徑R(即所有圓形物體的外包絡(luò)圓半徑)盡可能小，約束條件式(2)要求任意兩個(gè)圓形物體之間互不重疊，約束條件式(3)要求每個(gè)圓形物體均處于容器范圍內(nèi)。

1.2 選擇特性分析

定序定位法在求解圓形布局問題時(shí)，首先將圓形物體排序，然后將排序后的圓形物體逐個(gè)放入容器中以獲得布局解。定序定位法本質(zhì)上是在確定圓形物體的放置順序和放置位置，其中放置順序的確定是一個(gè)典型的組合優(yōu)化問題。對(duì)于組合優(yōu)化問題，目前已有很多較為成熟的求解方法[22]。圓形物體在容器內(nèi)的放置位置通常不止一個(gè)，放置位置的確定就是從多個(gè)位置中選擇一個(gè)恰當(dāng)?shù)奈恢?。在定序定位方法范疇下，?dāng)放置順序確定以后，圓形布局問題就轉(zhuǎn)化為圓形物體的位置選擇問題。由于定序定位法是在逐步構(gòu)造布局解，每當(dāng)新的圓形物體放入容器時(shí)就會(huì)形成新的布局。下面結(jié)合格局和可行位置的概念來進(jìn)一步分析圓形布局問題的選擇特性。

定義1格局。假定在圓形容器內(nèi)已經(jīng)互不重疊地置入了k(k≥0)個(gè)圓形物體，將容器和這k個(gè)圓形物體的位置集合稱為一個(gè)格局Ck。將容器的圓心置入原點(diǎn)，首個(gè)圓形物體置入容器邊緣并與容器相切形成初始格局C1。當(dāng)置入容器內(nèi)的圓形物體個(gè)數(shù)為n時(shí)，稱其為合法格局；反之，若置入容器內(nèi)的圓形物體的個(gè)數(shù)小于n，且容器外的待置圓形物體不能合法地置入容器時(shí)(即不與已布局圓形物體重疊且不超出容器范圍)，稱其為非法格局。

定義2可行位置。用圓形物體的圓心坐標(biāo)描述其位置，同時(shí)將容器也看作一個(gè)已布局的“圓形物體”。對(duì)于格局Ck，若將待置圓形物體cj放入容器后，使其與Ck中的任一圓形物體均不重疊且至少與兩個(gè)圓形物體相切，就將此時(shí)圓形物體cj的圓心坐標(biāo)稱為其在格局Ck下的可行位置。

具體的，待置圓形物體cj與已布局圓形物體cp、cq同時(shí)相切的位置計(jì)算表達(dá)式為：

其中：(xj,yj)、(xp,yp)和(xq,yq)分別為圓形物體cj、cp和cq的圓心坐標(biāo)，Rj、Rp和Rq分別為圓形物體cj、cp和cq的半徑。一般情況下，由方程組(4)可計(jì)算得到兩組坐標(biāo)。但是將圓形物體cj的圓心置于這些坐標(biāo)上時(shí)，其有可能與容器或容器內(nèi)除cp、cq外的其他圓形物體相交。如圖2a中j2處與容器相交，圖2b中j1處與圓形物體ct相交。因此，由方程組(4)計(jì)算得到的坐標(biāo)還需進(jìn)一步滿足約束式(2)和式(3)，才能得到可行位置。

同理，待置圓形物體cj與容器和已布局圓形物體cp同時(shí)相切的位置計(jì)算表達(dá)式為：

其中：(xj,yj)和(xp,yp)分別為圓形物體cj和cp的圓心坐標(biāo)，Rj和Rp分別為圓形物體cj和cp的半徑。一般情況下，由方程組(5)也可計(jì)算得到兩組坐標(biāo)。但是將圓形物體cj的圓心置于這些坐標(biāo)上時(shí)，其有可能與容器內(nèi)除cp外的其他圓形物體相交。如在圖2c中，j2處與圓形物體cq相交。因此，由方程組(5)計(jì)算得到的坐標(biāo)還需進(jìn)一步滿足約束式(2)，才能得到可行位置。

結(jié)合上述定義，總結(jié)圓形物體的位置選擇特性如下：

(1)給定一個(gè)格局，圓形物體在當(dāng)前格局下的可行位置通常不止一個(gè)，如在圖3a中，c4有c41、c42和c43三個(gè)可行位置。

(2)將圓形物體放到不同的可行位置上，會(huì)形成不同的布局方案。如圖3b和圖3c中c5的放置位置不同，所形成的布局方案也不同。

(3)不同可行位置的價(jià)值或優(yōu)度一般不同。直觀上看，可行位置的優(yōu)度與格局(這里指將圓形物體放到該位置上所形成的新格局)的緊密程度和剩余空間的完整程度有關(guān)。比如，圖3d中c61處的格局比c62處的格局更為緊湊，說明c61處的空間利用率更高；對(duì)比圖3b和圖3c，將c5置于容器后，后者的剩余空間比前者更為完整，從而可容納更多的圓形物體。

(4)給定不同的格局，圓形物體在容器內(nèi)的可行位置集合不同。如在圖3e和圖3f中，c7的位置集合各不相同。當(dāng)格局中圓形物體數(shù)量較少時(shí)，待置圓形物體無論半徑大小，其在容器內(nèi)可行位置的數(shù)量相差不大；當(dāng)格局中圓形物體的數(shù)量較多時(shí)，半徑較小的圓形物體在容器內(nèi)的可行位置數(shù)量通常高于半徑較大的圓形物體。

2 蟻群定序定位算法

2.1 蟻群優(yōu)化定序

在定序定位法中，確定圓形物體的放置順序是一個(gè)典型的組合優(yōu)化問題。蟻群算法由于既能利用先驗(yàn)問題知識(shí)，又能利用后驗(yàn)解的信息，已被成功用于許多組合優(yōu)化問題。蟻群算法在解決組合優(yōu)化問題時(shí)，通常將其看作圖論中的最優(yōu)路徑問題。本文采用蟻群算法優(yōu)化放置順序，對(duì)應(yīng)的圖論表示如圖4所示。在圖4中，pi,j構(gòu)成了有向圖的頂點(diǎn)，表示第i次放置第j個(gè)圓形物體，從而形成包含i個(gè)圓形物體的格局Ci。由于每個(gè)圓形物體均可在布局的各個(gè)階段放入容器中，因而在構(gòu)造不同階段的格局時(shí)都有n個(gè)頂點(diǎn)可供選擇。因?yàn)橐巡季值膱A形物體不能重復(fù)參與布局，理論上當(dāng)前格局下的每個(gè)頂點(diǎn)與后續(xù)格局下的頂點(diǎn)之間都有n-1條邊。在蟻群算法中，螞蟻的任務(wù)就是構(gòu)造一條從C1到Cn的最優(yōu)路徑。在具體求解過程中，螞蟻根據(jù)各路徑上所積累的信息素及路徑的啟發(fā)信息決定其轉(zhuǎn)移方向。信息素的積累體現(xiàn)的是一種正反饋?zhàn)饔?，啟發(fā)信息則表示對(duì)路徑的期望程度，可根據(jù)某種啟發(fā)式算法確定[23]。

在蟻群算法的基礎(chǔ)上，本文結(jié)合圓形布局問題以及定序定位方法的特點(diǎn)，采用偽隨機(jī)比例規(guī)則確定螞蟻由頂點(diǎn)pk,i轉(zhuǎn)移到頂點(diǎn)pk+1,j的概率：

(6)

(7)

其中：allowedk表示格局Ck下待置圓形物體的集合；xij表示邊(i,j)上的信息素；α表示對(duì)應(yīng)的信息啟發(fā)式因子；yij表示邊(i,j)上的啟發(fā)信息；β表示對(duì)應(yīng)的期望啟發(fā)式因子；zj表示放置第j個(gè)圓形物體的啟發(fā)信息；γ表示對(duì)應(yīng)的期望啟發(fā)式因子；q表示區(qū)間[0,1]內(nèi)的一個(gè)隨機(jī)數(shù)；q0表示決策點(diǎn)，0≤q0≤1。

(8)

蟻群算法在解決經(jīng)典組合優(yōu)化問題旅行商問題(Traveling Salesman Problem，TSP)時(shí)，邊(i,j)上的啟發(fā)信息yij表示由城市i轉(zhuǎn)移到城市j的期望程度。一般而言，城市之間的距離越短，轉(zhuǎn)移的期望程度越高，yij通常取城市之間距離的倒數(shù)。定序定位法在解決圓形布局問題時(shí)將圓形物體逐個(gè)置入容器，放置時(shí)還要考慮格局的緊湊性。一般而言，放置順序相鄰的物體之間的放置位置也相鄰。本文用最優(yōu)布局中各圓形物體之間的距離描述啟發(fā)信息，即

yi,j=1/(di,j+r)，

2.2 蟻群勞動(dòng)分工定位

2.2.1 勞動(dòng)分工與定位過程之間的映射

在蟻群等社會(huì)性昆蟲中，族群需要完成哺育、覓食、筑巢、防御等任務(wù)。蟻群勞動(dòng)分工表現(xiàn)為不同的螞蟻執(zhí)行不同的任務(wù)，且執(zhí)行各項(xiàng)任務(wù)的螞蟻的比率在內(nèi)部繁衍生息和外部侵略挑戰(zhàn)的作用下可以動(dòng)態(tài)變化，而該比率下螞蟻的分工恰好滿足族群對(duì)各項(xiàng)任務(wù)的需求。更重要的是，蟻群中的螞蟻既不具備任何關(guān)于族群需求的全局信息，也不存在一個(gè)領(lǐng)導(dǎo)者指揮螞蟻的行為，螞蟻僅根據(jù)局部信息就能選擇出符合族群需求的恰當(dāng)任務(wù)。蟻群勞動(dòng)分工本質(zhì)上是一種任務(wù)分配，也可以看作是螞蟻對(duì)任務(wù)的選擇。

圓形布局問題的定位過程就是確定圓形物體在容器內(nèi)的放置位置，而這樣的位置通常不止一個(gè)，定位過程則要求從多個(gè)可行位置中選擇一個(gè)恰當(dāng)?shù)奈恢梅胖脠A形物體。因此，定位過程可以看作是圓形物體的位置選擇問題。定序定位法將圓形物體逐個(gè)置入容器，在每個(gè)階段的定位過程中，圓形物體的位置選擇只能依據(jù)當(dāng)前格局的局部信息，而當(dāng)前格局下的最優(yōu)位置不一定是符合整體布局的最佳位置。因此，如何根據(jù)局部信息選擇恰當(dāng)?shù)姆胖梦恢檬嵌ㄎ贿^程的難點(diǎn)所在。

蟻群勞動(dòng)分工可以看作是螞蟻對(duì)任務(wù)的選擇，圓形布局問題的定位過程可以看作是圓形物體對(duì)可行位置的選擇。將圓形物體看作螞蟻，可行位置看作任務(wù)，則任務(wù)選擇可為位置選擇提供參考。據(jù)此，本文提出一種蟻群勞動(dòng)分工定位算法。表1從選擇的視角進(jìn)一步對(duì)比分析了蟻群勞動(dòng)分工和圓形布局的定位過程，二者都屬于離散選擇范疇，這為本文方法的可行性提供了依據(jù)。同時(shí)，蟻群勞動(dòng)分工僅利用局部信息就能選擇出恰當(dāng)任務(wù)的特點(diǎn)，恰好符合圓形布局對(duì)定位過程中位置選擇的要求，這進(jìn)一步增強(qiáng)了本文方法的可行性。

表1 蟻群勞動(dòng)分工和圓形布局定位過程之間的比較

2.2.2 勞動(dòng)分工中的刺激-響應(yīng)原理

蟻群勞動(dòng)分工中的刺激-響應(yīng)原理可簡要描述如下：族群中每個(gè)任務(wù)都對(duì)應(yīng)一個(gè)刺激，刺激的強(qiáng)度描述了任務(wù)的緊急程度。螞蟻對(duì)于每個(gè)任務(wù)都存在一個(gè)閾值，閾值的大小反映了螞蟻響應(yīng)不同任務(wù)的實(shí)際差別。當(dāng)任務(wù)的刺激強(qiáng)度超過螞蟻的響應(yīng)閾值時(shí)，螞蟻選擇任務(wù)的概率高；反之，螞蟻選擇任務(wù)的概率低。BONABEAU[24]和THERAULAZ[25]等給出了刺激—響應(yīng)原理的一種量化形式：假設(shè)某個(gè)任務(wù)的刺激為S，螞蟻對(duì)應(yīng)的閾值為θ，則螞蟻選擇該任務(wù)的概率為P=S2/(S2+θ2)。刺激—響應(yīng)原理通過環(huán)境和個(gè)體的自組織交互實(shí)現(xiàn)了螞蟻對(duì)任務(wù)的選擇，并被成功用于一些任務(wù)選擇問題[26-28]。

2.2.3 勞動(dòng)分工定位算法

將圓形物體看作螞蟻，可行位置看作任務(wù)，分別為可行位置和圓形物體設(shè)置恰當(dāng)?shù)拇碳ず烷撝担瑒t利用蟻群勞動(dòng)分工中的刺激-響應(yīng)原理就可實(shí)現(xiàn)圓形物體對(duì)可行位置的選擇。對(duì)刺激和閾值的設(shè)計(jì)需要結(jié)合圓形布局問題定位過程的特點(diǎn)，這里主要考慮兩個(gè)原則：①增大對(duì)已布局空間的利用;②減小對(duì)未布局空間的破壞。

(1) 刺激

圓形布局問題的目標(biāo)是最大化容器的空間利用率。由于定序定位法是在逐步構(gòu)造布局解，在每一階段一般都會(huì)要求已布局的空間盡量緊湊，這樣才能逐漸提高容器的空間利用率。將待置圓形物體放到給定格局下某個(gè)可行位置上以后，若該物體與其他已放好的圓形物體之間的位置緊密，則說明新格局下已布局空間的利用率高。圓形物體之間的位置關(guān)系可由彼此的距離來度量，距離越短，位置越緊密。計(jì)算待置圓形物體在可行位置上與容器內(nèi)其他圓形物體(排除計(jì)算可行位置的圓形物體)之間的距離，將這些距離由小到大排序后進(jìn)行加權(quán)求和，以此定義新格局的局部密度，如式(9)所示。

(9)

在定位過程中，將待置圓形物體放到某個(gè)可行位置上后，若所形成格局的局部密度越大，說明其對(duì)已布局空間的浪費(fèi)越小，優(yōu)先選擇該位置的機(jī)會(huì)一般也越大。在刺激—響應(yīng)原理中，任務(wù)的刺激越大，個(gè)體選擇任務(wù)的概率越大。因此，可將局部密度看作刺激，假設(shè)二者具有正比關(guān)系：S=ω×Den。

(2)閾值

定序定位法在逐步構(gòu)造布局解的過程中，將容器空間分為已布局空間和未布局空間兩部分。為提高容器的空間利用率，除了要求已布局空間盡量緊湊以外，一般還要求未布局空間連續(xù)完整，這樣才能放置更多的圓形物體。直觀上看，將圓形物體放到容器中心或者靠近中心的位置上時(shí)，其對(duì)容器空間連續(xù)性的破壞比較大。這與穴度算法[29]中基于“金角銀邊草肚皮”的放置思路相似，即容器腹地位置的價(jià)值較低。計(jì)算待置圓形物體在可行位置上與容器中心的距離，以此定義對(duì)應(yīng)位置的容器中心度，如式(10)所示：

(10)

在定位過程中，將待置圓形物體放到某個(gè)可行位置上后，若其對(duì)應(yīng)的容器中心度小，說明其對(duì)容器剩余空間的破壞較小，優(yōu)先選擇該位置的機(jī)會(huì)一般也較大。在刺激—響應(yīng)原理中，個(gè)體的閾值越小，個(gè)體選擇任務(wù)的概率越大。因此，可將中心度看作閾值，假設(shè)二者具有正比關(guān)系：θ=υ×Cen。

(3)選擇概率

假設(shè)待置圓形物體在當(dāng)前格局下共有t個(gè)可行位置，與第i個(gè)可行位置對(duì)應(yīng)的刺激和閾值分別為Si和θi，則根據(jù)刺激—響應(yīng)原理，待置圓形物體選擇第i個(gè)可行位置的概率為：

(11)

(4)定位過程

當(dāng)圓形物體的放置順序確定時(shí)，勞動(dòng)分工定位算法將按照該順序逐個(gè)放置圓形物體，主要包括以下4個(gè)步驟：①在當(dāng)前格局下，計(jì)算出待置圓形物體在容器內(nèi)的可行位置；②將待置圓形物體“試放”到每個(gè)可行位置上，通過分別計(jì)算待置圓形物體與已布局圓形物體和容器的位置關(guān)系，得到與可行位置對(duì)應(yīng)的刺激和閾值；③待置圓形物體根據(jù)式(11)選擇可行位置進(jìn)行放置；④更新當(dāng)前格局，得到新的格局。重復(fù)上述過程，直到最后一個(gè)圓形物體置入容器內(nèi)，或者沒有可行位置放置待置圓形物體為止。

(5) 參數(shù)分析

定位過程即為圓形物體選擇恰當(dāng)?shù)奈恢茫话銜?huì)優(yōu)先考慮使已布局空間緊湊和未布局空間連續(xù)的位置。上述定義的局部密度和容器中心度可以分別描述已布局空間的緊湊性和未布局空間的連續(xù)性，將二者的比值作為可行位置的優(yōu)度。勞動(dòng)分工定位算法中有刺激比例系數(shù)ω和閾值比例系數(shù)υ兩個(gè)參數(shù)?；喪?11)可知，二者以比例(ω/υ)的形式影響圓形物體對(duì)可行位置的選擇。當(dāng)(ω/υ)過大時(shí)，選擇優(yōu)度小的可行位置的概率會(huì)顯著增大，而選擇優(yōu)度大的可行位置的概率則變化不明顯，此時(shí)圓形物體將以近似隨機(jī)的方式選擇可行位置；當(dāng)(ω/υ)過小時(shí)，選擇優(yōu)度大的可行位置的概率會(huì)減小，而選擇優(yōu)度小的可行位置的概率則會(huì)趨于零，此時(shí)圓形物體將近似以貪婪的方式選擇優(yōu)度大的可行位置；對(duì)(ω/υ)取值的設(shè)置，應(yīng)使得選擇優(yōu)度大的可行位置的概率和選擇優(yōu)度小的可行位置的概率保持在接近的量級(jí)，從而避免隨機(jī)選擇或者貪婪選擇的出現(xiàn)。

(6)計(jì)算復(fù)雜度

表 2 不同參數(shù)(ω/υ)下的平均效率 %

2.3 完整的定序定位算法

結(jié)合上述蟻群優(yōu)化定序和蟻群勞動(dòng)分工定位，圖5給出了完整的定序定位算法流程圖。

3 實(shí)驗(yàn)結(jié)果與比較

本文算法通過Java實(shí)現(xiàn)，并在CPU主頻為2.40 GHz、內(nèi)存為4 GB的PC機(jī)上進(jìn)行實(shí)驗(yàn)。選取兩組具有代表性的國際公開算例作為測試集，其中第1個(gè)測試集來自文獻(xiàn)[12]，第2個(gè)測試集來自文獻(xiàn)[30]。

3.1 參數(shù)設(shè)置

本文算法包括蟻群優(yōu)化定序和蟻群勞動(dòng)分工定位兩部分，其中定位算法的設(shè)計(jì)是本文的重點(diǎn)。蟻群優(yōu)化定序中信息素、啟發(fā)式因子等參數(shù)的設(shè)置已在2.1節(jié)給出，本節(jié)主要討論蟻群勞動(dòng)分工定位中刺激—閾值比例系數(shù)(ω/υ)的取值。具體的，從第一個(gè)測試集中選10個(gè)算例來研究(ω/υ)對(duì)布局結(jié)果的影響，并用占空比density(即置入容器內(nèi)所有圓形物體面積之和與容器面積的比值)來度量布局效率。

在(ω/υ)的不同取值下，每個(gè)算例獨(dú)立運(yùn)行5次，表2給出了5次實(shí)驗(yàn)的平均布局效率。從表2可以看出，(ω/υ)∈[1.4,2]時(shí)布局效率較高，這與第2.2.3節(jié)的參數(shù)分析結(jié)論一致。(ω/υ)以平方的形式影響圓形物體對(duì)可行位置的選擇，取值過小時(shí)近似為貪婪選擇，取值過大時(shí)近似為隨機(jī)選擇。因此，本文實(shí)驗(yàn)中將(ω/υ)的值設(shè)為1.6。

3.2 計(jì)算結(jié)果

圓形布局問題的求解方法可以分為全裝填法和定序定位法兩大類。對(duì)比已有文獻(xiàn)發(fā)現(xiàn)，大部分方法屬于全裝填法，而對(duì)定序定位法的研究較少。本文算法屬于定序定位法，為了驗(yàn)證該算法的有效性，分別將其與最新的全裝填法和經(jīng)典的定序定位法進(jìn)行比較。對(duì)于測試集中的每個(gè)算例，獨(dú)立運(yùn)行本文算法10次，記錄其中的最小容器半徑和平均運(yùn)行時(shí)間。

表3給出了本文算法與全裝填法——迭代禁忌變鄰域下降算法(Iterated Tabu Search and Variable Neighborhood Descent, ITS-VND)[11]和空間分

表3 本文算法與全裝填方法的結(jié)果比較

表4給出了本文算法與其他定序定位法——啟發(fā)式算法1(Algorithm 1.0,A1.0)[12]、啟發(fā)式算法1.5(Algorithm 1.5,A1.5)[12]、集束搜索法(Beam Search, BS)[16]、自適應(yīng)集束搜索法(Adaptive Beam Search, ABS)[17]在第一個(gè)測試集上的結(jié)果比較，每個(gè)算例的最小容器半徑用粗體表示。由表4可以看出，本文算法所得結(jié)果在算例NR11-1上與A1.5持平，在算例NR10-1和NR11-1上與BS持平，其余結(jié)果均優(yōu)于A1.0、A1.5和BS。與ABS相比，本文算法在4個(gè)算例上取得了相同的結(jié)果，在剩余17個(gè)算例上取得了更好的結(jié)果。本文算法在這17個(gè)算例上的平均改進(jìn)幅度為0.29%，其中在算例NR40-1上的改進(jìn)幅度最大，在算例NR12-1上的改進(jìn)幅度最小，分別為(355.658 7-352.419 6)/355.658 7=0.91%和(65.033 8-65.024 5)/65.033 8=0.01%。另外，本文算法的計(jì)算時(shí)間也比ABS短。

表4 本文算法與定序定位方法的結(jié)果比較

上述定序定位法提出時(shí)間過早，為進(jìn)一步驗(yàn)證本文算法在進(jìn)行定序定位求解時(shí)的有效性，選擇與文獻(xiàn)[30]中的定序定位算法(Sequential Positioning Algorithm，SPA)繼續(xù)作對(duì)比實(shí)驗(yàn)。由于SPA是針對(duì)圓形物體和矩形容器的一種定序定位算法，對(duì)比時(shí)需要將圓形容器擴(kuò)展為矩形容器。圓形容器對(duì)應(yīng)的目標(biāo)是最小化容器半徑，矩形容器對(duì)應(yīng)的目標(biāo)是寬度固定的情況下最小化容器的長度。主要擴(kuò)展思路如下：對(duì)于待置圓形物體ci，將其與已布局圓形物體和矩形底邊同時(shí)相切的位置，與已布局圓形物體和矩形長邊同時(shí)相切的位置，以及與矩形底邊和長邊同時(shí)相切的位置，都納入潛在可行位置中，并通過不干涉約束刪除其中的不可行位置。矩形容器內(nèi)與可行位置對(duì)應(yīng)的閾值，用待置圓形物體在可行位置上到容器底邊中心線的距離來度量。表5給出了本文算法與SPA在第2個(gè)測試集上的結(jié)果比較，每個(gè)算例的最小容器長度用粗體表示。從表5可以看出，在30個(gè)測試算例中，本文算法在20個(gè)算例上取得的結(jié)果優(yōu)于SPA，在8個(gè)算例上取得的結(jié)果與SPA持平，在2個(gè)算例上取得的結(jié)果不如SPA。SPA在每個(gè)算例上的平均計(jì)算時(shí)間為35.62 s，本文算法在每個(gè)算例上的平均計(jì)算時(shí)間為75.28 s。

表5 本文算法與SPA的結(jié)果比較

3.3 分析討論

本文提出的蟻群勞動(dòng)分工定位算法將圓形布局問題的定位過程看成一個(gè)位置選擇問題，并通過刺激—響應(yīng)的方式為圓形物體選擇可行位置。3.2節(jié)通過與其他算法的橫向?qū)Ρ?，檢驗(yàn)了本文算法的性能，這里進(jìn)一步分析算法內(nèi)部刺激—響應(yīng)選擇方式的特性。具體的，在本文算法框架下，分別設(shè)計(jì)隨機(jī)選擇方式和貪婪選擇方式進(jìn)行對(duì)比。在隨機(jī)選擇方式中，圓形物體等概率選擇可行位置。在貪婪選擇方式中，圓形物體始終選擇優(yōu)度最高的可行位置。

選取第一個(gè)測試集中的24個(gè)算例進(jìn)行對(duì)比實(shí)驗(yàn)，刺激—響應(yīng)選擇(Stimulus-Response Selection, SRS)、隨機(jī)選擇(Random Selection, RS)和貪婪選擇(Greedy Selection, GS)在每個(gè)算例上都獨(dú)立運(yùn)行10次。表6從最優(yōu)值(Best)、平均值(Average)和標(biāo)準(zhǔn)差(Standard Deviation, SD)3個(gè)方面給出了3種選擇方式的實(shí)驗(yàn)結(jié)果，每個(gè)算例的最好結(jié)果用粗體表示。

從表6可以看出：

(1)在最優(yōu)值方面，與RS相比，SRS在所有算例上的平均改進(jìn)幅度為4.18%，其中在算例NR10-1上的改進(jìn)幅度最小為0.11%，在算例NR40-1上的改進(jìn)幅度最大為8.58%。與GS相比，SRS在所有算例上的平均改進(jìn)幅度為0.75%，其中在算例NR16-1上的改進(jìn)幅度最小為0.02%，在算例NR40-1上的改進(jìn)幅度最大為3.94%。

(2)在平均值方面，與RS相比，SRS在所有算例上的平均改進(jìn)幅度為7.73%，其中在算例NR12-1上的改進(jìn)幅度最小為1.36%，在算例NR17-1上的改進(jìn)幅度最大為18.70%。與GS相比，SRS在所有算例上的平均改進(jìn)幅度為0.62%，其中在算例NR11-1上的改進(jìn)幅度最小為0.02%，在算例NR40-1上的改進(jìn)幅度最大為3.01%。

(3)在標(biāo)準(zhǔn)差方面，SRS在所有算例上的平均值為1.04，RS在所有算例上的平均值為6.81，GS在所有算例上的平均值為0.82，說明RS的穩(wěn)定性最差，SRS和GS的穩(wěn)定性相當(dāng)。

表6 三種選擇方式的比較

文獻(xiàn)[31]將算法的收斂性定義為其在優(yōu)質(zhì)解附近逼近最優(yōu)解的能力，將算法的多樣性定義為其通過探索未搜索區(qū)域逼近最優(yōu)解的能力。在隨機(jī)選擇方式下，圓形物體無差別地選擇放置位置，具有很大的盲目性。再結(jié)合布局問題的組合特征，導(dǎo)致其在較優(yōu)解附近(或未探索區(qū)域)逼近最優(yōu)解的能力較差。在貪婪選擇方式下，圓形物體始終選擇優(yōu)度最高的放置位置。由于是在逐步構(gòu)造布局解，這樣的選擇方式很容易使搜索陷入局部最優(yōu)。再結(jié)合布局問題局部最優(yōu)解多的特點(diǎn)，導(dǎo)致其搜索區(qū)域小且容易過早停滯在次優(yōu)解處。刺激—響應(yīng)選擇方式在綜合考慮已布空間緊密度和未布空間完整度的情況下，通過刺激和閾值的相互作用確定圓形物體的放置位置，該選擇過程繼承了蟻群勞動(dòng)分工的任務(wù)選擇柔性，表6的對(duì)比結(jié)果進(jìn)一步表明了其有效性。從概率的角度來看，隨機(jī)方式下所有放置位置被選中的概率相同；貪婪方式以概率1選擇當(dāng)前最優(yōu)的放置位置；刺激—響應(yīng)方式下各放置位置被選中的概率與其優(yōu)度有關(guān)；隨機(jī)方式和貪婪方式是刺激—響應(yīng)方式的兩種極端情況。

4 結(jié)束語

定序定位法求解圓形布局問題時(shí)，按照放置順序(定序)將圓形物體逐個(gè)置入容器中適當(dāng)?shù)奈恢?定位)。本文從“定位可以看成是一個(gè)位置選擇問題”的角度出發(fā)，即從多個(gè)可行位置中選擇一個(gè)恰當(dāng)?shù)奈恢梅胖脠A形物體，提出一種蟻群勞動(dòng)分工算法。該算法的核心思路是借鑒蟻群勞動(dòng)分工的任務(wù)選擇實(shí)現(xiàn)定位過程的位置選擇，并將定位過程對(duì)已布局空間的緊密性要求映射成蟻群勞動(dòng)分工中的刺激，將定位過程對(duì)未布局空間的完整性要求映射成蟻群勞動(dòng)分工中的閾值。蟻群勞動(dòng)分工的任務(wù)選擇柔性使得位置選擇具有一定的靈活性，從而在一定程度上維持了搜索格局的多樣性。對(duì)兩組國際公開測試集的計(jì)算結(jié)果表明，本文算法是求解圓形布局問題的一種快速而有效的算法。

在今后的工作中，擬將本文算法擴(kuò)展應(yīng)用于三角形和不規(guī)則形狀等物體的布局設(shè)計(jì)。此外，布局問題與經(jīng)典的背包問題、下料問題和裝載問題非常類似，相關(guān)成果還可進(jìn)一步推廣到這類問題的求解中。