0%

A Cooperative Coevolution Hyper-Heuristic Framework for Workflow Scheduling Problem

  • 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 作为染色体个体的组成块,随机初始化个体,并计算其适应值(这里计算适应值时,是通过随机挑选另一个种群中的个体来组成启发式算法,然后对工作流进行调度,再根据适应值函数计算得到的)。

  • 交叉、变异

  • 选择:有可能选择父代,也有可能选择新生成的子代作为新一代种群中的个体,至于选择谁,要根据两个个体的适应值进行判断(这里计算适应值时,是通过挑选另一个种群中的最优个体来组成启发式算法,然后对工作流进行调度,再根据适应值函数计算得到的)。

---------------The End---------------