文章编号：１００７—１４２３（２０１５）２６—００４９—０３ ＤＯＩ：１０．３９６９￣．ｉｓｓｎ．１００７—１４２３．２０１５．２６．０１３ 二次分配问题的布谷鸟搜索算法 许秋艳 （盐城工学院信息工程学院，盐城２２４０５１） 摘要： 二次分配问题是一种典型的组合优化难题。该问题由于目标函数的非线性而使得问题的求解异常复杂。为求解二次 分配问题。设计基于布谷鸟搜索算法的优化方法。布谷鸟搜索算法是一种新型现代启发式算法，具有结构简单和易于 编程等特点。针对二次分配问题的特点，给出算法的实现流程。实验结果表明该算法的可行性和有效性。 关键词： 二次分配问题：布谷鸟搜索算法：组合优化 １ 二次分配问题的数学模型 二次分配问题（Ｑｕａｄｒａｔｉｃ Ａｓｓｉｇｎｍｅｎｔ Ｐｒｏｂｌｅｍ，ＱＡＰ） 最早由Ｋｏｏｐｍａｎｓ和Ｂｅｃｋｍａｎｎ在１９５７年提出ｌ１１．是一 是一个开放式的问题。布谷鸟搜索算法（Ｃｕｃｋｏｏ Ｓｅａｒｃｈ Ａｌｇｏｒｉｔｈｍ，ＣＳＡ）是一种新型现代启发式算法，由Ｙａｎｇ 和Ｄｅｂ在２００９年提出 ＣＳＡ具有参数少．易于编程实 现和优化性能好等特点．本文将ＣＳＡ用于对ＱＡＰ问题 的求解．实验结果证明了本文所给算法的可行性和有 效性 种典型的组合优化难题。ＱＡＰ通常可以描述为：给定ｎ 个设施和ｎ个地点．各个地点之间的距离矩阵为Ｄ＝ ［西 ，各个设施之间的运输量矩阵为 ［ ，设施 建在地点ｋ，且设施建在地点ｆ所产生的费用为． ． ２ 二次分配问题的布谷鸟搜索算法 ＣＳＡ源于对布谷鸟寄生育雏行为和鸟类的莱维飞 。现要将这ｎ个设施建造在这ｎ个地点上．给每个设施 分配一个位置．使得总费用最低［２１： ｍｉｎｐ ｉ＝１ ｊ＝ｌ 行行为的模拟，算法的伪代码如图１所示，具体原理请 参考文献『５１。在求解连续优化问题时，ＣＳＡ表现出良好 ・ （ ） 的搜索性能。为充分发挥ＣＳＡ求解连续优化问题的优 势．在求解ＱＡＰ时，算法的搜索空间仍定义在连续空 间，且搜索范围在『０，１１之间。为将ＣＳＡ的搜索空 其中，７ｒ是所有分配方案的集合，Ｐ（ ）表示设施ｉ 被分配的地点。ＱＡＰ的目标是找到一个排列ｐ＝｛Ｐ ，ｐ：， …，ｐｎ｝，使得总费用最少。 自提出以来．二次分配问题已经广泛用于许多问 间和ＱＡＰ的解空间相对应，定义如下的映射 以规模 为５的ＱＡＰ为例，假设ＣＳＡ产生的一个解为 ［０．８１４７，０．９０５８，０．１２７０，０．９１３４，０．６３２４１，对解分量进行 题的研究中，例如，工厂位置选址、集成电路布线、作业 调度、打字机键盘设计和接力赛跑排序等翻。目前，用于 求解ＱＡＰ的传统算法有分支定界法、动态规划法和割 平面法等；现代启发式算法有遗传算法、模拟退火算 排序，每个分量对应的排序号为『３，５，１，２，４１，即第１个 设施被分配在第３个地点．第２个设施被分配在第５ 个地点，第３个设施被分配在第１个地点．第４个设施 被分配在第２个地点，第５个设施被分配在第４个地 点 法、蚁群算法和粒子群算法等。这些算法为求解ＱＡＰ 提供了思路．但由于自身搜索机制的．还不能完全 有效求解ＱＡＰ。当前，如何设计求解ＱＡＰ的算法仍然 现代计算机 ２０１５．０９中④ 布谷鸟搜索算法的伪代码［５１： Ｏｂｊｅｃｔｉｖｅ ｆｕｎｃｔｉｏｎ ｆ（ｘ），ｘ＝（ｘ 一，ｘｄ）Ｔ； Ｉｎｉｔｉａｌ ａ ｐｏｐｕｌａｔｉｏｎ ｏｆ ｎ ｈｏｓｔ ｎｅｓｔｓ ｘｉ（ｉ，１，２，…，ｎ）； Ｗｈｉｌｅ（ｔ＜ＭａｘＧｅｎｅｒａｔｉｏｎ）ｏｒ（ｓｔｏｐ ｃｒｉｔｅｒｉｏｎ） Ｇｅｔ ａ ｃｕｃｋｏｏ（ｓａｙ ｉ）ｒａｎｄｏｍｌｙ ｂｙ Ｌｅｖｙ ｆｌｉｇｈｔ； Ｅｖａｌｕａｔｅ ｉｔｓ ｑｕａｌｉｔｙ／ｆｉｔｎｅｓｓ Ｆｉ； Ｆ＝ Ｃｈｏｏｓｅ ａ ｎｅｓｔ ａｍｏｎｇ ｎ（ｓａｙ ｊ）ｒａｎｄｏｍｌｙ； Ｉｆ（Ｆ。＞Ｆ ） Ｒｅｐｌａｃｅ ｊ ｂｙ ｔｈｅ ｎｅｗ ｓｏｌｕｔｉｏｎ； Ｅｎｄ Ａｂａｎｄｏｎ ａ ｆｒａｃｔｉｏｎ（ｐ ）ｏｆ ｗｏｒｓｔ ｎｅｓｔｓ Ｄ＝ ［ａｎｄ ｂｕｉｌｄ ｎｅｗ ｏｎｅｓ ａｔ ｎｅｗ ｌｏｃａｔｉｏｎｓ ｖｉａ ｅｖｙＬ ｌｆｉｇｈｔｓ］； Ｋｅｅｐ ｔｈｅ ｂｅｓｔ ｓｏｌｕｔｉｏｎｓ（ｏｒ ｎｅｓｔｓ ｗｉｔｈ ｑｕａｌｉｔｙ ｓｏｌｕｔｉｏｎｓ）； Ｒａｎｋ ｔｈｅ ｓｏｌｕｔｉｏｎｓ ａｎｄ ｆｉｎｄ ｔｈｅ ｃｕｒｒｅｎｔ ｂｅｓｔ； Ｅｎｄ ｗｈｉｌｅ Ｐｏｓｔｐｒｏｃｅｓｓ ｒｅｓｕｌｔｓ ａｎｄ ｖｉｓｕａｌｉｚａｔｉｏｎ． 利用本文算法计算这两个ＱＡＰ算例的函数值分 别为２２５０和１６５２，对应的排列分别为【２，１，４，３】和 【３，１０，１ｌ，２，１２，５，６，７，８，１，４，９１。经验证，这两个计算 结果已经达到已知的最优解．从而说明本文算法在处 理二次分配问题的优势。 ３ 数值实验 为测试本文算法的优化性能．采用ＱＡＰ两个典型 算例进行验证。 １ ２ ２ ３ ４ ４ ５ ３ ５ ６ ７ ３ ４ ６ ８ ５ ６ ６ ５ ｌ ４ ６ ３ Ｏ ６ ３ ７ ９ ９ ２ ２ ７｛７ 算例１ １ Ｏ ｉ １ ２ ３ ３ ４ ２ ４ ５ ６ ４ 结语 为求解二次分配问题．本文给出了基于布谷鸟搜 ２ １ ０ ２ １ ２ ２ ３ １ ３ ４ ５ Ｏ ９Ｏ １０ ０ ０ ７８ ２６ ４ ６ Ｏ ２ ６ ４ ４ ４ ２ ６ ３ ６ Ｏ ６ ３ ２ Ｏ ５ Ｓ ３ ３ ９ ４ ３ ６ ９Ｏ ０ ０ ０ ２ １ ２ Ｏ １ ２ ２ ３ ３Ｄ＝ ３ ４ ５Ｆ＝ ｉ０ ０ ０ ４５ ０ Ｏ ５６ １８ ０ ２１ ５６ ３ ２ １ １ Ｏ １ ｉ ２ ２ ２ ３ ４ ４５ Ｏ ８ ７ ６ ５ Ｏ ４ ３ ４ ５ ７ ６ ７ １８ ２１ Ｏ 索算法的求解方法．并通过实验验证了所提出算法的 可行性和有效性．将算法用于图着色问题是进一步的 研究方向。 ４ ３ ２ ２ ｉ ０ ２ ３ ３ ｉ ２ ３ ５ ９ ４ ５ ４ Ｏ ８ ５ ５ Ｓ ７ ５ 算例２ ４ ３ ２ ２ １ ２ ０ ｉ ３ １ ２ ３ ５ ４ ３ ３ ２ ３ １ ０ ４ ２王２ ６ ９ ４ ３ ３ ８ ０ ６ ８ ４ ６ ７ ６ ２ ４ ３ ４ ５ ６ Ｏ １ ５ ５ ３ ３ ２ １ ３ ２ ３ ３ ４ Ｏ ４ Ｓ ６ ５ ２ ２ ９ ５ ５ ８ １ Ｏ ４ ５ ２ ５ ４ ３ ３ ２ １ １ ２ ４ Ｏ １ ２ ６ ５ ４ ４ ３ ２ ２ １ ５ １ ０ １ ６ ５ ５ ４ ３ ３ ２ ６ ２ １ ０ ｌ ７ ６ ４ ７ ５ ４ ５ ４ ０ ７ ７ ４ ４ ３ ３ ６ ７ ６ ５ ５ ７ Ｏ ９ ６ ７ ６ ６ ７ ５ ７ ３ ２ ７ ９ Ｏ 参考文献： 【１］Ｋｏｏｐｍａｎｓ Ｔ Ｃ，Ｂｅｃｋｍａｎｎ Ｍ Ｊ．Ａｓｓｉｇｎｍｅｎｔ ｐｒｏｂｌｅｍｓ ａｎｄ ｔｈｅ ｌｏｃａｔｉｏｎ ｏｆ ｅｃｏｎｏｍｉｃ ａｃｔｉｖｉｔｉｅｓ［Ｊ］．Ｅｃｏｎｏｍｅｔｒｉｃａ，１９５７，２５（１）：５３—７６． 【２】马良，朱刚，宁爱兵．蚁群优化算法［Ｍ］．北京：科学出版社，２０１０． ［３］张惠珍，马良，王洪刚．二次分配问题及其研究进展（Ｉ）ｌＪ１．科技通报，２０１０，２６（６）：８０１—８０５，８１６． ［４］Ｙａｎｇ Ｘ，Ｄｅｂ Ｓ．Ｃｕｃｋｏｏ ｓｅａｒｃｈ ｖｉａ ｌｅｖｙ ｌｆｉｇｈｔｓ［Ｃ］．Ｗｏｒｌｄ Ｃｏｎｇｒｅｓｓ ｏｎ Ｎａｔｕｒｅ＆Ｂｉｏｌｏｇｉｃａｌｌｙ Ｉｎｓｐｉｒｅｄ Ｃｏｍｐｕｔｉｎｇ．Ｐｉｓｃａｔａｗａｙ：ＩＥＥＥ Ｐｕｂｌｉｃａｔｉｏｎｓ，２００９：２１０—２１４． ［５］Ｙａｎｇ Ｘ Ｓ，Ｄｅｂ Ｓ．Ｅｎｇｉｎｅｅｒｉｎｇ ｏｐｔｉｍｉｚａｔｉｏｎ ｂｙ ｃｕｃｋｏｏ ｓｅａｒｃｈ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｍａｔｈｅｍａｔｉｃａｌ Ｍｏｄｅｌｉｎｇ ａｎｄ Ｎｕｍｅｒｉｃａｌ Ｏｐｔｉ— ｍｉｚａｔｉｏｎ．２０１０．１（４）：３３０—３４３． 作者简介： 许秋艳（１９８１一），女，讲师，从事领域为算法设计及其应用 收稿日期：２０１５—０６—２５ 修稿日期：２０１５—０９—１０ ④ 现代计算机２０１５．０９中 Ｃｕｃｋｏｏ Ｓｅａｒｃｈ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｑｕａｄｒａｔｉｃ Ａｓｓｉｇｎｍｅｎｔ Ｐｒｏｂｌｅｍ ＸＵ Ｑｉｕ——ｙａｎ （Ｓｃｈｏｏｌ ｏｆＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＹａｎｃｈｅｎｇＩｎｓｔｉｔｕｔｅ ｏｆＴｅｃｈｎｏｌｏｇｙ，Ｙａｎｃｈｅｎｇ ２２４０５１） Ａｂｓｔｒａｃｔ： Ｑｕａｄｒａｔｉｃ Ａｓｓｉｇｎｍｅｎｔ Ｐｒｏｂｌｅｍ（ＱＡＰ）ｉｓ ａ ｔｙｐｉｃａｌ ｈａｒｄ ｐｒｏｂｌｅｍ ｉｎ ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ．Ｉｔ ｉｓ ｈａｒｄ ｔｏ ｓｏｌｖｅ ＱＡＰ ｂｅｃａｕｓｅ ｏｆ ｉｔｓ ｎｏｎ— ｌｉｎｅａｒ ｏｂｊｅｃｔｉｖｅ ｆｕｎｃｔｉｏｎ．Ｔｏ ｓｏｌｖｅ ＱＡＰ．ｐｒｏｐｏｓｅｓ ａ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ Ｃｕｃｋｏｏ Ｓｅａｒｃｈ Ａｌｇｏｒｉｔｈｍ（ＣＳＡ）．ＣＳＡ ｉｓ ａ ｎｏｖｅｌ ｍｅｔａｈｅｕｒｉｓｔｉｃ ｗｈｉｃｈ ｉｓ ｓｉｍｐｌｅ ａｎｄ ｅａｓｙ ｔｏ ｐｒｏｇｒａｍ．Ａｃｃｏｒｄｉｎｇ ｔｈｅ ｆｅａｔｕｒｅｓ ｏｆ ＱＡＰ，ｓｈｏｗｓ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｐｒｏｃｅｄｕｒｅ．Ｔｈｅ ｒｅｓｕｌｔｓ ｄｅｍｏｎｓｔｒａｔｅ ｔｈａｔ ｔｈｅ ｐｒｅｓｅｎｔｅｄ ｍｅｔｈｏｄ ｉＳ ｆｅａｓｉｂｌｅ ａｎｄ ｅｆｆｅｃｔｉｖｅ． Ｋｅｙｗｏｒｄｓ： Ｑｕａｄｒａｔｉｃ Ａｓｓｉｇｎｍｅｎｔ Ｐｒｏｂｌｅｍ；Ｃｕｃｋｏｏ Ｓｅａｒｃｈ Ａｌｇｏｒｉｔｈｍ；Ｃｏｍｂｉｎａｔｏｒｉａｌ Ｏｐｔｉｍｉｚａｔｉｏｎ （上接第４５页） Ａ Ｓｏｃｉａｌ Ｎｅｔｗｏｒｋ Ｓｐｒｅａｄ Ｃｏｓｔ Ｍｏｄｅｌ Ｂａｓｅｄ ｏｎ Ｕｓｅｒ Ｉ ｎｆｌｕｅｎｃｅ ＹＡＮＧ Ｙａｎｇ ，ＷＡＮＧ Ｙａｎｇ－ｙｕ （１．Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｎａｎｊｉｎｇ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ ２１００２３； ２．Ｃｏｌｌｅｇｅ ｏｆ Ｔｅａｃｈｅｒ Ｅｄｕｃａｔｉｏｎ，Ｎａｎｊｉｎｇ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ ２１００２３） Ａｂｓｔｒａｃｔ： Ｉｎ ｏｒｄｅｒ ｔｏ ａｓｓｅｓｓ ｔｈｅ ｃｏｓｔ ｏｆ ｔｈｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ｓｐｒｅａｄ ｔｏ ｂｌｏｇ，ｐｒｏｐｏｓｅｓ ａ ｍｅｔｈｏｄ ｔｏ ａｓｓｅｓｓ ｔｈｅ ｃｏｓｔ ｏｆ ａ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ｃｏｍｍｕｎｉｃａｔｉｏｎ． Ｂａｓｅｄ ｏｎ ＰａｇｅＲａｎｋ ａｌｇｏｒｉｔｈｍ ａｎｄ ａｎａｌｙｔｉｃ ｈｉｅｒａｒｃｈｙ ｐｒｏｃｅｓｓ，ｃａｌｃｕｌａｔｅｓ ｔｈｅ ｕｓｅｒ ｉｎｆｌｕｅｎｃｅ．Ｕｓｅｓ ｇｒｅｅｄｙ ａｌｇｏｒｉｔｈｍ ａｎｄ ｇｌｏｂａｌ ａｌｇｏｒｉｔｈｍ， ｉｎｆｅｒｓ ｔｈｅ ｕｓｅｒｓ ｒｅｌｅａｓｉｎｇ ｑｕａｎｔｉｔｙ ｒａｎｋ ｗｈｅｎ ａｌｌ ｕｓｅｒｓ ｃａｎ ｓｅｅ ｉｔ，ａｎｄ ｃｏｍｐａｒｅｓ ｔｈｅ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ．Ｃｏｎｓｉｄｅｒｉｎｇ ｔｈｅ ｕｓｅｒ ｉｎｆｌｕｅｎｃｅ ａｎｄ ｔｈｅ ｕｓｅｒ ｒｅｌｅａｓｉｎｇ ｑｕａｎｔｉｔｙ ｒａｎｋ，ｅｓｔａｂｌｉｓｈｅｓ ａ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ｓｐｒｅａｄ ｃｏｓｔ ｍｏｄｅｌ，ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｂｌｏｇ ｄａｔａ，ａｓｓｅｓｓｅｓ ｔｈｅ ｃｏｓｔ ｏｆ ｔｈｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ｓｐｒｅａｄ． Ｋｅｙｗｏｒｄｓ： ＰａｇｅＲａｎｋ Ａｌｇｏｒｉｔｈｍ；Ａｎａｌｙｔｉｃ Ｈｉｅｒａｒｃｈｙ Ｐｒｏｃｅｓｓ；Ｇｒｅｅｄｙ Ａｌｇｏｒｉｔｈｍ；Ｇｌｏｂａｌ Ａｌｇｏｒｉｔｈｍ；Ｓｏｃｉａｌ Ｎｅｔｗｏｒｋ Ｓｐｒｅａｄ Ｃｏｓｔ Ｍｏｄｅｌ 现代计算机 ２０１５ ｆ）９申＠
