- The Cooperative Coevolution Hyper-heuristic Framework 包含两部分:
- The HBWS Algorithm,使用启发式算法来调度工作流,得到最终的调度解
- The CCGP Algorithm,生成最终的启发式算法给 HBWS 使用,我们看这篇论文的目的就是看这个算法它的实现细节是什么样的。
A Cooperative Coevolution Hyper-Heuristic Framework for Workflow Scheduling Problem
The CC Hyper-Heutistic Framework
The Cooperative Coevolution Hyper-heuristic Framework 包含两部分:
- The HBWS Algorithm
- The CCGP Algorithm
The HBWS Algorithm
该算法(The Heuristic-Based Workflow Scheduling Algorithm)使用启发式算法来调度工作流,它被设计为一种基于列表的调度方法,列表中罗列有一系列的启发式算法,每个启发式算法都包含两个阶段:
- 任务优先级确认阶段,用
代表对应的启发式算法在任务优先级确认时所使用的“函数” - 资源选择阶段,用
代表对应的启发式算法在资源选择时所使用的“函数”
举个例子,对于启发式算法
HEFT
,为 upward-rank 方法, 为 实际上,最后该算法只会使用一种启发式算法来调度工作流,而该启发式算法就是使用
The CCGP Algorithm
最终得到的启发式算法。- 任务优先级确认阶段,用
该算法的伪代码如下:
The CCGP Algorithm
- 该算法(The Cooperative Coevolution Genetic Programming Algorithm)用于得到最终更优的启发式算法。我们看这篇论文的目的就是看这个算法它的实现细节是什么样的。
- 在 HBWS 算法中已经说明,启发式算法包含两个阶段:任务优先级确认阶段
和资源选择阶段 ,所以在 CCGP 算法中,需要对这两个阶段对应的 “函数” 进行 CCGP 算法的 “作用”,以使得最终得到的启发式算法是由最优的 组成的。
The Framework Implementation
Function and Terminal Set
Function 和 Terminal 集合就是用来构建
和 的。 Function Set:
- Function Set 都大同小异,就是常见的数学运算的算子
Terminal Set:Terminal Set 需要根据研究的问题具体设计,因为这篇论文需要分别考虑
和 ,所以作者分别就 和 设计了两组 Terminal Set。
The CCGP Algorithm Implementation
CCGP 算法关于 GP 方面的具体实现细节基于另一篇论文《Self-Learning Gene Expression Programming》,在 SL-GEP 中,每一条染色体都包含一个 “main program” 和一系列自定义函数 “Automatically Defined Functions (ADFs)”。
既然使用了 GP,那肯定要涉及对染色体个体的适应值评估,本文所使用的适应值函数为
SLR(Schedule Length Ratio)
,。 初始化:使用前面的 Terminal Set、Function Set 作为染色体个体的组成块,随机初始化个体,并计算其适应值(这里计算适应值时,是通过随机挑选另一个种群中的个体来组成启发式算法,然后对工作流进行调度,再根据适应值函数计算得到的)。
交叉、变异
选择:有可能选择父代,也有可能选择新生成的子代作为新一代种群中的个体,至于选择谁,要根据两个个体的适应值进行判断(这里计算适应值时,是通过挑选另一个种群中的最优个体来组成启发式算法,然后对工作流进行调度,再根据适应值函数计算得到的)。