Running Noob

Do Something Meaningful

0%

Multi-Swarm Co-Evolution Based Hybrid Intelligent Optimization for Bi-Objective Multi-Workflow Scheduling in the Cloud

发表于 更新于 分类于
本文字数： 7.8k 阅读时长 ≈ 7 分钟
  • 在云环境下基于多群协同进化的双目标（执行时间和执行成本）多工作流调度的混合智能优化
  • 双目标：执行时间和执行成本
  • 多群协同进化：第一个种群关注执行时间最优化、第二个种群关注执行费用最优化、第三个种群关注两者之间的权衡最优化，这三个种群相互协作（协同进化）
  • 混合智能优化：结合 PSO、GA、SA 的优点，PSO 加快了收敛效率，GA 从 PSO 得到的非支配解中产生更多的可能为帕累托最优解的解；SA 避免陷入局部最优
  • 输出一组帕累托解

Multi-Swarm Co-Evolution Based Hybrid Intelligent Optimization for Bi-Objective Multi-Workflow Scheduling in the Cloud

  • 可以学习的点：

    1. 通过 SWC 技术将多工作流转换为一个大的单工作流。
    2. PSO 种群粒子的初始化：随机、HEFT、交叉。
    3. 对要评估的参数用归一化的方法。
    4. 三个种群之间相互协作：共同构建全局档案；每迭代 50 次，对全局档案贡献多的种群会将自己的信息分享给对全局档案贡献少的种群。

  • 在云环境下基于多群协同进化的双目标（执行时间和执行成本）多工作流调度的混合智能优化

    • 双目标：执行时间和执行成本
    • 多群协同进化：第一个种群关注执行时间最优化、第二个种群关注执行费用最优化、第三个种群关注两者之间的权衡最优化，这三个种群相互协作（协同进化）
    • 混合智能优化：结合 PSO、GA、SA 的优点，**PSO 加快了收敛效率，GA 从 PSO 得到的非支配解中产生更多的可能为帕累托最优解的解；SA 避免陷入局部最优**

introduction

  • 首先将工作流的任务调度在云服务器上时，要同时考虑执行时间和执行费用（双目标），这就涉及了多目标优化问题；除此之外，会有越来越多的用户（多用户）将其各种各样的工作流（多工作流）提交给云服务器进行处理，因此对云服务器的响应能力会有更高的需求。

    所以总的来说，这篇论文就是想要通过提出的调度优化策略（混合智能优化，所谓智能优化，就是基于元启发式算法的优化，包括PSO、GA、ACO、SA等，混合智能优化，就是将这些优化算法的优点结合起来），来对所提交的所有工作流进行合理的调度（多工作流调度问题），能对所有工作流的执行时间和执行成本之间的权衡进行最优化，同时还能满足所有用户的服务质量要求（如时间期限、预算等）。

Problem Formulation

multiple workflow model

  • 工作流集合

    • 每一个工作流都是一个有向无环图 DAG，

      • ，是工作流中任务的集合
      • ，工作流中任务之间的边
        • 表示任务和任务之间的依赖关系，任务是任务的直接前驱任务，任务是任务的直接后继任务。
        • 任务的直接前驱任务集合为，直接后继任务集合为
      • 是预定义的截止时间约束

    • 对于多工作流，可以利用 SWC(the Synchronization based Workflows Combination procedure) 来将其转换为一个大的工作流。

      L. Chen, X. Li, and R. Ruiz, “Resource renting for periodical cloud workflow applications,” IEEE Trans. Services Comput., vol. 13, no. 1,pp. 130–143, Jan./Feb. 2020.

resource model

  • 云计算资源，这是虚拟机的集合。
    • 每个虚拟机都有两个属性：
      1. ：计算处理能力，用 MFLOPS 来衡量
      2. ：单位时间 Δ 的租赁费用

Proposed Algorithm

Encoding and Initialization

  • 是粒子的位置向量，代表任务和虚拟机之间的映射关系。

    • 例如，表示将任务调度给虚拟机执行。

    因为应用了 PSO 算法，所以每个粒子还有它自己的速度向量。

  • 种群粒子初始化的操作：

    • ：为每个任务随机挑选虚拟机。
    • ：利用 HEFT 算法生成。
    • ：从中选择两个任务，这两个任务被调度给不同的虚拟机执行，然后将这两个任务被调度的虚拟机进行交换，生成。
    • ：将中被调度给计算速度最快的虚拟机的那些任务，重新调度给相对快类型的虚拟机，是为了将租赁费用纳入考虑。

    对于以上生成的九个粒子，为每个种群都随机挑选三个（因为有三个种群，所以刚好分完）。

    • 然后再在每个种群中加入其他一些初始化粒子，这些粒子的形成过程为：为每个任务随机挑选虚拟机执行。

  • 任务执行顺序的确定：

    1. 先计算任务的 Upward Rank，
      • 是任务的 Upward Rank，是任务的直接后继任务，是任务的直接后继任务集，是任务和任务之间的传输时间，是任务的执行时间。
    2. 然后根据任务的 Upward Rank 计算任务的截止时间
      • 是任务的 Upward Rank，即 entry task 的 Upward Rank。

    Q. Wu, F. Ishikawa, Q. Zhu, Y. Xia, and J. Wen, “Deadline-constrained cost optimization approaches for workflow scheduling in clouds,” IEEE Trans. Parallel Distrib. Syst., vol. 28, no. 12,pp. 3401–3412, Dec. 2017.

