一种求解0-1背包问题退火贪婪遗传算法

一种求解0-1背包问题退火贪婪遗传算法

ID:32804616

大小:56.10 KB

页数:4页

时间:2019-02-15

一种求解0-1背包问题退火贪婪遗传算法_第1页
一种求解0-1背包问题退火贪婪遗传算法_第2页
一种求解0-1背包问题退火贪婪遗传算法_第3页
一种求解0-1背包问题退火贪婪遗传算法_第4页
资源描述:

《一种求解0-1背包问题退火贪婪遗传算法》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

1、一种求解0-1背包问题退火贪婪遗传算法摘要:将贪婪算法和退火算法融入遗传算法,结合各自算法的优点形成了一种混合遗传算法。通过实验表明,运用此算法求解0-1背包问题,搜索能力明显优于基本遗传算法和贪婪算法。关键词:0-1背包问题;遗传算法;贪婪算法;模拟退火中图分类号:TP301.60T背包问题(KnapsackProblem)是一个典型的NP完全(NondeterministicPolynomiaCompleteness)问题⑴,在现实生活中有着广泛应用,如生产安排、资源分配、投资决策等都可建模为背包问题。因此,

2、对该问题求解方法的研究,在理论上和实践中都有着重要的意义。求解0-1背包问题的方法有多种,如枚举法、动态规划法、回溯法、贪婪算法、遗传算法等。其中,遗传算法作为智能搜索算法的一种,具有全局寻优、智能搜索以及收敛速度快等特性,在求解0-1背包问题中显现了一定的优势。遗传算法基于"优胜劣汰”自然选择机制,通过选择、交叉、变异等操作使群体中的个体不断朝着最优解的方向移动[2]。本文在各种算法对背包问题研究的基础上,将贪婪算法和模拟退火算法引入遗传算法,给出了一种混合遗传算法求解0-1背包问题。1背包问题数学模型背包问题

3、的一般描述为:已知n个物品的重量wi(wi>0)和价值ci(ci>0)(i=l,2,…,n),给定一个背包,容量限制为v(v>0),问如何选择物品装入背包,使得在背包容量限制之内,装入的物品总价值最大,且单个物品不能多次装入、不能分割。0T背包问题的数学模型可表示为[3]:目标函数:约束条件:xi丘(0,1}(i=l,2,…,n)式中,xi为0-1决策变量,xi=l时表示物品i装入背包中,xi=0时表示其未装入。2混合遗传算法设计2.1染色体编码方法根据0-1背包问题的特点,采用与问题物品个数等长的二进制编码方法

4、。编码串中1表示对应的物品放入背包中,0表示不放入。如110110101000……0001表示第1、2、4、5、7、9、n号物品放入背包中,其他的则不放入。2.2贪婪算法在解码中的应用上述编码方案虽然比较直观,但随机生成的编码串,或是交叉、变异操作产生的新个体,不一定满足约束条件,即在这种编码方案下会产生一些无效染色体。可引入贪婪算法的思想解决这一问题,这里采用单位价值贪婪策略[4],这种策略为:从剩余物品中选择可装入包的价值密度Pi=ci/wi值最大的物品,直到超出背包容量为止。具体步骤如下:①对所有xi=l的

5、物品,按它们的价值密度Pi二ci/wi(i=l,2,•••,n)形成一个从大到小排序的队列q(i),即价值密度最高的物品序号为q(1),次之为q(2),以此类推。②置k=lo③引入贪婪算法解码变换:如果,则将q(k)所对应的物品装入背包,置xq(k)=1,k=k+l,转向第③步;如果,则转向第④步。④往后的队列序号j,即从k到n对应的物品不放入背包,置xq(j)=0。2.3适应度函数因为背包问题求的是目标函数的最大值,所以可用目标函数值作为适应度函数值,即适应度函数为:2.4选择、交叉和变异算子遗传算法通过使用选

6、择算子对个体进行优胜劣汰操作。这里采用遗传算法常用到的比例选择算子,即是轮赌盘选择,这种选择方法个体被选中的概率与它的适应度大小成正比,保证了适应度较高的个体被选择到下一代的几率更高。考虑到交叉、变异操作可能会破坏当代最优个体,最终选择算子采用比例选择基础上的最优保存策略(最优保存策略能让适应度最好的个体不被破坏,尽可能保留到下一代群体中)。由于采用二进制编码方案,因此交叉算子采用较为简单的单点交叉算子,即在编码串中随机设置一个交叉点,然后在该点处按交叉概率pc交换两个个体的部分染色体。变异算子采用基本位变异,即

7、以变异概率pm将随机指定的基因座上的值由1变为0,或由0变为1。2.5模拟退火过程模拟退火算法是基于金属退火的机理而创建的一种通用优化算法,它依据Metropolis准则接受新解,其在接受优质解的同时,在一定限制范围内接受劣质解,因此能够有效跳出局部最优的"陷阱”[5]。模拟退火算法与遗传算法相比较,模拟退火算法具有较强的局部搜索能力,而遗传算法则能更好的把握全局搜索,将两种算法相结合,可以互相取长补短。步骤如下:①设置初始温度Tk(k=0),迭代次数num(numWN+)。②置ni=lo③进行第ni次迭代,将染

8、色体的第ni位的基因置为0,第chromlength-ni+1(chromlength为染色体长度)位基因置为1,以此提高模拟退火的局部搜索能力,并计算函数差值△仁f(j)-f(i),其中j为新生成的个体,i为原来的个体。如果Af20,则新生成个体复制到下一代群体;如果Af

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。