Running Noob

Do Something Meaningful

0%

Multi-Tree Genetic Programming Hyper-Heuristic for Dynamic Flexible Workflow Scheduling in Multi-Clouds

发表于 更新于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟
  • MTGP-HH 算法流程：
    1. 首先初始化种群，生成一系列的个体，每个个体都包含三棵树（对应三种选择规则，即任务选择规则、云选择规则、云中实例选择规则）。
    2. 对种群中的个体进行评估，选择其中优异的个体进行后续的操作。
      • 如何对种群中的个体进行评估呢？ -> 计算个体的适应值
      • 个体的适应值如何得到呢？ -> 根据个体的三棵树得到对应的公式（对树进行中序遍历），根据对应的公式，对任务、云、实例进行选择，就能得到一个调度解，将这个调度解应用到模拟环境中去，就得到了模拟执行后的结果，根据模拟执行的结果进行计算，就得到了个体的适应值。
    3. 对优异的个体，进行遗传操作（复制、交叉、变异），得到新个体（后代）。
    4. 对新个体重复 2、3 操作，直到达到循环终止条件，最终得到了一个最优个体，通过这个最有个体得到最终的调度解，就是算法输出的调度解。

Multi-Tree Genetic Programming Hyper-Heuristic for Dynamic Flexible Workflow Scheduling in Multi-Clouds

  • 虽然这是一篇关于多云环境下工作流调度的论文，但我们主要看的是这篇论文中的 Multi-Tree Genetic Programming Hyper-Heuristic（MTGP-HH） 算法是如何发挥作用的。

The Proposed Dynamic Workflow Scheduling Algorithm

  • MTGP 算法会自动生成进行工作流调度决策的三种规则：

    • 任务选择规则：用于选择要执行的下一个任务
    • 云选择规则：用于选择执行任务的云
    • 实例选择规则：用于选择云中具体执行任务的实例

  • MTGP 算法说到底是遗传算法，所以包含以下基本组成部分：

    • Population：种群中包含有多个个体
    • Individual：每个个体都包含三棵树（对应三种选择规则）
    • Evaluation：单个个体的适应值由三种选择规则联合计算得到
    • Evolution：种群中的个体之间相互交叉变异，来实现种群的进化

  • 总结一下 MTGP-HH 这个算法是怎么使用的：

    1. 首先初始化种群，生成一系列的个体，每个个体都包含三棵树（对应三种选择规则，即任务选择规则、云选择规则、云中实例选择规则）。
    2. 对种群中的个体进行评估，选择其中优异的个体进行后续的操作。
      • 如何对种群中的个体进行评估呢？ -> 计算个体的适应值
      • 个体的适应值如何得到呢？ -> 根据个体的三棵树得到对应的公式（对树进行中序遍历），根据对应的公式，对任务、云、实例进行选择，就能得到一个调度解，将这个调度解应用到模拟环境中去，就得到了模拟执行后的结果，根据模拟执行的结果进行计算，就得到了个体的适应值。
    3. 对优异的个体，进行遗传操作（复制、交叉、变异），得到新个体（后代）。
    4. 对新个体重复 2、3 操作，直到达到循环终止条件，最终得到了一个最优个体，通过这个最有个体得到最终的调度解，就是算法输出的调度解。

Individual Representation

  • 每个个体包含三棵树，每棵树对应一种选择规则。下面是个体的一个表示例子，Rule1 的树结构最终表示的式子就是 R1 = max{NKQ, TETQ} - UR / ET，对树进行中序遍历即可得到。

    • 对每种选择规则，都有一系列的 “terminals”，也就是 low-level heuristics（如图中的字母所示），我们根据不同规则（Rule1、Rule2、Rule3）所对应的树，根据作用集 function-set 得到最终的 low-level heuristics，再根据这个 low-level heuristics 去得到真正的调度解。

      • low-level heuristics 从何而来？

        根据工作流任务和多云系统的信息 state 设计而来，也就是说，low-level heuristics 需要根据你的研究问题，由你人为的来进行设计才行。

    • 这篇论文的 terminals 和 function sets 如下：

Population Initialization

  • 种群初始化阶段是用来初始化种群的个体的，由于用树状遗传编程来表示个体，所以这些初始化个体的形状到底是怎么样的：树的最大深度是多少？是一颗满二叉树还是非满二叉树？树的具体形状如何？都是需要考虑的。
    • 这篇论文使用 “ramped-half-and-half” 方法来对种群进行初始化，亦即，一半的个体是满二叉树的表现形式，另一半的个体是非满二叉树的表现形式。这篇论文设定了一个 maximum depth，一半个体的满二叉树的深度即为最大深度，另一半个体的非满二叉树的深度是随机的，不大于最大深度。但是非满二叉树的具体形状是什么样的？待定，还未解决
    • 这篇论文设置的 minimum / maximum depth 分别为 2 / 7。所有个体在任何时刻的 maximum depth 为 8。

Individual Evaluation

  • 这篇论文使用的是 “离散事件驱动的模拟过程” 来对个体的适应值进行 “计算”。也就是说，在工作流调度处于不同的事件阶段时，会采用不同的选择规则（任务选择规则、云选择规则、云中实例选择规则）对工作流进行调度，再把调度解应用到模拟环境中去，就得到了模拟执行后的结果，根据模拟执行的结果进行计算，就得到了个体的适应值。

Parent Selection

  • 使用 tournament selection 来选择产生后代的父代个体

Evolution

  • 复制：选择固定前 n 个最优个体到下一代的种群中去

  • 交叉、变异：

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