# 柔性3C制造车间全流程协同调度系统

**Repository Path**: zhr530629/LEA-TASE

## Basic Information

- **Project Name**: 柔性3C制造车间全流程协同调度系统
- **Description**: 这项研究解决了HCPS中的能量最小化任务调度问题。 它包括三个子问题：处理器分配、任务排序和确定处理器的执行频率。 我们提出了一种学习辅助进化算法 (LEA)，以高效地找到可靠和高质量的解决方案。
- **Primary Language**: Matlab
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2024-03-28
- **Last Updated**: 2025-06-17

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 柔性3C制造车间全流程协同调度系统-基于复杂系统调度的能量最小化辅助学习进化算法


## 主要用到的算法
无监督学习，深度强化学习，智能智能优化算法

## 介绍
这项研究解决了HCPS中的能量最小化任务调度问题。 它包括三个子问题：处理器分配、任务排序和确定处理器的执行频率。 我们提出了一种学习辅助进化算法 (LEA)，以高效地找到可靠和高质量的解决方案。 其中，通过端到端的自监督学习，建立了一个双向长短期记忆网络嵌入式自动编码器模型。 该模型提取了三个强耦合子问题之间的相互联系，有助于在低维特征空间中进行有效的全局搜索。 该模型构建了一个并行框架，其中有两个共同进化的子群，一个使用自动编码器，另一个在原始搜索空间中进行定期评估。 为了平衡 LEA 的探索和利用能力，我们采用了一种基于深度强化学习的方法，并利用一种新颖的基于反馈控制的奖励函数来构建搜索算子选择方案。 它为两个共同进化的子群选择合适的搜索算子组合。 数值实验证明，LEA 在合理的时间内找到高质量计划方面优于最近开发的几种竞争方法。

## 挑战和动机
在线调度通常需要在五分钟内完成调度，快速启发式算法生成的日程表通常性能有限，基于种群的进化算法在解决中大型问题时需要耗费大量的计算时间。所以我们在考虑，能否可以在不降低求解质量的前提下尽量的缩短计算时间？本研究旨在通过解决以下两个问题来回答这个问题：
1) 如何揭示处理器分配、任务排序和确定处理器频率等强耦合子问题之间复杂的相互依存关系？
要有效解决 ETSP，必须解决所有三个相互关联的子问题。前人提出了各种优化框架，用于综合调度问题，以获得全局最优结果。然而，有些方法，例如分支与边界法，可能非常耗时。其他方法则孤立地处理每个子问题，或者依赖于特定问题的先验知识。近期开发的一种自动编码器嵌入式优化算法有望通过将原始解决方案映射到低维空间来管理这些复杂性，从而促进高质量子解决方案的生成。
尽管如此，最初的自动编码器嵌入式优化算法针对的是连续优化问题，正如中指出的，在自动编码器中采用全连接层会阻碍组合优化的特征学习，尤其是在处理二进制决策变量的非二进制编码值时。为了解决这一局限性，我们提出了一种嵌入双向长短期记忆网络的自动编码器（BLA），它能捕捉 ETSP 中决策变量之间的相互依赖关系。具体来说，我们首先使用一组长短期记忆单元将二进制决策变量转换为，然后使用自动编码器将嵌入压缩为低维潜在表示，最后我们在低维空间中执行一些网络嵌入式搜索算子，生成子代解决方案。
2) 如何为原始解空间和低维特征空间选择有效的搜索算子？
从另一个角度看，使用 BLA 生成低维潜在表示可以被视为一种创新的编码方法。与需要特定问题定义和明确物理意义的传统编码方法不同，低维潜在表示并不对应于时间表。它必须通过用于 BLA 的解码器在原始空间中重建为解决方案。这使得潜表征更像是一种机器学习编码技术，而非人类可以轻易理解的技术。因此，元启发式的传统搜索算子可能不适合 LEA。DRL通过揭示当前种群的状态，为动态识别适当的算子提供了一种有前途的解决方案。因此，本研究提出了一种基于 DRL 的超启发式，用于在原始空间和低维空间中选择合适的算子。
应用 DRL 进行算子选择还面临其他挑战。元启发式在很大程度上依赖于其群体的随机运动。因此，相同的状态-操作对可能会观察到不同的结果，导致误导性的奖励信号，从而需要手动调整奖励函数。此外，进化算法的收敛速度并不一致，通常是初始迭代快于后期迭代。静态奖励函数可能会阻碍长期奖励的最大化。因此，我们提出了一种新颖的基于反馈的奖励函数，以稳定 DRL 学习过程。

