因为二次分配问题是一种典型的NP-Hard问题，所以为了求解它就需要研究一种高效率高精度的求解方法。二次分配问题有着非常广泛的应用。无论是在工业应用方面，还在生活实际中多多少少都会遇到类似的问题。国内外学者们通过对这些问题的研究，一共总结出了136种算例[4]。这些算例能帮助人们对实际理论进行研究。在过去的几十年中，随着计算机技术的不断发展，国内外学者对QAP模型使用各种算法的进行深入的仿真研究，在二次分配问题的求解方法上面有着很明显的进步，很多种不同的求解二次分配问题的好方法被研究了出来。本文研究了用萤火虫算法来求解二次分配问题，研究内容如下：72853

（1）对国内外用于求解二次分配问题的算法作一个描述。

（2）本文选用萤火虫算法来求解，并与现在已经取得不错结果的粒子群算法和遗传算法进行对比。

本文选用设备位置等实际问题为背景，研究了使用萤火虫算法来求解二次分配问题。其研究意义为研究已知矩阵的信息，从中获取到有效的知识，来求的最佳花费的结果。将该算法的结果通过与其他已知算法的的结果比较，得知该算法的运行速度更快，能在更短的时间内找到最优解，应用于二次分配问题的求解中是可行的。

通过研究萤火虫算法，并使用萤火虫算法求解QAP问题，是将萤火虫算法从一个只适用于求解连续型问题的算法到一个能用于求解离散型问题的算法进行的一个拓展，也是对QAP问题进行的一个新思路。其他组合优化问题也能以此为鉴，使用萤火虫算法进行求解。

迄今为止，也有很多精确算法用于求解二次分配问题。但是二次分配拥有NP难解性，精确算法只能对 的二次分配问题进行求解。为了能高效准确的求出二次分配问题的最优解，模拟退火算法[5-7]、遗传算法[8-12]、蚂蚁算法[13-16]、粒子群算法[17-18]、禁忌搜索算法[19]和贪婪随机自适应搜索算法[20]等智能性算法应用于求解二次分配问题中。

通过物理中固体物质的退火过程和普通组合优化问题之间有着类似之处提出了模拟退火算法[21]。在Burkard[5] 使用模拟退火算法求解二次分配问题后，Wilhelm和Ward，Connolly[6] 等也使用该算法求解二次分配问题。他们对不同的降温过程使用了交换邻域搜索策略的方法进行了实验，并对实验的结果进行研究分析。结果表明，冷却进度表和控制参数值的不同直接影响到了模拟退火算法的计算结果。Misevicius[7]提出了改进模拟退火算法。该算法将模拟退火算法的初始温度和冷却进度表进行了一定的改进。结果表明，改进模拟退火算法求得的二次分配问题的最优解比模拟退火算法更佳。论文网

在生物进化论的影响下，J。Holland提出了遗传算法[21]。但是无论二次分配问题的规模大小如何，标准遗传算法都很难进行求解。因此大多是将混合遗传算法用于二次分配问题的求解。Fleuren 和Ferland[22]为了使遗传算法能更有效的求解二次分配问题，将它与禁忌搜索算法结合使用。在进行了一系列实验后，证明了该算法所求得的最优解比标准遗传算法更优。Ahuja 和Orlin 等[11]提出了贪婪遗传算法（遗传算法与贪婪机制结合使用）。在当时所有求解二次分配问题的算法里，贪婪遗传算法将QAPLIB库中的103个二次分配实例求得当时的最优解。Drezner [12]根据实际问题的结构，在禁忌搜索的遗传算法中加入了一些特殊交叉机制，并在求解29个QAPLIB库中等以上规模(30 ≤ n ≤ 100)的算例时，取得了非常不错的效果。同时发现该算法所求得的二次分配问题最佳花费，多数情况下比贪婪遗传算法所求得的小。 二次分配问题研究现状:http://www.youerw.com/yanjiu/lunwen_82950.html