多维背包问题(Multi-dimensional Knapsack Problem, MKP)是当今现实生活中使用最为广泛的背包问题,也是著名的整数规划问题。自从Lorie和Savage设计出第一个MKP例子以来,研究者们不断地对其探索与研究,经过半个世纪的努力,MKP在运筹学、经济学、信息学、航空技术等领域均获得广泛应用。本文研究了MKP的遗传算法求解方案,设计出一种基于模式扰动的改进遗传算法(SIGA).该算法首先利用模式固定率Ra进行自适应模式替换,生成和保存种群的优良个体；之后引入扰动因子优化交叉操作,引入“模式基因差异比”调整变异算子,提高寻优能力,最大程度上增加了种群的多样性,避免算法陷入局部最优；最后利用贪婪算子的价值重量比来评价适应度值,完成最大利用率解的修正与修复。通过对实例的仿真实验表明该算法能够快速搜索到最优解并迅速收敛于该值,搜索性能比一般遗传算法更强,得到的解精度更高、更稳定。在分析混沌理论与蚁群算法的基础上,本文将混沌搜索思想与自适应蚁群算法相结合,提出了一种引入混沌搜索的自适应蚁群算法(CAACA)来求解MKP。利用混沌因子影响信息素的更新,既保证了搜索初期的速度又扩大了搜索后期的范围；重新设计选择概率并选用概率和为u的“轮盘赌”思想来选择蚂蚁路径,增大了搜索的随机性,结合启发式因子的动态调整以及禁忌表的交换策略,在很大程度上避免算法陷入局部最优。通过测试大量的实例,对解性能、收敛性等方面的比较,结果表明CAACA不仅可以得到高精度的解,而且有效改善了蚁群算法早熟收敛的问题,提高了搜索性能。最后,本文对SIGA和CAACA两种算法性能进行了对比,并将集装箱装载问题建模成多维背包问题加以求解,结果表明,在求解小规模问题时,SIGA在收敛速度、求解效率上要优于CAACA;在求解大规模问题时,CAACA在求解性能、求解精度上要优于SIGA。