二次分配問題的布谷鳥搜索算法

許秋艷

（鹽城工學(xué)院信息工程學(xué)院，鹽城　224051）

二次分配問題的布谷鳥搜索算法

許秋艷

（鹽城工學(xué)院信息工程學(xué)院，鹽城224051）

1　二次分配問題的數(shù)學(xué)模型

二次分配問題（Quadratic Assignment Problem，QAP）最早由Koopmans和Beckmann在1957年提出［1］，是一種典型的組合優(yōu)化難題。QAP通常可以描述為：給定n個(gè)設(shè)施和n個(gè)地點(diǎn)，各個(gè)地點(diǎn)之間的距離矩陣為D= ［dij］n×n，各個(gè)設(shè)施之間的運(yùn)輸量矩陣為F=［fij］n×n，設(shè)施i建在地點(diǎn)k，且設(shè)施j建在地點(diǎn)l所產(chǎn)生的費(fèi)用為fijdkl。現(xiàn)要將這n個(gè)設(shè)施建造在這n個(gè)地點(diǎn)上，給每個(gè)設(shè)施分配一個(gè)位置，使得總費(fèi)用最低［2］：

其中，π是所有分配方案的集合，p（i）表示設(shè)施i被分配的地點(diǎn)。QAP的目標(biāo)是找到一個(gè)排列p=｛p1，p2，…，pn｝，使得總費(fèi)用最少。

自提出以來，二次分配問題已經(jīng)廣泛用于許多問題的研究中，例如，工廠位置選址、集成電路布線、作業(yè)調(diào)度、打字機(jī)鍵盤設(shè)計(jì)和接力賽跑排序等［3］。目前，用于求解QAP的傳統(tǒng)算法有分支定界法、動(dòng)態(tài)規(guī)劃法和割平面法等；現(xiàn)代啟發(fā)式算法有遺傳算法、模擬退火算法、蟻群算法和粒子群算法等。這些算法為求解QAP提供了思路，但由于自身搜索機(jī)制的限制，還不能完全有效求解QAP。當(dāng)前，如何設(shè)計(jì)求解QAP的算法仍然是一個(gè)開放式的問題。布谷鳥搜索算法（Cuckoo Search Algorithm，CSA）是一種新型現(xiàn)代啟發(fā)式算法，由Yang 和Deb在2009年提出［4］。CSA具有參數(shù)少，易于編程實(shí)現(xiàn)和優(yōu)化性能好等特點(diǎn)，本文將CSA用于對(duì)QAP問題的求解，實(shí)驗(yàn)結(jié)果證明了本文所給算法的可行性和有效性。

2　二次分配問題的布谷鳥搜索算法

CSA源于對(duì)布谷鳥寄生育雛行為和鳥類的萊維飛行行為的模擬，算法的偽代碼如圖1所示，具體原理請(qǐng)參考文獻(xiàn)［5］。在求解連續(xù)優(yōu)化問題時(shí)，CSA表現(xiàn)出良好的搜索性能。為充分發(fā)揮CSA求解連續(xù)優(yōu)化問題的優(yōu)勢(shì)，在求解QAP時(shí)，算法的搜索空間仍定義在連續(xù)空間，且搜索范圍限制在［0，1］之間。為將CSA的搜索空間和QAP的解空間相對(duì)應(yīng)，定義如下的映射。以規(guī)模為5的QAP為例，假設(shè)CSA產(chǎn)生的一個(gè)解為［0.8147，0.9058，0.1270，0.9134，0.6324］，對(duì)解分量進(jìn)行排序，每個(gè)分量對(duì)應(yīng)的排序號(hào)為［3，5，1，2，4］，即第1個(gè)設(shè)施被分配在第3個(gè)地點(diǎn)，第2個(gè)設(shè)施被分配在第5個(gè)地點(diǎn)，第3個(gè)設(shè)施被分配在第1個(gè)地點(diǎn)，第4個(gè)設(shè)施被分配在第2個(gè)地點(diǎn)，第5個(gè)設(shè)施被分配在第4個(gè)地點(diǎn)。

布谷鳥搜索算法的偽代碼［5］：

3　數(shù)值實(shí)驗(yàn)

為測(cè)試本文算法的優(yōu)化性能，采用QAP兩個(gè)典型算例進(jìn)行驗(yàn)證。

算例1

算例2

利用本文算法計(jì)算這兩個(gè)QAP算例的函數(shù)值分別為2250和1652，對(duì)應(yīng)的排列分別為 ［2，1，4，3］和［3，10，11，2，12，5，6，7，8，1，4，9］。經(jīng)驗(yàn)證，這兩個(gè)計(jì)算結(jié)果已經(jīng)達(dá)到已知的最優(yōu)解，從而說明本文算法在處理二次分配問題的優(yōu)勢(shì)。

4　結(jié)語

為求解二次分配問題，本文給出了基于布谷鳥搜索算法的求解方法，并通過實(shí)驗(yàn)驗(yàn)證了所提出算法的可行性和有效性，將算法用于圖著色問題是進(jìn)一步的研究方向。

［1］Koopmans T C，Beckmann M J.Assignment problems and the location of economic activities［J］.Econometrica，1957，25（1）：53-76.

［2］馬良，朱剛，寧愛兵.蟻群優(yōu)化算法［M］.北京：科學(xué)出版社，2010.

［3］張惠珍，馬良，王洪剛.二次分配問題及其研究進(jìn)展（I）［J］.科技通報(bào)，2010，26（6）：801-805，816.

［4］Yang X，Deb S.Cuckoo search via levy flights［C］.World Congress on Nature&Biologically Inspired Computing.Piscataway：IEEE Publications，2009：210-214.

［5］Yang X S，Deb S.Engineering optimization by cuckoo search［J］.International Journal of Mathematical Modeling and Numerical Optimization，2010，1（4）：330-343.

Quadratic Assignment Problem；Cuckoo Search Algorithm；Combinatorial Optimization

Cuckoo Search Algorithm for Quadratic Assignment Problem

XU Qiu-yan

（School of Information Engineering，Yancheng Institute of Technology，Yancheng 224051）

1007-1423（2015）26-0049-03

10.3969/j.issn.1007-1423.2015.26.013

許秋艷（1981-），女，講師，從事領(lǐng)域?yàn)樗惴ㄔO(shè)計(jì)及其應(yīng)用

2015-06-25

2015-09-10

二次分配問題是一種典型的組合優(yōu)化難題。該問題由于目標(biāo)函數(shù)的非線性而使得問題的求解異常復(fù)雜。為求解二次分配問題，設(shè)計(jì)基于布谷鳥搜索算法的優(yōu)化方法。布谷鳥搜索算法是一種新型現(xiàn)代啟發(fā)式算法，具有結(jié)構(gòu)簡單和易于編程等特點(diǎn)。針對(duì)二次分配問題的特點(diǎn)，給出算法的實(shí)現(xiàn)流程。實(shí)驗(yàn)結(jié)果表明該算法的可行性和有效性。

二次分配問題；布谷鳥搜索算法；組合優(yōu)化

Quadratic Assignment Problem（QAP）is a typical hard problem in combinatorial optimization.It is hard to solve QAP because of its nonlinear objective function.To solve QAP，proposes a method based on Cuckoo Search Algorithm（CSA）.CSA is a novel metaheuristic which is simple and easy to program.According the features of QAP，shows the algorithm procedure.The results demonstrate that the presented method is feasible and effective.