背包问题的实用求解算法研究

背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、网络 信息安全等应用中具有重要的价值。从计算复杂性理论看,背包问题是一个经 典NP难解问题。半个多世纪以来,该问题一直是算法与复杂性研究的热点问 题之一。论文研究了背包问题的实用求解算法,提出了改进的新算法,并利 用Maltab对几种算法进行了仿真实验,测试的结果显示出新算法在解决0/1背包 问题时表现出了良好的性能。在论文中主要进行的工作如下: 1. 首先讨论了传统算法设计技术求解背包问题的方法,主要有递归算法、动 态规划算法、分支定界法、图论法、贪婪算法等,同时讨论了背包问题在 电子商务公钥密码系统中的应用。 2. 论文中重点研究了遗传算法(GA)在解决背包问题上的应用,在广泛了 解现有遗传算法的优缺点的基础上,结合耗散结构理论提出了耗散遗传算 法(DGA)。耗散遗传算法能够在一定程度上克服普通遗传算法的缺点。 通过仿真实验证实了该方法在解决0/1背包问题上的有效性。 3. 另外本文还研究了蚁群算法(ACO)在解决背包问题上的应用,蚁群优化 算法是新出现的一种模拟蚂蚁觅食行为的仿生随机优化算法,在货郎商 问题(TSP)等优化问题上有较为成熟的应用,本文将其应用在背包问题 中,也取得了较好的效果。 4. 同时本文也研究了粒子群算法(PSO)在解决背包问题上的应用。粒子群 优化算法是在对模拟鸟群捕食行为的研究中产生的一种新算法,本文将其 与其他算法进行了对比,并给出了在0/1背包问题上的解决方法。