## 主要贡献
本研究提出了一种学习辅助进化算法（LEA），可有效且高效地解决 ETSP 问题。它的独特贡献有两方面：
1）通过无监督端到端学习建立了一个新颖的 BLA 模型，以捕捉三个强耦合子问题之间的内在联系。它允许 LEA 在信息丰富的低维空间中有效地进行全局搜索。 
2) 提出了一种基于 DRL 的自适应迭代搜索算法，用于在原始解空间和低维解空间中选择适当的搜索算子。它包括一个基于反馈的奖励函数，以平滑处理 DRL 的学习过程。

## 有向无环图（DAG，Directed Acyclic Graph）
ETSP 中的所有任务都可以用 DAG 来描述。 例如，下图显示了一个有 9 个任务的示例，其中任务 8 有两个前置任务，这意味着它只能在任务 3 和任务 4 完成后才能执行。 如果链接的两个任务在不同的处理器中执行，则指示符上的数字表示通信时间。 例如，在不同处理器上执行任务 1 和任务 4 需要 8 个单位的通信时间。

![DAG 示例：每个粗体数字代表一个任务，直接弧上的规则数字表示两个不同处理器之间的通信时间。](Main_code/DAG.png)

## LEA的流程框架
与传统的进化算法不同，LEA 集成了两种机器学习技术，即基于自动编码器的无监督学习方法和基于 DRL 的算子选择方案。 这种组合形成了一个并行框架，其中包含两个共同进化的子种群。 其中一个子群使用 BLA 将高维解压缩为低维表示以便进行全局探索，而另一个子群则遵循标准的进化过程。 DRL 在这两个子群中选择适当的搜索算子，作为一种超启发式。 如下图所示，LEA 包括离线训练和在线执行两个阶段。前者使用历史数据来训练 BLA 和 DRL 选择器，而在线阶段则使用这些训练好的模型来搜索高质量的时间表，详见下面的英文伪代码。

 **LEA的整体流程框架：** 

![framework](Main_code/framework.png)

 **LEA的伪代码：** 

![伪代码](Main_code/%E4%BC%AA%E4%BB%A3%E7%A0%81.png)

## BLA 模型
据我们所知，ETSP 中的各种高质量解通常都有类似的高拟合和低阶子解。识别和保留这些子解是有益的，但由于决策变量之间的强耦合性，识别和保留这些子解具有挑战性。为了解决这个问题，我们提出了学习决策变量间高拟合组合的 BLA。它可以降低丢失有价值子方案的风险，从而提高 LEA 的全局搜索能力。

训练数据库： 引入 BLA 是为了学习序列数据（即 yS 和 yA），类似于自然语言处理中使用的技术。从他们的进步中汲取灵感，我们放弃了直接从完整解决方案中形成训练数据集的做法。相反，我们引入了一种基于规则的方法，将 yS 和 yA 切割成它们的子解，从而帮助 BLA 学习更多局部信息。
首先，利用 LEA 早期迭代中的历史最佳解法和使用HEFT规则获得的解法对 BLA 进行训练。然后，采用三种基于规则的方法生成子解决方案： 例如，如果处理器 2 的任务顺序为 {7, 3, 4}，则该相对执行顺序将作为 yS 的子解决方案。2) 生成基于频率的任务分配方案的子解决方案。例如，如果在历史最佳解决方案中，任务 2 和 3 经常被分配给处理器 3，则会为 yA 生成一个子解决方案 {d, 3, 3, d, - - , d}，其中 d 代表一个填充标记。请注意，我们在这里使用填充标记 d 是为了保持 BLA 输入的长度不变。3) 通过随机选择 v 个任务（其中 v∈ {2, ... , n - 1}）进行任务分配或排序方案，形成子解决方案。例如，如果选择了任务 3、4、8 和 10，它们的执行序列为 {8, 4, 3, 10} in ，那么这个序列就会被用作训练的子解决方案。这些基于规则的方法旨在丰富和充实用于训练 BLA 的数据集。

