多媒体实验七报告
实验目的
将贪婪修复方法与遗传算法相结合,构成混和遗传算法,并求解经典背包问题。
算法概要
1. 背包问题概述
假设我们需要从许多物品(通常称作项目)中选择一些来填充一个背包。存在 n 个不
同项目可以使用,每个项目 j 具有重量(weight)
ω
j
和价值(cost) 。背包可以承重的
上限是 V。问题是如何寻找项目的最优子集从而在满足背包承重约束的基础上最大化总价
值。价值,重量和承重是正整数。
设 为二进制变量。如果项目 j 被放入背包,则 =1,否则 =0。背包问题的数学描述
如下:
(7-1)
(7-2)
这种问题就是所谓 0-1 背包问题(0-1 knapsack problem),带有一个简单约束的纯整
数规划,是一类非常重要的整数规划问题。
2. 贪婪算法求解背包问题
贪婪算法属于一步式启发算法,即每采用一个贪婪准则便做出一个不可撤回的决策。
用贪婪算法求解背包问题的特点是每一步迭代选一物品入包,直到无法再装。该算法没有
在两个可行解之间比较选择,算法结束时得到一个可行解。
常用的贪婪准则是价值密度(价值重量比 )贪婪算法,这种选择准则为:从剩余
物品中选择可装入包的 值最大的物品,这也是通常所使用的贪婪策略,因为它是一个
直觉上的近似的解。
3. 基于贪婪算法的混合遗传算法求解背包问题
将贪婪算法与遗传算法相结合构成的混合遗传算法,通过遗传算法的择优,不断重复
执行选择、杂交和变异以及贪婪算法的修正这样一个过程,所求解将不断进化越来越接近
最优解。