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

【作者】 史今驰；

【导师】 朱大铭；

【作者基本信息】 山东大学 ， 计算机软件及理论， 2005， 硕士

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

【Abstract】 Knapsack problem had wide applications in a lot of fields. Knapsack problem is belongs among NP-hard problems. Since 50s, It always been a hotfield problem. In contrast, lots of newer methods and techniques have been developed by introducing concepts and thoughts in other fields into combinatorial optimization. The researches about theores and algorithms existed to solve combinatorial optimization problems have been carried out with more attention to newer methods. In this paper, Simulation is presented by using MATLAB software. The results shows that these new algorithms are useable. The research fields include:1. Traditional methods and techniques in solving comibinatorial optimization especially knapsack problems is presented. Thus as Branch-and-bound algorithms, Dynamic programming algorithms, Tighter bounds algorithms, Imagecompute, Heuristic algorithm, etc.2. How to use Genetic Algorithm in solving combinatorial optiomization has been studied in detail. A novel genetic algerithm is presented by combining simple GA and dissipative system theory for knapsack problem,and simulation research of solving large scale knapsack prmlem is carried out for this method.The result of this method for solving large scale knapsack problem is greatly improved over simple GA for the result of numerical experiment.3. Ant Colony Optimization is a newer product from simulating behavior of ants in seeking food. It’s a kind of bionics random searching algorithm. Usng Ant Colony Optimization to solve combinatorial optimization problems has been studied and the result of recent reserches was given.4. The effect of partical swarm optimization algorithm in combinatorial optimization has been discussed. A new method of connecting 0/1 knapsack problem with partical swarm optimization was devised after analizing the advantage and disadvantage of partical swarm optimization. Analisis and research for the result of the experiment is carried out, and the differences between the various algorithms are given. The direction of study in future is given.更多还原