网络结构：如下图所示，BLA 包含两个主要部分，即 BLA 编码器和 BLA 解码器。选择这种方法是因为任务序列是由一系列不重复的整数表示的，因此需要一个能够捕捉变长序列的模型。与传统的自动编码器不同，Z′ 并不直接重建为其原始形式。相反，我们基于 DRL 的运算符选择方案 O 会选择一个搜索运算符 OB，用来从 Z 生成变异后代 Z′。
BLA-Decoder 的目的是将 Z′ 重构为子代方案 y′。如下图所示，处理器分配方案（yA′）的 BLA-Decoder 输出由 m 维向量组构成。软最大层用于将它们转换为整数输出。例如，如果使用 BLA 解码器生成的与任务 1 相对应的输出向量为 < 0.02, 0.86, 0.13 >，则我们使用其最大值的索引作为 yA′ 的第一个元素，即由于 0.86 是最大值，因此也可以生成任务序列子解决方案 yS′。

![BLA模型](Main_code/BLA.png)


## 基于深度强化学习（DRL）的操作算子选择策略
将 DRL 用于运算符选择的一个关键挑战是将运算符选择问题转化为 DRL 问题。 按照 DRL 的原则，我们有以下任务：状态表示、行动构建和奖励定义。

 **DRL的状态空间特征：** 

![DRL的状态空间特征](Main_code/%E7%8A%B6%E6%80%81.png)

DRL的动作：
搜索算子通常侧重于执行广泛的局部搜索，而在其中，它们应帮助 LEA 识别有前途的解决方案空间，即富含高质量子解决方案的解决方案空间。为了实现这一目标，我们提出了一种基于算子的行动，即修改现有的优化算法，并根据各种优化原理对其进行重构。通过大量的先期运行和分析，我们选择了 20 种合适的算子组合，专门用于处理 ETSP。主要算子包括：i) 单点交叉和多点变异算子；ii) 两点交叉和多点变异算子；iii) 迭代局部搜索算子；iv) 模拟退火算子；v) 改进的麻雀搜索算子；vi) 基于最早完成时间规则的算子；vii) 霜冻优化算子和 viii) 差分进化算子。 在 DRL 的每一步训练中，我们都会选择一个用于低维特征空间的算子和一个用于原始解空间的算子。

 **DRL 的流程框架：** 

![DRL](Main_code/DRL.png)


## 测试实例定义
我们的数值模拟采用了一组基准方案。 它可以在 https://sourceforge.net/projects/taskgraphgen 上找到。 这些场景具有不同的问题规模，从 9 个任务到 252 个任务不等。 一个任务最多可以在 16 个处理器中执行，最多有 42 个前处理器。 根据同行的的建议，DAG 应用程序的截止时间被设定为ˆD = 1.3 - ˆC，其中ˆC 是通过 HEFT 规则生成的时间表的时间跨度。

## 敏感性分析
 **参数DB的敏感性分析：** 
BLA 的潜在维度（用 DB 表示）对其重建能力起着至关重要的作用。下图显示了 DB 变化的影响。 可以看出，过小或过大的值都不理想。 过小的 DB 值可能会限制模型从原始数据中捕捉足够信息的能力，从而可能导致重要特征的丢失。 相反，过高的 DB 值可能会产生精确的输入重构，但却无法有效捕捉决策变量的基本特征。 根据我们之前的运行情况，一个合适的选择是 DB = ⌈0.25 - n⌉，其中 n 是任务数。

 **不同DB在实例SFT01上表现的结果：** 

