知识卡片

普通读书笔记卡 · 1295.i.1.h

背包编码决定可行性处理

理解等级:中级

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]。

用修复时要明确:参与评价并保留下来的是修复后的解,而不是原染色体。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第 1 章 1.3.3 节(`EPUB/xhtml/chapter1_0009.xhtml`);表 1.14–1.16、图 1.26–1.29。 - 结论依据:原文对比三类编码,并讨论不可行解的罚函数与解码方法。 - 原始内容:对于不可行解,现已提出了两种处理方法:罚函数法和解码方法。