← 返回刚才阅读的位置

知识卡片

结构图卡 · 3760.a.1.a

cDDE以概率采样搜索排列

理解等级:高级

压缩离散差分进化(cDDE)用于置换流水车间调度,解是工件排列。它用概率分布(由节点矩阵和边矩阵表示的概率模型)初始化并生成候选排列,同时保存两个排列:当前排列,以及迄今最好的精英排列。

每轮迭代:

  1. 从概率模型采样两个排列。
  2. 按 DE/best/1 变异:“best”表示以最优个体(这里即精英排列)为基础,“1”表示用一组差异去扰动它,差异来自两个采样排列;再按交叉概率交叉,得到候选。
  3. 对候选做基于插入操作的局部搜索。
  4. 用 Metropolis 准则决定是否接受:更好就接受,更差也以随温度下降的概率接受,见 [[较差候选仍可按温度概率接受]]。
  5. 更新节点矩阵和边矩阵,直到满足终止条件。

连续 DE 的“差向量”在这里改成了基于排列的扰动,因此表示、搜索和接受规则都面向排列空间。原书未展开两个矩阵的具体含义与更新式。

结构图:

flowchart TD
  A[初始化可行排列、精英与概率模型] --> B[按模型采样排列]
  B --> C[DE/best/1变异与交叉]
  C --> D[插入局部搜索]
  D --> E{Metropolis准则接受?}
  E -- 是 --> F[更新当前排列]
  E -- 否 --> G[保留当前排列]
  F --> H[更新节点与边概率模型]
  G --> H
  H --> I{满足终止条件?}
  I -- 否 --> B
  I -- 是 --> J[输出精英排列]
这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第 10 章《10.4.1 基于差分进化算法的置换流水线调度》(源文件:`_epub-src/EPUB/xhtml/chapter10_0011.xhtml`) - 结论依据:步骤明确给出概率模型采样、DE/best/1 变异、交叉、插入局部搜索、Metropolis 接受、节点/边矩阵更新及终止输出顺序。 - 原始内容:在排列U_G上执行局部搜索,根据Metropolis准则判断是否接受新排列作为当前排列。 - 原始内容:更新算法的概率模型,即更新节点矩阵和边矩阵。 ```