欢迎来到天天文库
浏览记录
ID:57749454
大小:1012.70 KB
页数:3页
时间:2020-03-28
《一种结合贪婪因子求解0-1背包问题的分布估计算法.pdf》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、基金项目学术探讨2014年第10期一种结合贪婪因子求解0-1背包问题的分布估计算法谭阳周虹(湖南网络工程职业学院,湖南长沙410004)[摘要]针对0-1背包问题,在分布估计算法的基础上提出了一种结合传统贪婪方法的新算法。通过计算物品的重量价值比后获得物品的贪婪因子值,并将贪婪因子融入基本的分布估计算法之中,在保证收敛速度的基础上进一步平衡了个体间的竞争,相较对比算法而言取得了更好的优化结果。[关键词]分布估计算法;贪婪因子;0-1背包问题;概率模型次降序排列。因此本文在对0-1背包问题的处理上采用将物1.引言品的vi/
2、wi值作为该物品的加权因子,以作为在分布估计算法背包问题又称子集合问题,运筹学中一个典型的组合中该物品被选择的参考因素。优化难题,有着广泛的应用背景,如仓库货物装载问题、选2.2分布估计算法址问题等。不失一般性背包问题的描述通常如下:给定n分布估计算法(EDA)是一种新兴的基于统计学原理的个物品和1个背包,物品i的重量为wi,其价值为vi,i=1,随机优化算法最初由Baluja[7]在1994年提出,分布估计算法2,…,n。且该背包的最大容量为C,要从给定的n个物品是一种全新的进化方法。分布估计算法首先构造描述解空中挑选
3、若干个物品放入背包中,要满足挑选的物品总重量间的概率模型,通过对种群的评估,从中选择优秀的个体集不超过C,且总价值达到最大。背包问题的解采用向量合,然后采用统计学习等方法根据优秀的个体构造概率模X=(xT1,x2,…,xn),xi∈{0,1}表示。其数学模型为:型;然后由这个概率模型随机采样产生新的种群,如此反复n迭代,实现种群的进化,直到满足终止条件。标准的EDA的Maxåvixi算法流程如下:i=1nStep1:初始化群体,并对每一个个体计算适应值;ts..åwixi£CStep2:依据适应值,从群体中选择优秀的个体
4、;i=1(1)Step3:根据所选择的个体的分布,构建概率模型;xi∈{0,1}i=1,2,…,nStep4:根据概率模型进行随机采样,生成下一代群体,背包问题属于NP难题,目前求解的方法有精确方法并对新个体计算适应值;(如动态规划、递归法、回溯法、分支限界法等[1]),近似算法Step5:判断是否符合终止条件,符合则算法结束并输出(如贪婪法[1],Lagrange法等)以及智能优化算法(如模拟退火结果;否则转Step2。算法[2]、遗传算法[2]、遗传退火进化算法[3]、蚁群算法[4−5])、粒子本文采用二进制表达,分
5、布估计算法中的种群个体,每群优化算法[6]。精确方法虽然可以得到准确解,但时间复杂个个体采用长度为n的0-1字符串表达对物品的选取情况,性与物品数目成指数关系。近似算法和智能优化算法虽然X=x1,x2,…,xn,xi=0,1,i=1,2,…,n当xi=0时则表示第i个物不一定得到准确解,但可得到比较有效解,并且时间复杂性品没有被选择。比较低。2.3算法的概率模型及更新机制2.结合贪婪因子的分布估计算法通过建立一个包含n个分量的概率向量p(x)=[p(x1),p(x2),…,2.1贪婪因子p(xn)]来表示在解空间中分布的
6、概率模型,其中p(xi)为物品i贪婪算法通过一系列的选择得到问题的解,在每一次总被选取的概率。通常在算法开始时会将初始概率p(x)设置是做出在当前状态下看来是最好的选择,也就是希望通过局为[0.5,0.5,…,0.5]的均匀分布状态,随着算法迭代进化,新部的最优来达到一个全局的最优。这种启发式的策略并不个体的产生则基于概率向量p(x)的分布情况来产生。即个总能获得最优解,然而在许多情况下确能达到预期的目的。体中对于物品i的选取是通过一个0~1间的随机数r来决定通常对于0-1背包问题采用价值密度贪婪准则:每次都选取的,若有
7、r
8、中的PBIL法则[7]来更新概率向量p向量概率p(x);(x)。Step7:判断是否符合终止条件,符合则算法结束并输出N1j结果;否则转Step3。pt+1(x)=(1-α)pt(x)+α∑xt(2)Nj=1由此可见,在分布估计算法中引入贪婪因子可以更好地其中t为算法当前进化的代数,pt(x)为第t代时的概率向量,在
此文档下载收益归作者所有