粒子群解决背包问题.doc
3页1、PSO解决0-1背包问题背包问题是经典的NP-hard组合约束优化问题之一,由于其难解性,该问题在信息密码学和数论研究中具有极重要的应用。通常求解背包问题的方法有基于深度优先搜索的回溯法、基于广度优先搜索的分支界限法、动态规划法和基于 SIMD共享存储的并行算法,这些都是很成熟的确定性优化方法。随着问题规模的增长,求解背包问题的时间复杂性增长非常快,因此,设计新的高效算法来求解背包问题,具有重要的理论和实际意义。粒子群优化算法(Particle Swarm Optimization,PSO)是一种基于群智能的随机优化技术,在连续域优化问题中已经取得了比较成功的应用,但是在离散域优化上的应用相对较少,本文尝试利用粒子群优化算法求解0-1背包问题。一、粒子群算法的基本原理粒子群优化算法于1995年由Eberhart博士和Kennedy博士提出。在PSO算法中,每个优化问题的解都是搜索空间中的一个“粒子”,算法初始化为一群随机粒子(随机解),然后通过迭代找到最优解。在每一次迭代中,粒子通过跟踪两个“极值”来更新自己,第1个是粒子本身所找到的最优解,称为个体极值xBest,另一个极值是整个种群
2、目前找到的最优解,称为全局极值gBest。在基本粒子群优化算法中,粒子群在一个D维空间中搜索,粒子的总数为n,每个粒子的速度和位置按如下公式进行变化:其中:第k次迭代后粒子i飞行速度矢量的第d维分量;:第k次迭代后粒子i位置矢量的第d维分量;:粒子i个体最好位置xBest的第d维分量;:群体最好位置gBest的第d维分量;,:权重因子;,:随机函数,产生0,1的随机数;:惯性权重函数。式(1)主要通过3部分来计算粒子i的新速度:粒子i前一时刻的速度,粒子i当前位置与自己最好位置之间的距离,粒子i当前位置与群体最好位置之间的距离。粒子i通过式(2)计算新位置的坐标。通过式(1)决定粒子i下一步的运动位置。二、基于0-1背包问题描述背包问题的描述如下:是第i个物品的体积,b是背包的体积,是第i个物品的价值。 本文中所考虑的是0-1背包问题的PSO求解,其数学模型建立如下: 目标函数: 约束条件:三、算法的实现取粒子维数D=20,粒子数n=40,最大代数gnmax=50,加速因子c1=2.0、c2=2.0,惯性权重w=0.8。物品体积和价值可表示为向量:a=92, 4, 43, 83, 84
3、, 68, 92, 82, 6, 44, 32, 18, 56, 83, 25, 96, 70, 48, 14, 58;c=44, 46, 90, 72, 91, 40, 75, 35, 8, 54, 78, 40, 77, 15, 61, 17, 75, 29, 75, 63。通过A=repmat(a,n,1)语句可将a扩展成40*20的矩阵,每一行代表一个粒子,同理也将c扩展成40*20的矩阵C。随机产生初始位置和初始速度,并将单个粒子的初始最佳位置xbest,xbest的适应度fxbest,粒子群的初始最佳位置gbest以及gbest的适应度fgbest都定义为0。然后按照粒子群算法的原理开始循环。在循环过程中更新单个粒子最佳适应度,粒子群最佳适应度,并且计算背包内物品体积是否超过限制,如果超出则将其适应度改为0。最后显示fgbest,即包内物品价值;sgbest,包内物品质量;gbest,显示最佳选择物品方案,1代表选择,0代表不选择。四、结果fgbest = 1024sgbest = 871gbest = Columns 1 through 20 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1图 1五、结果分析与其它进化计算方法相比,PSO算法具有收敛速度快,设置参数少,程序实现异常简洁等优点。但同时由于PSO算法在优化过程中所有粒子都向最优解的方向飞去,所以粒子趋向同一化,群体的多样性逐渐丧失,致使后期算法的收敛速度明显变慢,甚至处于停滞状态,因而很容易陷入局部最优解,也就难以获得较好的优化结果。
《粒子群解决背包问题.doc》由会员飞****9分享,可在线阅读,更多相关《粒子群解决背包问题.doc》请在金锄头文库上搜索。
2019年抚顺市第六中学高考生物简单题专项训练(含解析)
2019年教科版八年级物理上册全册学案
2019年宝鸡晨光中学高考生物简单题专项训练(含解析)
2019年象山港书院高考生物简单题专项训练(含解析)
2019年一级建造师工程经济考点总结
2019年小学教育教学工作总结4篇
2019年浙江省金华市中考数学试卷(解析版)
2019年布拖县中学高考生物简单题专项训练(含解析)
2010年卫生系列中级职称内科学风湿及结缔组织病习题及参考答案
2019年信阳晨光中学高考生物简单题专项训练(含解析)
2018年一级建造师市政实务必考点
2019年和县第三中学高考生物简单题专项训练(含解析)
2018高考化学微题型微考点训练1--20
2019年大理市大理第二中学高考生物简单题专项训练(含解析)
2019年三中高考生物简单题专项训练(含解析)
2018检验检测机构质量手册
2019年衡南县第三中学高考生物简单题专项训练(含解析)
2019年宏华中学高考生物简单题专项训练(含解析)
2018年银行从业资格考试个人贷款考点重点难点总结
2018全省行政执法资格模拟考试试题
2024-04-17 2页
2024-04-17 2页
2024-04-17 2页
2024-04-17 2页
2024-04-17 2页
2024-04-17 2页
2024-04-17 2页
2024-04-17 2页
2024-04-17 2页
2024-04-17 2页