![DB](Main_code/DB.png)

 **参数LR的敏感性分析：** LEA的重建能力受学习率 LR 的影响。下图总结了不同 LR 值的影响。学习率太小会导致 LEA 容易陷入局部最优状态，而学习率太大则会导致参数更新过多，从而偏离最优解。根据我们之前的运行情况，LR = 0.0003 是一个合适的选择。

 **不同LR在实例SFT04上表现的结果：** 

![学习率](Main_code/LR.png)

 **参数γ的敏感性分析：** 折扣因子用 γ 表示，用于衡量未来回报的重要性。我们分析了不同 γ 的影响，如下图所示。由于元启发式所需的迭代次数较多，我们选择了相对较大的 γ = 0.95。

 **不同γ在实例SFT07上表现的结果：** 

![折扣因子](Main_code/%E6%8A%98%E6%89%A3%E5%9B%A0%E5%AD%90.png)

## 消融实验结果
 **消融实验：BLA模型的作用** 

为了证明 BLA 的有效性，我们将基本遗传算法（GA）与其变种 BLA-GA 进行了比较。BLA-GA 的设计目的是首先将原始种群压缩到低维空间，然后在不执行任何额外运算的情况下直接重建原始种群。在有限的 360 秒 CPU 时间内，两种算法都独立运行了 10 次，结果如下图所示。
下图显示，BLA-GA 比 GA 找到了总能耗更低的解决方案。 从理论上讲，在不做任何进一步处理的情况下，直接从自动编码器的压缩结果中重新构建一个解，应该能得到压缩前的解。不过，由于 BLA 使用高质量的解决方案作为训练数据，因此会保留一些高拟合度和低阶子解决方案的记忆。 因此，使用 BLA 可以降低丢失有价值子方案的风险，从而提高全局搜索能力。

 **GA 和 BLA-GA 的结果（柱状图表示能耗，折线图表示其标准偏差）：** 

![消融实验-BLA](Main_code/BLA%E6%B6%88%E8%9E%8D.png)

 **消融实验：基于深度强化学习（DRL）的操作算子选择策略的作用** 

在本节中，我们将通过比较两种算法（即Random-OS 和 DRL-OS）来研究基于 DRL 的算子选择方案 O 的作用。 前者在低维特征空间和原解空间中随机迭代选择算子，后者则使用 O 来选择这些算子。 这两种算法的评估参数相同。 下图显示了 Random-OS 和 DRL-OS 在不同问题实例中的结果。从下图中可以看出，DRL-OS 和 Random-OS 在小规模实例中得到的解的总能耗相当，因为小规模实例很容易通过这两种算法找到接近最优的解。然而，在中大规模实例中，DRL-OS 的总体性能明显优于 Random-OS，这意味着 DRL-OS 可以为种群演化选择更好的算子。

为了深入研究 DRL-OS 优于Random-OS 的原因，我们分析了两种算法的演化过程。 最佳适配值的收敛过程如图能耗降低曲线所示，适配值的标准偏差如图标准差迭代曲线所示。可以看出，DRL-OS 的收敛速度比Random-OS 快，在初始迭代过程中，DRL-OS 的适应度值比Random-OS的适应度值波动更大。随后，DRL-OS 与其同类算法相比，显示出较小的适应度值差异，并侧重于广泛的局部搜索。 总之，我们基于 DRL 的算子选择方案通过利用特定问题的知识，帮助 LEA 减少了 "无效搜索"，显著增强了其开发能力。

 **Random-OS 和 DRL-OS 的结果（柱形图表示能耗，折线图表示其标准偏差）：** 

![Random-OS 和 DRL-OS 的结果](Main_code/DRL-OS.png)

**Random-OS 和 DRL-OS 的能耗降低曲线：** 

![能耗降低曲线](Main_code/%E9%99%8D%E4%BD%8E%E6%9B%B2%E7%BA%BF.png)

