知识卡片

普通读书笔记卡 · 3757.a

双种群分工搜索调度分配与排序

理解等级:高级

柔性车间调度同时包含两类决策:机器分配(每道工序交给哪台可选机器)与工序排列(各机器上工序的先后)。双种群 EDA(B-EDA)在迭代若干代后按分裂准则拆成两个种群,分别搜索这两类决策,满足合并准则时再合并,然后照常采样和更新概率模型。

多目标 P-EDA 则让两个子群用不同方式产生优势个体,按 Pareto 最优性能评价适应度,并加入基于关键路径的局部搜索。关键路径是决定最大完工时间的那条首尾相接的工序链,只有调整其上的工序才可能缩短总工期。子群分工有助于针对不同决策结构设计搜索步骤;原书只概述方案,不能据此断言这些方法普遍避免早熟或优于其他算法。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 9 . 4 基 于 分 布 估 计 算 法 的 调 度 问 题 · 查看原书依据

      Wang等[65-66]提出了求解柔性作业车间的双种群分布估计算法(B-EDA),在EDA进行若干代迭代后,通过分裂准则利用双种群分别对机器分配和工序排列进行搜索,再在满足合并准则的情况下进行种群合并,然后对概率模型进行采样和更新。针对多目标柔性作业车间调度问题提出了一种基于Pareto的有效分布估计算法(P-EDA),在Pareto最优性能的基础上进行适应度评价并建立相关的概率模型,同时将种群分为两个子群以不同的方式产生优势种群来避免早熟收敛的问题,并提出了基于关键路径的局部搜索策略。

    参考来源

    - 位置:《智能算法导论》第 9 章《9.4 基于分布估计算法的调度问题》(源文件:`_epub-src/EPUB/xhtml/chapter9_0007.xhtml`) - 结论依据:原文分别描述 B-EDA 对机器分配和工序排列的双种群搜索与合并,以及 P-EDA 的 Pareto 评价、双子群和关键路径搜索;卡片保留其分工机制并限定效果结论。 - 原始内容:通过分裂准则利用双种群分别对机器分配和工序排列进行搜索,再在满足合并准则的情况下进行种群合并,然后对概率模型进行采样和更新。