一种结合贪婪因子求解0-1背包问题的分布估计算法.pdf

《一种结合贪婪因子求解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代时的概率向量，在