Multi-Swarm Co-Evolution(PSO)

  • 第一个种群关注执行时间最优化、第二个种群关注执行费用最优化

    Z.-H. Zhan, J. Li, J. Cao, J. Zhang, H. S.-H. Chung, and Y.-H. Shi, “**Multiple populations for multiple objectives: A coevolutionary technique for solving multiobjective optimization problems,**” IEEE Trans. Cybern., vol. 43, no. 2, pp. 445–463, Apr. 2013.

  • 第三个种群关注两者之间的权衡最优化，权衡值：

    • 是粒子的完工时间
    • 是粒子的执行开销
    • 是全局中最小的完工时间，是全局中最大的完工时间
    • 是全局中最小的执行开销，是全局中最大的执行开销

    越小的粒子权衡优化越好，越应该被保留。

  • 因为使用的是 PSO 算法，所以第 k 次迭代和第 k+1 次迭代中，第个种群中的第个粒子的位置和速度的关系式为：

    • $v_{h,s}^{k+1} = \omega·v_{h,s}^k+c_1r_1·(\hat{p}{h,s}-x{h,s}^k)+c_2r_2·(\hat{l}h-x{h,s}^k)+c_3r_3·(\hat{g}h-x{h,s}^k)$

    其中 $\hat{p}{h,s}是X{h,s}$ 自己的 best position，是第 h 个种群的本地引导解决方案，是第 h 个种群的全局引导解决方案。

    是惯性权重，是加速系数，是 [0,1] 之间的随机数。

    • 对于惯性权重和加速系数，有参考借鉴的文献：

      P. K. Tripathi, S. Bandyopadhyay, and S. K. Pal, “Multi-objective particle swarm optimization with time variant inertia and acceleration coefficients,” Inf. Sci., vol. 177, no. 22, pp. 5033–5049, Jun. 2007.

      • 第 k 次迭代的惯性权重：，即是在随着迭代次数 k 的增加而线性减小。

      • 第 k 次迭代的加速系数：

        可以看出，在随着迭代次数 k 的增加而线性减小，在随着迭代次数 k 的增加而线性增加。

      K 是迭代次数的最大值。

  • 在每一次迭代后，都会对每个种群中的每个粒子进行评估，对于每个种群自己来说，会将适应值高的粒子存储在本地档案中，即对进行更新。

    而三个种群是在并行地更新自己的的，同时这三个种群会一起去更新全局档案。

  • 由于对于不同的种群，它对全局档案的贡献是不一样的，会有比较好的种群和不那么好（inferior）的种群，所以要让好的种群能帮助 inferior 的种群找解，所以，每迭代 50 次，那些对全局档案贡献多的种群会将自己的信息分享给对全局档案贡献少的种群。

    ![](Multi-Swarm-Co-Evolution-Based-Hybrid-Intelligent-Optimization-for-Bi-Objective-Multi-Workflow-Scheduling-in-the-Cloud/swarm cooperation.jpg)

Elite Enhancement and Guiding Solution Update(GA)

  • 在根据 PSO 得到比较优异的粒子（即调度解）后，可以利用 GA 进一步扩大解空间，增加找到更优非支配解的概率。

    • 不过当中的调度解较多时，GA 迭代是比较耗时的，所以只对中较为 superior 的解进行遗传算法处理，即 do elite enhancement。

      当中的调度解的个数超过（是 Elite Enhancement Strategy (EES) 选择精英的最大数量）时：

      1. 先根据粒子的适应值对中的粒子进行排序，截取前个作为父集。
      2. 然后对父集进行遗传算法的操作（和 NSGA-Ⅱ 算法的操作一样）：选择、交叉、变异。
      3. 将遗传算法处理后生成的 offspring 添加到 offspring 集合中直到。
      4. 将合并到中。
      5. 评估中的粒子，计算其适应值，根据适应值排序。
      6. 将排序后的中的优异粒子添加到中，并删除中的非支配解，最终得到新的

  • 注意：这里的描述和算法略有出入……

  • 在三个种群的本地档案完成了更新和精英增强之后，它们的粒子（即调度解）会被添加到全局档案中，然后中的被支配解会被删除，由此来更新。

