宋真真，王金敏（天津職業(yè)技術師范大學機械工程學院，天津　300222）

一種解決三維矩形布局問題的蟻群算法

宋真真，王金敏
（天津職業(yè)技術師范大學機械工程學院，天津300222）

摘要：針對三維矩形布局問題，提出一種布局蟻群算法，該算法通過賦定值與隨機產生2種方式給出螞蟻的初始信息素并求得布局初始解。在迭代過程中選擇不同的信息素揮發(fā)系數，使更新后的信息素值隨機性更強，從而提高了算法的尋優(yōu)性能。通過算例的計算并與已有文獻結果進行比較，表明本文提出的算法可得到更優(yōu)的布局結果。關鍵詞：布局問題；蟻群算法；揮發(fā)系數

現代生活中的許多實際問題，例如集裝箱貨物擺放、儀器艙內儀器布局、車間布局設計、集成電路的設計等都涉及三維布局問題[1]，因此研究三維布局問題的有效解法具有重要的實際意義。隨著布局問題研究的不斷深入，求解算法越來越復雜，各種智能算法也隨之應用到布局問題中，如蟻群算法、遺傳算法、模擬退火算法、粒子群算法等。魯強等[2]使用蟻群優(yōu)化算法來優(yōu)化平面布局問題，利用蟻群變異特征加快了解的收斂速度。DANIEL等[3]根據應用在容器裝載布局問題的砌墻法并結合一維箱體裝載布局的求解方法，提出了一種直接的啟發(fā)式算法用來求解到二維、三維箱體布局。張德富等[4]根據砌墻工人長期積累的經驗，提出砌墻式算法用以求解三維矩形布局問題。WANG等[5]提出一種基于動態(tài)空間分解的三叉樹啟發(fā)式算法，用來解決三維裝箱問題。蟻群算法[6]具有通用性、魯棒性、自組織性、正反饋、并行分布式計算等特點，因此能夠更好地應用于組合優(yōu)化問題。本文將蟻群算法應用到三維矩形布局問題中，力求得到更好的布局結果。

1　三維矩形布局問題

1.1布局模型

三維矩形布局問題是指將形狀為長方體的布局物體（矩形塊）互不干涉地放入長方體的布局容器中，且矩形塊的各表面分別平行于布局容器的各表面；布局所追求的目標是使布局容器利用率最高。布局模型描述如下：

式中：Fit為布局容器的利用率，也稱布局適應度值函數；n表示布入容器的矩形塊的個數；li、wi、hi分別表示第i個已布入矩形塊的長、寬、高；L、W、H分別表示容器的長、寬、高；（xi、yi、zi）和（xj、yj、zj）分別表示第i個和第j個已布入矩形塊的中心點坐標；li、wi、hi分別表示第i個已布入矩形塊的長、寬、高。這里令布局容器的左下前角點的坐標為（0，0，0）。式（2）確保矩形塊完全布入容器中，而式（3）則保證了矩形塊互不干涉。

1.2定位規(guī)則

本文采用吸引子法作為矩形塊的定位方式，它通過在布局容器設置一些吸引子，用來吸引待布局矩形塊，以實現待布局矩形塊的定位。吸引子法描述如下：

在布局容器中設置m個吸引子，吸引子t的位置表示為（x0t，y0t，z0t）。待布矩形塊i在點（xi，yi，zi）處的定位函數為：

本文采用4個吸引子用于解決三維矩形布局問題。吸引子分別布置在布局容器下面的4個角點，即左下前、左上前、左上后、左下后，其定位函數為：

當系數ωt、αt、βt、γt確定后，定位函數也隨之確定。G（xi，yi，zi）取最小值的坐標點，即為此矩形塊的布入點。

2　布局蟻群算法

20世紀90年代初期，意大利學者Dorigo等[8-9]通過模擬自然界中螞蟻集體尋徑的行為而提出了蟻群算法（ant colony algorithm），它是一種基于種群的啟發(fā)式仿生類并行智能進化算法。蟻群算法包含適應階段和協(xié)作階段2個基本階段。在適應階段，螞蟻個體根據自身信息素濃度的大小進行自身調整；而在協(xié)作階段，各螞蟻通過信息交換，進行個體調整，以獲得更好的解。

蟻群算法相對于其他算法，對初始解的要求不高，在搜索的過程中不需要進行人工調整。利用正反饋原理，在一定程度上可以加快尋找到最優(yōu)解的速度；利用并行分布式計算的特征，不同螞蟻個體之間只能進行信息交流和傳遞，從而能夠相互協(xié)作，避免算法的早熟性收斂，有利于發(fā)現近似最優(yōu)解。

2.1信息素初始化及更新規(guī)則

蟻群算法是一種新興的智能優(yōu)化算法，自身存在易陷入局部最優(yōu)解的問題，容易出現停滯的現象。所以本文將蟻群信息素初始值的確定分為賦定值與隨機產生2種方式。

（1）依前人經驗，根據占角順序策略、下臺階法等[7]吸引子參數的特點，賦予其中一部分螞蟻[0，1]之間特定的值，以期得到較好的布局結果。

