参考文献 28

致谢 30

图清单

图序号 图名称 页码

图4-1 建立M文件 12

图4-2 Fuction编写界面 13

图4-3 模型的M文件创建 14

图4-4 Mutate的M文件创建 15

图4-5 MyCost的M文件创建 16

图4-6 PlotSolution的M文件创建 17

图4-7 萤火虫算法主程序的M文件创建 18

图4-8 萤火虫算法最终迭代位置图 19

图4-9 萤火虫算法最佳花费过程图 19

图4-10 粒子群算法最终迭代位置图 20

图4-11 粒子群算法最佳花费过程图 21

图4-12 遗传算法最终迭代位置图 21

图4-13 遗传算法最佳花费过程图 22

表清单

表序号 表名称 页码

表4-1 算例一结果对比 23

表4-2 算例二结果对比 25

表4-3 算例三结果对比 25

1 绪论

1。1 课题背景

二次分配问题是一种典型的最优化问题。最优化问题由针对连续变量的和针对离散变量的两类组成。组合优化问题是一种针对离散变量并从给定的一个有限对象集中寻求到一个最佳对象组合从而求得最优解的过程的问题。

组合优化也是一种数学优化，与算法理论、计算复杂度理论和运筹学知识都有着密不可分的联系。在求解数学问题上，组合优化会寻找一种有效地分配资源的方法。同时，它在人工智能、机器学习、软件工程、经济学理论等领域也都有着重要应用。组合优化问题很难去求解，因为它所需要的运行时间和存储空间不是固定不变的，都会随着问题规模的增大而增加，所以在计算机上很难去实现它，就是所谓的“组合爆炸”，也就不能用穷举搜索方法了。组合优化问题具有典型型而且求解难度高，这使得很多学者纷纷去研究这个问题。

二次分配问题是一个组合优化问题。它非常著名且有挑战性。二次分配问题由Koopmans和Beckmann[1]在1957年首次提出后，在背板布线、作业调度、打字机键盘设计、公司网点布局等各种工程领域都得到广泛的应用。甚至，一些同为NP-hard类型的组合优化问题，也能转化为二次分配问题[2]去求解。文献综述

1976年Sahni和Gonzales[3]证明了二次分配问题是一个NP-hard问题。因为二次分配问题存在着“组合爆炸”现象，它的分配规模越大搜索空间也会越大，所以要在短时间内求得问题的最佳结果是比较困难的。二次分配问题计算复杂，很难去求解。许多优化工具在测试性能时把它作为一个测试的标准。通过对求解二次分配问题方法发展的了解，能很清楚的知道到当今优化技术的发展和熟练度。因而，找到一种能很好地求解二次分配问题的算法对理论研究价值和实际应用背景都有很大的帮助。