← 返回刚才阅读的位置

知识卡片

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

编码要区分非法解与不可行解

理解等级:中级

编码把决策变量映射到染色体,译码将染色体还原为问题解。译码结果可能出两种不同的问题:

  • 非法解:译出来的东西根本不是该问题的一个解,落在解空间之外。示例:旅行商问题要求每个城市恰好访问一次,若交叉后染色体变成 3-2-5-3-…(城市 3 出现两次),它就不是一条合法路线。
  • 不可行解:译出来确实是一个解,但违反约束、不在可行域内。示例:0-1 背包中,每个 0/1 向量都是一种“选不选”的方案,但总重超过背包承重时就是不可行解。

两者的处理不同:非法解要靠保合法的算子或合法化修复,不可行解可用罚分或修复处理。编码可按问题采用二进制、整数或混合表示,但需同时检查可达性、冗余、合法性及邻近基因扰动的影响。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 1 . 2 . 1 遗 传 算 法 流 程 · 查看原书依据

      如图1.2所示非法解指的就是染色体解码出来的解在给定问题的解空间之外,不可行解指的是染色体译码后的解属于解空间,但不属于可行域。 图1.2 编码和译码解析图 编码的方式有很多种。

    参考来源

    - 位置:《智能算法导论》第 1 章 1.2.1 节“遗传算法流程”中的“遗传编码”(`EPUB/xhtml/chapter1_0004.xhtml`,图 1.2)。 - 结论依据:原文区分编码空间、解空间和可行域,并列出不冗余、合法性、完备性与因果性等评价原则;图 1.2 已核对。重复城市与背包超重两例为依据原书定义补充的教学示例(原书 1.3.2 节称 PMX 交叉直接产生的子代“并不是合法的”,1.3.3 节称超重解为不可行解),非该节原文案例。 - 原始内容:非法解指的就是染色体解码出来的解在给定问题的解空间之外,不可行解指的是染色体译码后的解属于解空间,但不属于可行域。 - 位置:《智能算法导论》第 10 章《10.1.3 差分进化算法与遗传算法的比较》(源文件:`_epub-src/EPUB/xhtml/chapter10_0004.xhtml`) - 结论依据:原文说 GA 可采用整数编码求解离散、整数和混合整数问题,支持按问题结构选择表示;不代表每种改造都自动保证可行性。 - 原始内容:采用整数编码将其应用于求解离散型优化问题、例如0-1非线性优化问题、整数规划问题以及混合整数规划问题等。