（2）為減小算法陷入局部最優(yōu)解的幾率，其余螞蟻的信息素賦值為[0，1]之間的隨機數。

螞蟻在不斷活動的同時，伴隨著信息素的釋放與揮發(fā)，在不同情況下信息素的更新方式會有所不同，如式（6）和式（7）。

若更新后的信息素值不在[0，1]范圍內，則將其在[0，1]之間隨機賦值；若τCbestj為0，強制τCbestj=0.001，即取接近0的極小值。

p0為螞蟻轉移概率的臨界值。p0值越小，則說明越靠近最優(yōu)解。?。?.1，0.2）之間的隨機數，當pij

ρ表示信息素揮發(fā)系數，其值越小，表明殘留信息素越多。ρ=c*ROU，ROU為與ρ相關的常數；c為變量系數。為使更新后的信息素值隨機性更強，取值范圍更廣，使變量系數c隨著迭代次數的改變而改變，c取值為：

式中：K為迭代次數。

2.2布局蟻群算法

本文利用蟻群算法優(yōu)化吸引子參數，提出了布局蟻群算法（PACA），算法步驟如下。

步驟1設置螞蟻個數N、迭代次數K。

步驟2初始化：產生N個螞蟻的初始信息素τij，計算每只螞蟻的適應度Fi（ti），從中選擇適應度最大的螞蟻，記錄其序號Cbest，適應度值記為Fi（tCbes）t，攜帶的信息素值為τCbestj。

步驟3迭代次數k=k+ 1，螞蟻序號i=0。

步驟4 i=i+ 1。

步驟6計算更新后每個螞蟻的適應度Fit′（i），若Fit′（i）>Fi（tCbes）t，則Fi（tCbes）t=Fit′（i），Cbest=C′best，記錄對應Fi（tCbes）t及Cbest。若當前循環(huán)中還有未執(zhí)行上述操作的螞蟻，即i

步驟7若k>K，轉至步驟8；否則，轉至步驟3。

步驟8輸出螞蟻Cbest的信息、布局方案及Fit （Cbes）t，算法結束。

3　算例及分析

本文在1.73 GHz、0.99 GB內存的計算機上，利用C++語言編寫程序實現布局蟻群算法，采用文獻[10]中的后6組算例（BR算例）進行運算。BR算例共有15組。每組100個算例。本文選取的BR10~BR15屬于強異構問題，而且異構性逐漸增強。蟻群算法初始參數選擇N=40、K=20、ROU=0.1。計算中，容器利用率是算例計算10次后得到的平均值。

選取BR10的部分算例（21~30），采用5種方式進行計算，得到布局結果如表1所示。5種方式主要用于研究算法中初始信息素、揮發(fā)系數的選擇對布局結果的影響。表1中：方式1的初始信息素隨機選取，揮發(fā)系數取0.2；方式2的初始信息素是由賦定值與隨機產生2種方式結合得到的，揮發(fā)系數取為0.2；方式3的初始信息素隨機選取，揮發(fā)系數取0.1；方式4的初始信息素隨機選取，揮發(fā)系數取0.3；方式5的初始信息素由賦定值與隨機產生2種方式結合得到，揮發(fā)系數取0.1。

表1　5種方式的布局利用率%

從表1中可以看出，方式3和方式5得到的利用率相對較高，兩者區(qū)別在于初始信息素的選取方式，相同之處為揮發(fā)系數均選取0.1。經過比較可知，初始信息素由2種方式結合給出、揮發(fā)系數取為0.1時，布局結果最好。

為研究揮發(fā)系數選取方式對布局結果的影響，選取BR10的部分算例（21~30）進行計算，得到布局結果如表2所示。表2中：I的揮發(fā)系數選取恒定值0.1；II的揮發(fā)系數在（ρmin，ρmax）之間取隨機值，ρmin=0.02，ρmax=0.1；III中的揮發(fā)系數?。?，0.1）之間的隨機值；IV中的揮發(fā)系數?。?，0.1）之間的值。

表2　4種情況的容器利用率%

從表2可以看出，IV的利用率最高，即揮發(fā)系數采用分段選取的方式較好。

根據表1和表2的分析結果，選取2種方式結合得到信息素初始值，揮發(fā)系數由分段方式得到，計算BR10~BR15這6組算例的容器利用率，具體計算結果及比較如表3所示。

表3　布局結果比較%

由表3可以看出，從BR10到BR15，隨著布局塊種類的增加，容器利用率呈不斷上升趨勢，說明本算法在強異構布局問題上更有優(yōu)勢。此外，BR14和BR15均得到了當前最優(yōu)值，分別比文獻中的最優(yōu)值提高0.3%和0.16%；BR10~BR13平均值計算結果沒有得到當前最優(yōu)值，但是利用率高于上述大部分算法。雖然文獻[14]中的BR10~BR13的利用率高于本文算法的利用率，矩形塊在每個待布局點有3個方向可以放置，經計算后選擇使剩余空間最小的方式，但本文中體積遞減的方式在待布局點是確定的放置方向，所以本文算法的復雜度比文獻[14]算法的復雜度低。

