知识卡片
背包编码决定可行性处理
0-1 背包要在总重不超过承重 W 的前提下,选出利润最大的物品组合。三种编码对“超重”的处理不同:
| 编码 | 染色体含义 | 会不会超重 |
|---|---|---|
| 二进制 | 第 j 位为 1 表示选第 j 件,如 [0 1 0 1 0 0 0] 表示选第 2、4 件 | 会 |
| 序列 | 物品编号的排列,表示装入的优先顺序 | 不会:按顺序装,装不下的跳过 |
| 可变长度 | 直接列出所选物品,与顺序无关 | 会 |
书中例子:序列 [1 6 4 7 3 2 5]、W = 100,装入 1、6、4 后总重 90,再放 7、3、2 都会超重,只有 5 能让总重恰为 100。
二进制等编码产生的超重解是不可行解,有两种处理:
- 罚函数法:超出承重的重量作为罚值,压低其适应度。
- 解码修复:把被选物品按利润/重量比降序排,依次装入直到装不下。书中例子:选中 2、3、7 号,比值为 1.2、0.33、2.0,按 7、2、3 的顺序装;装 7、2 后重 80,再装 3 会到 110 > 100,于是染色体修正为 [0100001]。
用修复时要明确:参与评价并保留下来的是修复后的解,而不是原染色体。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 . 3 . 3 基 于 遗 传 算 法 的 0 - 1 规 划 · 查看原书依据
对于不可行解,现已提出了两种处理方法:罚函数法和解码方法。 罚函数法由Gordon V.和Whitney D.提出,对于染色体的惩罚值就等于超出背包容量的总重量。
参考来源
- 位置:《智能算法导论》第 1 章 1.3.3 节(`EPUB/xhtml/chapter1_0009.xhtml`);表 1.14–1.16、图 1.26–1.29。
- 结论依据:原文对比三类编码,并讨论不可行解的罚函数与解码方法。
- 原始内容:对于不可行解,现已提出了两种处理方法:罚函数法和解码方法。