知识卡片
cDDE以概率采样搜索排列
压缩离散差分进化(cDDE)用于置换流水车间调度,解是工件排列。它用概率分布(由节点矩阵和边矩阵表示的概率模型)初始化并生成候选排列,同时保存两个排列:当前排列,以及迄今最好的精英排列。
每轮迭代:
- 从概率模型采样两个排列。
- 按 DE/best/1 变异:“best”表示以最优个体(这里即精英排列)为基础,“1”表示用一组差异去扰动它,差异来自两个采样排列;再按交叉概率交叉,得到候选。
- 对候选做基于插入操作的局部搜索。
- 用 Metropolis 准则决定是否接受:更好就接受,更差也以随温度下降的概率接受,见 [[较差候选仍可按温度概率接受]]。
- 更新节点矩阵和边矩阵,直到满足终止条件。
连续 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[输出精英排列]
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 0 . 4 . 1 基 于 差 分 进 化 算 法 的 置 换 流 水 线 调 度 · 查看原书依据
步骤4:在排列UG上执行局部搜索,根据Metropolis准则判断是否接受新排列作为当前排列。 步骤5:更新算法的概率模型,即更新节点矩阵和边矩阵。
参考来源
- 位置:《智能算法导论》第 10 章《10.4.1 基于差分进化算法的置换流水线调度》(源文件:`_epub-src/EPUB/xhtml/chapter10_0011.xhtml`)
- 结论依据:步骤明确给出概率模型采样、DE/best/1 变异、交叉、插入局部搜索、Metropolis 接受、节点/边矩阵更新及终止输出顺序。
- 原始内容:在排列U_G上执行局部搜索,根据Metropolis准则判断是否接受新排列作为当前排列。
- 原始内容:更新算法的概率模型,即更新节点矩阵和边矩阵。
```