基于概率粒子群算法的背包问题的研究

论文摘要

背包问题属于NP难问题,解决背包问题是解决组合优化所面临的问题之一,在现实中有着广泛的应用背景,开展对解决复杂组合优化问题的算法研究具有一定的理论意义和实用价值。本文在对背包问题进行研究分析的基础上,分析和比较了各类方法,提出了一种用于求解0-1背包问题的基于概率模型的粒子群算法。该算法利用对概率向量的操作实现群体的进化,来提高算法性能。然后利用本文构造的算法分别针对不同规模的背包问题进行了求解。实验结果表明本文提出的概率粒子群优化算法可以有效的改进算法收敛能力和寻优效果。

论文目录

• 中文摘要
• 英文摘要
• 第一章 绪论
• 1.1 选题的背景和意义
• 1.1.1 组合优化问题
• 1.1.2 背包问题
• 1.1.3 粒子群优化算法
• 1.2 国内外研究现状
• 1.2.1 背包问题的研究现状
• 1.2.2 粒子群算法的研究现状
• 1.3 本文的组织
• 第二章 背包问题
• 2.1 背包问题简介
• 2.2 背包问题的数学模型
• 2.3 背包问题的算法简介
• 2.3.1 背包问题的精确算法简介
• 2.3.2 背包问题的近似算法简介
• 2.4 小结
• 第三章 粒子群优化算法
• 3.1 粒子群算法的三种典型模型
• 3.1.1 基本PSO 模型
• 3.1.2 引入惯性权重的PSO 模型
• 3.1.3 带收缩因子的PSO 模型
• 3.2 粒子群算法的特点
• 3.3 PSO 算法的其他改进方法
• 3.3.1 离散PSO
• 3.3.2 自适应PSO
• 3.3.3 混合PSO
• 3.3.4 免疫PSO
• 3.4 PSO 与其它进化算法的比较
• 3.5 粒子群优化算法的应用
• 3.6 小结
• 第四章 概率粒子群优化算法
• 4.1 粒子群算法改进策略
• 4.1.1 粒子群算法存在的问题及其改进思路
• 4.1.2 PSO 的粒子速度更新项分析
• 4.1.3 PSO 的收敛性能分析
• 4.1.4 改进后的PSO 流程
• 4.1.5 典型测试函数分析
• 4.2 概率分析进化算法
• 4.2.1 概率分析进化算法概述
• 4.2.2 概率分析进化算法的基本原理
• 4.2.3 概率分析进化算法的分类
• 4.3 引入概率分析进化算法的粒子群算法
• 4.3.1 概率粒子群算法描述
• 4.3.2 改善搜索速度的策略
• 4.3.3 概率粒子群算法流程
• 4.4 小结
• 第五章 概率粒子群算法求解背包问题
• 5.1 应用概率粒子群算法求解背包问题
• 5.1.1 粒子的构造方式
• 5.2 仿真试验
• 5.3 小结
• 第六章 结论
• 参考文献
• 致谢
• 在学期间发表的学术论文和参加科研情况