参考资料--粒子群优化算法及其在背包问题中的应用.docxVIP

摘要背包问题属于NP难问题，解决背包问题是解决组合优化所面临的问题之一，在现实中有着广泛的应用背景，而粒子群算法作为群智能算法而言，它通过追随当前有哪些信誉好的足球投注网站到的最优值来寻找全局最优。本文在对背包问题进行研究分析的基础上，采用基本粒子群算法、带惯性权重和带收缩因子的改进型粒子群算法来分别解决两个三十维和十维的0/1背包问题，通过多次试验，最终得出了所给的背包问题的最优解，与已知问题最优解一致。关键词：粒子群优化算法，智能算法，背包问题，最优化AbstractKnapsack problem is NP-hard problem to solve the knapsack problem solving combinatorial optimization problems faced by one of the wide range of applications in the real background, while the particle swarm algorithm as a swarm intelligence algorithm, by following the current search for the optimal.The value to find the global optimum. Based on the analysis of the knapsack problem, using the particle swarm algorithm with inertia weight and with a shrinkage factor improved particle swarm optimization to solve the two thirty-dimensional and eleven-dimensional 0/1 knapsack problem, through a multi-trials, and ultimately obtained the optimal solution to the knapsack problem with known optimal solution consistent.Keywords:?Particle swarm optimization?algorithm, ?the?intelligent algorithm, knapsack problem, optimization,目录1 绪论11.1 组合优化问题11.2 背包问题11.3 对背包问题的研究21.4 本文的结构42 优化算法和背包问题52.1 粒子群算法62.2 背包问题72.3 本章小结93 基本粒子群算法在背包问题中的应用103.1 基本粒子群算法103.2 基于基本粒子群算法的背包问题113.3 本章小结214 基于改进型粒子群算法的背包问题224.1 引入惯性权重与收缩因子的改进型粒子群算法224.2 基于改进型粒子群算法的背包问题244.3 本章小结285 总结与展望295.1 本文总结295.2 展望29参考文献30致谢321 绪论1.1 组合优化问题在人们的生活和工作中，总会碰到各种各样的问题，而解决这些问题的方案又有许多，组合优化问题是一种离散最优化问题，就是在给定约束条件下，求出使目标函数极小(或极大)的变量组合问题。组合优化往往涉及排序、分类、筛选等问题，它是运筹学的一个重要分支[1]。典型的组合优化问题有旅行商问题（Traveling Salesman Problem－TSP）、加工调度问题（Scheduling Problem，如Flow-Shop，Job-Shop）、0-1背包问题（Knapsack Problem）、装箱问题（Bin Packing Problem）、图着色问题（Graph Coloring Problem）、聚类问题（Clustering Problem）等。这些问题描述非常简单，并且有很强的工程代表性，理论上说每一个组合优化问题都可以通过枚举的方法求得最优解，但枚举是以时间为代价的，有的枚举时间还可以接受，有的则不可能接受，即所谓的“组合爆炸[2]。对于这些NP完全的组合优化问题，至今尚无很好的解析算法，一般采用启发式算法来解决。 组合优化问题在规划、调度、资源分配、决策等问题中有着非常广泛的应用，在国际上得到了广泛的重视[3]。国际上许多优秀的运筹学家、计算机科学家和数学家等都投入到这一领域，针对许多有重要意义的组合最优化问题提出了相应的理论和优化算法，目前已发展成为运筹学和应用数学的一个十分活跃的研究领域，具有重大的理论意义与实用价值，其目的主要是寻找离散事件的最优编排、分组、次序或筛选等，是运筹学中的一个经典而重要的