為探尋容器利用率與迭代次數和螞蟻個數之間的關系，經部分算例（81~90）計算后，得到趨勢圖，如圖1和圖2所示。

圖1　利用率與迭代次數的關系（算例81~90）

圖2　利用率與螞蟻個數的關系（算例81~90）

從圖1中可以看出，容器利用率在迭代次數為40時，曲線趨于平穩(wěn)。在尋找容器利用率與螞蟻個數的關系時，得到了圖2的“W”型曲線，說明容器利用率不一定隨著螞蟻個數的增多而增大；在迭代次數為40、60、80時出現利用率高值點，迭代次數為50、70時出現利用率低值點，說明在迭代次數為偶數時，容器利用率較高。

4　結束語

本文針對三維矩形布局問題，將賦定值與隨機生成2種方式作為初始信息素的來源，在更新方式的信息素揮發(fā)系數選取上提出分段選取的思想，經過算例計算及分析，本文算法取得了良好的計算結果。此外，算法還有一些問題有待進一步研究解決，如怎樣通過改變信息素更新方式提高算法的搜索能力，如何去探究容器利用率與螞蟻個數的關系等，這些將是今后研究的內容與方向。

參考文獻：

［1］COLORNI A，DORIGO M，MANIEZZO V，et al. Distributed optimizationbyantcolonies［C］//Proceedingsof European Conference on Artificial Life. Paris：Elsevin Publishing，1991：134-142.

［2］魯強，陳明.平面布局的蟻群算法［J］.計算機應用，2005，25（5）：1019-1021.

［3］DANIEL M，ANDREAS B. A heuristic for solving large bin packing problems in two and three dimensions［J］. CEJOR，2012，20：337-354.

［4］張德富，韓水華，葉衛(wèi)圍.求解矩形Packing問題的砌墻式啟發(fā)式算法［J］.計算機學報，2008，31（3）：509-515.

［5］WANG Z J，KEVIN W L，JASON K L. A heuristic for the container loading problem：A tertiary -tree -based dynamic space decomposition approach［J］. European Journal of Operational Research，2008，191：86-99.

［6］朱麗萍，王金敏.基于空間分割的求解布局幾何可行域的算法［J］.天津職業(yè)技術師范大學學報，2012，22（2）：30-33.

［7］王金敏，楊維嘉.動態(tài)吸引子在布局求解中的應用［J］.計算機輔助設計與圖形學學報，2005，17（8）：1725-1720.

［8］LODI A，DORIGO M，MANIEZZO V，et al. Distributed optimization by ant colonies［C］//Proceedings of European Conference on Artificial Life. Paris：Elsevin Publishing，1991：134-142.

［9］BONABEAU E，DORIGO M，THERAULAZ G. Inspiration for optimization from social insect behaviour［J］. Nature，2000，406（6）：39-42.

［10］BISCHOFF E E，RATCLIFFB S W. Issues in the development of approaches to container loading［J］. Omega，1995，23（3）：377-390.

［11］GEHRING H，BORTFELDTA. A genetic algorithm for solving the container loading problem［J］. International Transactions in Operational Research，1997，4（6）：401-418.

［12］BORTFELD T A，GEHRING H. A tabu search algorithm for weakly heterogeneous container loading problems［J］. OR Spectrum，1998，20（4）：237-250.

［13］GEHRING H，BORTFELD T A. A parallel genetic algorithm for solving the container loading problem［J］. International Trasactions in Operational Research，2002，9（4）：497-511.

［14］MOURA A，OLIVEIRA J F. A GRASP approach to the container loading problem［J］. IEEE Intelligent Systems，2005，20（4）：50-57.

［15］王金敏，朱麗蘋，甄士剛.一種基于蜜蜂進化選擇算子的布局遺傳算法［J］.圖形學學報，2014，35（5）：690-696.

Ant-colony algorithm for 3D rectangular packing problem

SONG Zhen-zhen，WANG Jin-min
（School of Mechanical Engineering，Tianjin University of Technology and Education，Tianjin 300222，China）

Abstract：A packing ant-colony algorithm is proposed for the 3D rectangular packing problem.The algorithm obtains initial information and packing initial solution of ants by two ways，specific values and random values. And the article takes different pheromone evaporation coefficients in the iterative process，making the random of update information values stronger，which improves the searching optimization of the algorithm.Through the calculation of some cases，it indicates that the packing results are better than the existing literature by the algorithm of the article.

Key words：packing problem；ant-colony algorithm；volatile coefficient

作者簡介：宋真真（1989—），女，碩士研究生；王金敏（1963—），男，教授，碩士生導師，研究方向為智能布局、計算機輔助設計與圖形學.

基金項目：天津職業(yè)技術師范大學科研發(fā)展基金資助項目（KJ14-64）.

收稿日期：2015-07-09

中圖分類號：TP301.6

文獻標識碼：A

文章編號：2095－0926（2015）03－0025－04