二次分配问题的布谷鸟搜索算法

许秋艳

（盐城工学院信息工程学院，盐城　224051）

二次分配问题的布谷鸟搜索算法

许秋艳

（盐城工学院信息工程学院，盐城224051）

1　二次分配问题的数学模型

二次分配问题（Quadratic Assignment Problem，QAP）最早由Koopmans和Beckmann在1957年提出［1］，是一种典型的组合优化难题。QAP通常可以描述为：给定n个设施和n个地点，各个地点之间的距离矩阵为D= ［dij］n×n，各个设施之间的运输量矩阵为F=［fij］n×n，设施i建在地点k，且设施j建在地点l所产生的费用为fijdkl。现要将这n个设施建造在这n个地点上，给每个设施分配一个位置，使得总费用最低［2］：

其中，π是所有分配方案的集合，p（i）表示设施i被分配的地点。QAP的目标是找到一个排列p=｛p1，p2，…，pn｝，使得总费用最少。

自提出以来，二次分配问题已经广泛用于许多问题的研究中，例如，工厂位置选址、集成电路布线、作业调度、打字机键盘设计和接力赛跑排序等［3］。目前，用于求解QAP的传统算法有分支定界法、动态规划法和割平面法等；现代启发式算法有遗传算法、模拟退火算法、蚁群算法和粒子群算法等。这些算法为求解QAP提供了思路，但由于自身搜索机制的限制，还不能完全有效求解QAP。当前，如何设计求解QAP的算法仍然是一个开放式的问题。布谷鸟搜索算法（Cuckoo Search Algorithm，CSA）是一种新型现代启发式算法，由Yang 和Deb在2009年提出［4］。CSA具有参数少，易于编程实现和优化性能好等特点，本文将CSA用于对QAP问题的求解，实验结果证明了本文所给算法的可行性和有效性。

2　二次分配问题的布谷鸟搜索算法

CSA源于对布谷鸟寄生育雏行为和鸟类的莱维飞行行为的模拟，算法的伪代码如图1所示，具体原理请参考文献［5］。在求解连续优化问题时，CSA表现出良好的搜索性能。为充分发挥CSA求解连续优化问题的优势，在求解QAP时，算法的搜索空间仍定义在连续空间，且搜索范围限制在［0，1］之间。为将CSA的搜索空间和QAP的解空间相对应，定义如下的映射。以规模为5的QAP为例，假设CSA产生的一个解为［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　数值实验

为测试本文算法的优化性能，采用QAP两个典型算例进行验证。

算例1

算例2

利用本文算法计算这两个QAP算例的函数值分别为2250和1652，对应的排列分别为 ［2，1，4，3］和［3，10，11，2，12，5，6，7，8，1，4，9］。经验证，这两个计算结果已经达到已知的最优解，从而说明本文算法在处理二次分配问题的优势。

4　结语

为求解二次分配问题，本文给出了基于布谷鸟搜索算法的求解方法，并通过实验验证了所提出算法的可行性和有效性，将算法用于图着色问题是进一步的研究方向。

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

［2］马良，朱刚，宁爱兵.蚁群优化算法［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

二次分配问题是一种典型的组合优化难题。该问题由于目标函数的非线性而使得问题的求解异常复杂。为求解二次分配问题，设计基于布谷鸟搜索算法的优化方法。布谷鸟搜索算法是一种新型现代启发式算法，具有结构简单和易于编程等特点。针对二次分配问题的特点，给出算法的实现流程。实验结果表明该算法的可行性和有效性。

二次分配问题；布谷鸟搜索算法；组合优化

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.