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

許秋艷

（鹽城工學院信息工程學院，鹽城　224051）

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

許秋艷

（鹽城工學院信息工程學院，鹽城224051）

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

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

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

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

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

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

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

3　數(shù)值實驗

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

算例1

算例2

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

4　結(jié)語

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

［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］.北京：科學出版社，2010.

［3］張惠珍，馬良，王洪剛.二次分配問題及其研究進展（I）［J］.科技通報，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-），女，講師，從事領域為算法設計及其應用

2015-06-25

2015-09-10

二次分配問題是一種典型的組合優(yōu)化難題。該問題由于目標函數(shù)的非線性而使得問題的求解異常復雜。為求解二次分配問題，設計基于布谷鳥搜索算法的優(yōu)化方法。布谷鳥搜索算法是一種新型現(xiàn)代啟發(fā)式算法，具有結(jié)構(gòu)簡單和易于編程等特點。針對二次分配問題的特點，給出算法的實現(xià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.