SA

  • 为了避免三个种群在 GA 阶段选择粒子后陷入局部最优，还要应用 SA 来进行处理：

    1. 根据适应值对新的中的粒子进行升序排序（不应该是降序排序吗？），将其中的第个粒子作为 inferior solution，记为
    2. 然后基于 Metropolis acceptance rule，有概率作为新的本地引导解 local guiding solution

    所以，种群第 k+1 次迭代的本地引导解为：

    • 其中是新的中的第个粒子，是新的中的第 1 个粒子。

      是之间的随机整数

      是种群的温度冷却率，是种群的当前温度（在每次迭代中根据降低）

      是之间的随机浮点数

      是种群第 k 次迭代时的本地引导解决方案

  • 同样，对于全局档案，也要进行 SA 处理：

    • 将中适应值最小的粒子作为种群的新的

FlowChart

  • 整个算法的流程图：

Experimental Results and Analysis

Experimental Settings

  • platform：workflowsim

  • workflow：Montage、Epigenomics、Cybershake、LIGO

  • datasets：因为这篇论文是将多个工作流合并为一个，所以在合并时，考虑了工作流的数量、工作流中任务的数量，以构建不同的数据集。

    这篇论文构建了五个不同的数据集：D-4-25, D-8-25, D-8-50, D-16-50 and D-16-100。

Parameters and Metrics

  • 参数的设置：用大量的实验来找到合适的值

  • 评价多目标优化问题中的调度解的指标：Hypervolume () 和

    • Hypervolume：通过计算 PF 中各解之间的封闭面积体积和一个通常选作最大目标值组合的参考点得到。Hv 的值越大，表明所得到的解越好。

      J. J. Durillo and R. Prodan, “Multi-objective workflow scheduling in Amazon EC2,” Cluster Comput., vol. 17, no. 2, pp. 169–189, Mar. 2014.

    • ：表示在 B 中，由 A 中的解决方案支配的解决方案在 B 中的比率。

      ，表示支配或等于

      表示在 B 中找不到被 A 中的解决方案支配的解决方案；表示对于在 B 中找到的每一个解决方案，都能在 A 中至少找到一个解决方案支配或者等于它。

      Z. Chen et al., “Multiobjective cloud workflow scheduling: A multiple populations ant colony system approach,” IEEE Trans. Cybern., vol. 49, no. 8, pp. 2912–2926, Aug. 2019.

Results and Analysis

  • 实验结论：

    1. 与 NSGA-Ⅱ 和 ECMSMOO 相比，MCHO 在寻找非支配解上要明显优于它们，尽管在工作流规模较小时 MOACS 能和 MCHO 有相近的表现，但是随着工作流规模的增大，MCHO 的优势显得越来越明显。 -> 通过非支配解的图

    2. 通过对 Hv 以及的分析也可以得到上面 1 的结论，通过来直观地感受 MCHO 相对于其他算法所提升的百分比。 -> 通过的图

      ，{NSGA-II, ECMSMOO, MOACS}

      V. Arabnejad, K. Bubendorfer, and B. Ng, “Budget and deadline aware e-science workflow scheduling in clouds,” IEEE Trans. Parallel Distrib. Syst., vol. 30, no. 1, pp. 29–44, Jan. 2019.

      • 这里并没有直接对比 Hv 的值，而是转化为对比百分比。

    3. 通过的值可以得到，由 MCHO 得到的解能很大程度上地支配由 NSGA-Ⅱ 和 ECMSMOO 得到的解，且在工作流规模较大的时候（D-16-100）， 由 MCHO 得到的解也能支配 MOACS 得到的解。

    4. MCHO 的运行时间要优于 MOACS，但是要劣于 NSGA-Ⅱ 和 ECMSMOO。

    总结：MCHO 不管是在最优化表现上还是在运行效率上，都要优于 MOACS；尽管 MCHO 需要比 NSGA-Ⅱ 和 ECMSMOO 更多的运行时间，但是它在最优化表现上要远远大于后两者。

result and discussion

  • 通过基于多群协同进化的混合智能优化，将各种优化算法的优点结合了起来，**PSO加快了收敛效率，GA使得能更近地接近帕累托前沿PF（对于多目标问题的非支配解的最优情况）；SA避免陷入局部最优**。

    MCHO的实验效果优于NSGA-Ⅱ、ECMSMOO和MOACS。

  • 未来考虑方向：进一步往三目标最优化问题考虑，除了考虑执行时间和执行成本，还考虑能源消耗。

Question

  • 插入到种群中的预定义的解决方案从何而来？

  • 三个种群之间的关系是什么？

    第一个种群关注执行时间最优化、第二个种群关注执行费用最优化、第三个种群关注两者之间的权衡最优化，这三个种群相互协作（协同进化），共同构成全局非支配解空间。

  • elite enhancement strategy是什么？

    对于PSO算法得到的具有 “elite knowledge” 的非支配解，通过 GA 产生更多的可能为帕累托最优解的解，即为精英增强策略。

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