**Random-OS 和 DRL-OS 的标准差迭代曲线：** 

![std](Main_code/std.png)


## 算法性能比较
在本节中，我们将介绍通过应用我们提出的方法及其同类方法（即 GUROBI 优化器、GA、基本迭代局部搜索（ILS）、E-HEFT 、强化辅助 ILS（RAILS 等算法，这些算法要么被广泛认为是最先进的技术，要么在最近的研究中被证明在 ETSP 上表现有效。将 LEA 与这些广受赞誉的算法进行比较提供了一个稳健的评估框架，展示了 LEA 与当前最佳算法的优缺点。 并且每种算法独立执行 10 次。另外如果计算时间超过一定的范围界限，HCPS 必须暂停目前的程序，等待随后的调度。因此，我们将超小型、小型、中型和大型场景的停止条件分别设置为 10 秒、30 秒、200 秒和 500 秒。 为了验证 LEA 发现的总能耗与 LGWO 发现的总能耗在统计上是否有显著差异，我们进行了 Wilcoxon-signed-rank 检验。 结果详见表 I 和表 II。

虽然 GUROBI 在小规模实例上表现出色，但它在中大规模实例上搜索解决方案所花费的时间却令人难以接受。 GUROBI 在 20 小时内找到的 MFT01 的下界和上界分别为 [724.74, 767.32]。 因此，我们将其结果作为高质量的低边界，尽管启发式规则（即 E-HEFT）可以快速找到可行解，但在小型和大型实例中，LEA 显著提高了平均适配值，比其分别提高了 50.40% 和 63.91%。 与 ILS、GA、RAILS、LGWO 和 LCS 相比，LEA 的平均适应度值分别提高了 35.62%、43.70%、32.98%、25.16% 和 22.11%。原因在于我们基于 DRL 的算子方案能够处理不同状态的群体，例如，在搜索过程的后期阶段，对众多解决方案进行大量突变往往会适得其反。 这种方法有可能导致群体忽略潜在的高质量解决方案，从而导致 "无效搜索"。 此外，除了 SFT01-02、SFT04 和 SGS01-SGS03、SGS06、LGS04 外，LEA 和 LGWO 在几乎所有实例中都存在显著的统计学差异，而大规模实例的 p 值则非常小。这是因为我们提出的 BLA 模型可以帮助 LEA 有效地执行全局搜索，找到并保存一些高拟合度和低阶子解决方案。因此，LEA 可以找到相对高质量的解，而无需承担过多的计算负担，因此特别适用于求解中型到大型的ETSP。

 **表I 在中小型基准情景下，对 GUROBI、E-HEFT、ILS、RAILS、GA、LGWO、LCS 和 LEA 进行比较** 

![中小型实例](Main_code/%E5%B0%8F%E5%9E%8B%E5%AE%9E%E4%BE%8B.png)

**表II 在大型基准情景下，对 GUROBI、E-HEFT、ILS、RAILS、GA、LGWO、LCS 和 LEA 进行比较** 

![大型实例](Main_code/%E5%A4%A7%E8%A7%84%E6%A8%A1.png)

## 结论
本研究考虑了HCPS中出现的能量最小化任务调度问题。通过考虑截止日期约束和处理器的动态频率调整，我们建立了一个混合整数编程模型。为了高效地获得高质量的调度结果，我们提出了基于BLA和算子选择方案的LEA。它的BLA提取了决策变量之间的潜在关系，能够在低维空间中进行有效的全局搜索。它的 DRL 具有基于反馈控制的奖励函数，用于学习最优算子选择，目的是在原始解空间和低维解空间中找到合适的搜索算子。LEA 采用平行框架，有两个共同进化的子群：一个使用 BLA，另一个遵循传统的进化过程。两个子群之间的信息交流使 LEA 能够在探索和利用之间取得平衡。 仿真结果表明，LEA 的性能优于同类竞争者。


## 所用到的软件或库
matlab
强化学习库