第三章  遗传算法在背包问题中的应用 10

3。1 背包问题 10

3。2 对背包问题的二进制编码 10

3。3 控制参数确定 10

3。4 适应度函数 11

3。4。1 适应度函数的作用 11

3。4。2 适应度函数的设计 11

3。5 选择算子的设计 12

3。6 交叉算子的设计 12

3。7 变异算子的设计 13

3。8 约束问题的处理 13

3。9 精英保留策略 14

第四章 遗传算法的实验 15

4。1 算法测试实验 15

4。1。1 测试函数选择 15

4。1。2 测试结果 15

4。2 遗传算法解决背包问题 18

4。3 改变控制参数的实验 19

4。3。1 改变种群大小 19

4。3。2 改变变异概率大小 20

4。3。3 改变交叉概率大小 21

4。4 解决不同维数的背包问题 22

结论与展望 24

致谢 25

参考文献 26

附录 27

第一章 绪论

1。1 本研究课题的目的及意义

背包问题是组合优化领域中的一个典型问题，现代社会中的很多资源分配问题都跟 背包问题相关[1]。背包问题具有非常广泛的实际应用领域，在商业、投资组合优化、计 算复杂性理论、组合数学、应用数学和密码学等领域经常出现背包问题的身影[2]。虽然 很容易对其陈述，但是想要对其求解却有很大的难度，它属于很困难的 NP 完全问题。 如果能找到切实有效的解决背包问题的方法，这将对可计算理论创造出巨大的理论价 值。目前对于这个问题的求解方法已经有了很多，比如解析法、枚举法等，但是这些优 化方法存在着一些缺点，在解决复杂的背包问题时，算法的过程会十分繁琐。

遗传算法所使用的是群体搜索技术，它以一定规格的种群作为一个单位进行搜索， 通过选择、交叉、变异等遗传操作对目前的种群进行搜索，由此产生出新一代的不完全 一样的群体，并逐步使种群进化到拥有或靠近最优解的状态[3]。因此，遗传算法以其更 加优秀的搜索能力，极为有效地对规模较大的复杂问题进行优化处理，并且更容易进行 计算，其功能也更强。作为一种新的全局优化搜索方式的遗传算法，相较于传统的优化 算法，凭借其简单通用、高效、实用、稳定性强、以及易于并行处理等突出特点，效力 于各种行业领域，并获得了不俗的成效，遗传算法已经成为重要的智能算法之一。

越来越多的学者正探索着构造更合适的遗传算法框架、建立更加有效的遗传作图。 而对于背包问题的求解这一方面的应用研究使得遗传算法日益完善，随着遗传算法的性 能一步步提高，遗传算法必将解决更加复杂的背包问题。