【论文】略读笔记71-前沿-多进化算法结合

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

2022 年 北理工大学团队 发表于 CCF-A 类期刊 TPDS。

🎯需求

• 许多科学应用都可以很好地模拟为大规模工作流。云计算已成为托管和执行这些工作流的合适平台。
  • 科学应用通常以工作流的形式呈现。
    • 它们通常规模庞大，包含数百或数千个关系复杂的任务，这就进一步要求具有强大计算和存储能力的庞大基础设施来处理这些应用。
  • 如今，云计算因其弹性和异构性而成为一种前景广阔的分布式计算图。
    • 在云计算中，用户可以按需动态请求服务，而无需自行购买和维护本地物理机器。因此，越来越多的科学工作流正在过渡到或已经转移到云平台上执行。
• 近年来，工作流调度备受关注。
  • 云计算中的工作流调度是将工作流中的每个任务分配给合适的资源，以满足某些性能标准。云服务提供商（CSP）可以以不同的价格为不同能力的用户提供各种几乎无限的虚拟化资源。
    

🚧现状

• 然而，由于云服务提供商必须为具有不同 QoS 需求的多个用户提供服务，因此对具有不同 QoS 需求的多个应用进行调度极具挑战性。
  • 通常情况下，租用更多资源或更昂贵的资源会缩短执行时间，但会增加成本。因此，由于云计算中的按使用付费模式，工作流调度的时间和成本都备受关注，这样的调度问题可以被模拟为多目标优化问题（MOP）。
  • 在现实调度情况下，会有越来越多的云用户在一段时间内向云提交各种工作流，这对数据中心的响应能力提出了更高的要求。因此，云数据中心必须以批量/并行模式处理多个工作流，以满足多个用户的 QoS 要求。
  • 因此，很难找到一种合适的多工作流调度算法，以优化所有工作流的执行时间和成本，同时确保每个用户所需的 QoS 要求。
• 受人类智慧、社会或生物实体自然现象的启发，依赖于随机搜索技术的智能优化是一种广泛应用于处理MOP的方法。
  • 它往往具有突出的全局优化能力和较强的通用性，适合迭代进化。
    • 近年来，粒子群优化（Particle Swarm Optimization，PSO）、遗传算法（Genetic Algorithm，GA）、模拟退火（Simulated Annealing，SA）等在解决云计算工作流调度问题中发挥了主导作用。
      • PSO 具有强大的社会学习机制，收敛速度快，而且易于实现，只需调整很少的参数。然而，PSO 在演化过程中很容易陷入局部最优状态，因此缺乏局部搜索技术。
      • SA 能够通过概率降低解的质量来解决陷入局部最优的问题，但它缺乏快速收敛能力。
      • GA 在多样性保持方面表现良好，但收敛速度较慢，找到全局最优的时间也比其他算法长。

🛩创新

• 为了克服上述缺点并充分发挥它们的优势，本研究提出了一种基于多群协同进化的混合智能优化（MCHO）算法，用于多工作流调度，在满足每个工作流的截止日期约束的同时，最大限度地减少总工作时间和成本。
  • 1）首先，我们设计了一种基于MPMO框架的多蜂群协同进化机制，采用三个蜂群来充分搜索各种精英解决方案，其中第一蜂群和第二蜂群分别专注于工期和成本的优化，而新引入的第三蜂群则兼顾两个目标，使三个蜂群集中搜索不同的非优势解，增加了精英个体的多样性。
  • 2）其次，为了提高全局搜索和收敛性能，我们在PSO粒子群优化器的更新过程中嵌入了局部和全局指导信息，引入全局档案和局部档案中的精英个体，分别对粒子进行全局和局部引导；并开发了一种群合作技术，进一步提高了其收敛性和全局搜索能力。
  • 3）第三，我们提出了一种基于遗传算法的精英增强策略，即对每个蜂群局部档案中的优势个体进行遗传操作，以利用更多的精英个体，扩大找到更多解的可能性，从而提高解的质量；并应用模拟退火的 Metropolis Acceptance 规则更新每个蜂群的局部指导解，通过概率接受局部档案中的劣质个体来更新局部指导解，以防止蜂群在早期阶段陷入局部最优，从而帮助 MCHO 摆脱局部最优状态。

📊效果

• 大量实验结果表明，MCHO 的分布式非优势解优于最先进的调度算法。
  • MCHO 的性能通过与 NSGA-II、ECMSMOO 和 MOACS 这三种同类算法的比较得到了验证。
  • 最终结果表明，MCHO 在解决方案的数量和优势方面都优于同行。它获得的 PFs 明显优于 NSGA-II 和 ECMSMOO。虽然 MOACS 与 MCHO 在小规模数据集上的表现相似，但我们的方法所得到的解决方案在 MOACS 为大规模数据集找到的解决方案中占据了多数优势。因此，MCHO 可以有效地解决双目标多工作流调度问题。

⛳️未来机会

• 作为未来的工作，我们计划：
  • 1）处理更复杂的问题场景，如具有各种资源供应模式的混合云；
  • 2）开发我们的算法，以应对考虑能耗的三目标优化问题；
  • 3）研究如何将基于关键路径的启发式算法产生的初始解添加到我们的算法中；
  • 4）在包含更多类型、更大规模科学工作流的数据集上评估我们的算法；
  • 5）在优化多目标工作流调度时应用基于支配关系或分解的方法；
  • 6）研究其他更有效的局部搜索方案，以提高 MCHO 的性能。

🧠疑问

1. 根据摘要，需求是多用户异构QoS工作流，看起来没有很特别的挑战。挑战具体是什么？如何更好地定位需求提出挑战？
   1. 同时存在大量用户的大量异构复杂工作流请求，同时优化困难。（感觉听起来没有很难，没体现出定量或定性的特点）
   2. 现有元启发式算法有陷入局部最优或求解效率低的问题，因此需要兼顾二者。（怎么样算高？怎么样算低？元启发式算法整体都很慢，如何判断是否满足需求？）
2. 没说清楚挑战的结果就是，看起来仅仅把不同方案杂揉在一起，没感觉到很难、很新、很亮。也没有针对大规模复杂工作流的特点设计独特机制。

---

---

• 希望这篇博客对你有帮助！如果你有任何问题或需要进一步的帮助，请随时提问。
• 如果你喜欢这篇文章，欢迎动动小手 给我一个follow或star。

🗺参考文献

[1] H. Li, D. Wang, M. Zhou, Y. Fan and Y. Xia, “Multi-Swarm Co-Evolution Based Hybrid Intelligent Optimization for Bi-Objective Multi-Workflow Scheduling in the Cloud,” in IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 9, pp. 2183-2197, 1 Sept. 2022, doi: 10.1109/TPDS.2021.3122428.