二次多背包问题及其扩展问题的启发式算法研究

摘要

二次多背包问题是经典0-1背包问题的一个扩展，在实际生活着中有着广泛的应用，例如当不同工人相互合作时有不同效率的情况下将工人分配到不同的任务、有预算约束下通信卫星的地球站选址问题以及铁路站点、货物运输终端、机场的选址问题等。与之相关的组成医疗小组问题来源于意大利米兰的某个医疗服务中心，该问题与二次多背包问题有着相似的结构，可以看成二次多背包问题的变种问题。这两个问题除了广泛的实际应用背景，也是一类十分复杂的组合优化问题，对于设计启发式算法求解十分有挑战。鉴于其实用性和理论挑战性，已经吸引了大批学者的目光，在文献中提出了各类求解这两个问题的启发式算法，但是仍然存在不足之处，还需要进一步的深入研究。本文拟在在已有的研究求解二次多背包问题以及组成医疗小组问题文献的基础上，提出更为高效的启发式算法并提升现有文献中的最好解，为求解这类问题提供更多的选择。
　　首先，研究了使用混合了可行与不可行局部搜索的禁忌搜索算法求解二次多背包问题。该算法引入了不可行解搜索阶段，允许算法在搜索过程中搜索不可行解，能够为算法带来更多的自由度。然后，我们在算例上进行了大量的实验来证明该算法的有效性并分析了算法各个重要组成部分的关键作用。
　　其次，本文根据二次多背包问题的分组特性，提出了一种基于backbone交叉算子混合算法求解该问题，该算子能够保留父代中的物品分配信息并遗传到子代，产生高质量的解。我们将该混合算法在不同时间限制下的计算结果与文献中求解QMKP最好的几种算法进行了对比，证明了该算法优异性并给出了小结。
　　第三，研究了由二次多背包问题变种而来的组成医疗小组问题，结合该问题的特点，提出了一种求解组成医疗小组问题的二阶段禁忌搜索算法。该算法中的二阶段局部搜索过程可以很好的处理目标函数和约束之间相互影响的关系，能够防止算法过早地陷入局部最优。我们通过实验将该算法与文献中的最好算法进行了对比，并分析了二阶段搜索过程对算法性能的影响，最后给出了小结。
　　第四，延续了第五章所研究的组成医疗小组问题，根据该问题的分组特性，将求解二次多背包问题的混合问题移植到用来求解组成医疗小组问题。该算法使用了基于的backbone交叉算子来生成高质量的子代并集成了一种基于质量和距离的种群更新规则来保持算法搜索过程中种群的健康度。我们同样给出了算例实验将其性能与文献中的算法进行了对比，并进行了额外的实验分析了算法各个重要组成部分在算法中的巨大作用。

目录

声明

1 绪 论

1.1 研究背景和意义

1.2 研究目标与方法

1.3 本文的结构

1.4 本文的主要创新点

2国内外相关研究综述

2.1 背包问题研究现状

2.2 二次背包问题的研究现状

2.3多背包问题的研究现状

2.4 二次多背包问题的研究现状

2.5 组成医疗小组问题的研究现状

2.6 小结

3带有策略震荡的禁忌搜索算法求解二次多背包问题

3.1问题描述与算法的提出

3.2求解QMKP的禁忌搜索算法

3.3计算实验

3.4对TS主要组成部分的分析

3.5本章小结

4混合算法求解二次多背包问题

4.1算法提出的背景

4.2 求解QMKP的混合算法

4.3计算实验

4.4本章小结

5 二阶段禁忌搜索算法求解组成医疗小组问题

5.1问题描述与算法的提出

5.2 求解CMC问题的二阶段禁忌搜索算法

5.3计算实验

5.4本章小结

6 混合算法求解组成医疗小组问题

6.1算法提出的背景

6.2求解CMC的混合算法

6.3计算实验

6.4对算法的分析

6.5本章小结

7全文总结与研究展望

7.1全文总结

7.2研究展望

致谢

参考文献

附 录1 攻读博士学位期间发表和完成的学术论文

附 录2 攻读博士学位期间主持和参与的研究课题