多云环境下随机森林算法驱动的工作流成本优化调度

《Future Generation Computer Systems》：Random forest algorithm-driven workflow cost optimization scheduling in a multi-cloud environment

　　

摘要

多云计算环境中资源类型的高度异构性以及计费模型的复杂性和多样性，使得在严格截止时间约束下完成科学工作流的工作流调度问题更加复杂且具有挑战性。尽管现有研究在减少多云环境中工作流调度的完成时间方面取得了进展，但在满足截止时间的同时最小化调度成本方面仍存在诸多困难。因此，本研究提出了一种随机森林增强粒子群优化算法（RFPSO）。RFPSO算法通过随机森林模型实现资源分配的智能初始化，从而提高了寻找最优解的效率。此外，该算法设计了基于关键路径的反射边界约束机制和分层任务分配机制。这种设计确保了关键任务可以优先访问更高性能的计算机资源，从而有效保证工作流中的任务能够按时调度和完成。此外，通过局部邻域搜索机制提高了最优解的质量。在表观基因组学和Montage等科学工作流数据集上的实验结果表明，与现有的最先进方法相比，RFPSO平均降低了57.31%的执行成本。

引言

在当今快速发展的云计算领域，随着工作流规模不断扩大，单云服务提供商在资源供应能力和服务连续性方面的局限性日益凸显[1]。因此，整合多云服务提供商家资源的云环境已成为企业和研究机构满足工作流应用和工作负载多样化需求的核心计算基础设施[2]。在多云计算领域，Amazon、Google和Microsoft等主要云服务提供商能够向用户提供丰富灵活的一系列解决方案和服务；这一能力得益于其广泛分布的的计算和存储设施[3]。此外，当多云环境中的任务集面临严格的截止时间约束时，资源性能、定价和任务依赖关系的动态变化使得传统静态调度方法因其缺乏自适应灵活性而难以实现最优调度效果[2]。因此，具有全局搜索能力和良好适应性的元启发式算法受到了广泛关注。这些算法能够有效解决具有复杂约束的优化问题，并在满足工作流任务截止时间和提高资源利用率方面展现出显著的应用潜力[4]，[5]。然而，尽管这些算法凭借其强大的全局搜索能力在该领域得到了广泛应用，它们仍然面临资源利用率低和参数调节灵活性不足等挑战[6]，[7]。相比之下，机器学习算法可以利用动态优先级排序和抢占式任务调度机制，将学习任务分配给具有不同优先级的任务队列[8]。因此，高优先级任务可以优先访问计算资源，从而允许它们更早开始训练过程[9]。例如，Yang等人[10]提出了一种结合贪心优化与机器学习的模型。该模型利用多层感知器神经网络根据历史数据预测任务执行时间，有效减少了工作流的执行时间。此外，Hayat等人[11]使用随机森林（RF）算法评估机器学习预测器的错误率。结果表明，在边际错误率下，RF方法可以增强资源利用率并减少执行时间。

以RF为代表的集成学习模型因其卓越的性能已在各个领域得到广泛应用[12]，[13]。例如，Dinnillah等人[14]通过将孤立森林与RF结合提出了一种鲁棒的捕鱼检测方法，展示了RF在噪声环境中的有效性。同样，Amalia等人的研究[15]表明，RF在处理不平衡数据分布时表现出显著的稳定性。这一特性有效解决了多云调度场景中资源负载波动以及任务和资源分布不均的挑战，为RF在云调度优化中的应用提供了理论支持，为其在动态变化的云计算环境中使用奠定了基础。这为在具有动态资源变化的云计算环境中应用RF奠定了基础。尽管上述研究均将RF作为分类模型使用，但它们尚未深入探索RF与元启发式搜索算法的联合优化。在众多算法中，RF因其综合性能而脱颖而出，特别是在与粒子群优化（PSO）算法的联合优化中展现出显著优势。其主要特点包括：(1)基于异构资源特性和动态计费数据的任务成本预测方法，可有效生成低成本、高质量的初始解，从而提高PSO算法的解质量和收敛效率；(2)使用RF模型进行任务调度，由于其快速构建和低计算资源消耗，可满足云环境的实时性和高效资源利用需求。为此，本文提出了一种随机森林增强粒子群优化算法（RFPSO），旨在通过这种集成提高云计算任务调度的整体性能。该算法利用RF模型优化PSO的初始解，将粒子群的搜索范围从随机分布的解空间缩小到一组高质量解的集中集合，从而提高优化效率。同时，RFPSO引入群体多样性信息实现搜索参数的动态自适应调整，并设计了针对关键路径松弛度的分层优化机制，在确保任务完成截止时间的同时最大限度地减少工作流调度成本。本文的主要创新包括：

• 提出了一种基于RF的初始群体优化机制。该机制构建了一个整合任务计算特征和资源异构特性的RF回归模型，同时引入了超时成本惩罚评分机制来筛选高质量初始粒子。这解决了传统元启发式算法中随机初始化导致的初始解质量低和收敛速度慢的问题。该方法不仅显著提高了初始群体的整体质量，还有效加速了全局最优解的搜索过程。

• 设计了一种由群体多样性驱动的动态参数调整和反射边界约束策略。该策略量化了群体与质心之间的分散程度，动态调整惯性权重和学习因子的非线性衰减过程，以解决静态参数适应性不足以及粒子越界导致的无效搜索问题。同时，采用反射边界处理机制来纠正越界粒子的位置，显著提高了算法在多云异构环境中的搜索稳定性。

• 构建了一种基于关键路径松弛度的分层优化框架。该框架通过计算任务松弛度来识别关键路径任务，并采用平衡高性能和低成本的资源分配策略，以解决关键任务和非关键任务之间调度优先级模糊导致的成本浪费问题。通过整合局部邻域搜索技术，该方法有效避免了算法陷入局部最优，同时优先满足关键任务的截止时间约束，从而实现执行成本的全局最小化。

本文其余部分结构如下。第2节系统回顾了相关领域的研究，突出了当前的研究进展。第3节形式化地定义了所研究的问题，并系统地建立了工作流、资源、预处理、时间和成本的模型。第4节详细介绍了所提出的RFPSO算法。第5节对实验过程和结果进行了全面分析。第6节总结了研究并讨论了未来的研究方向。

相关工作

在多云环境中，由于计算资源的异构性和任务依赖关系的复杂性，在截止时间约束下的工作流调度在有限时间内优化具有挑战性[16]。当前研究主要集中于启发式、元启发式和基于机器学习的调度方法。启发式调度方法。早期研究经常采用基于经验建立规则的启发式算法来分配适当的资源。

系统模型与问题描述

本节主要阐述了工作流和资源的建模、预处理模型、成本模型以及优化问题的描述。表1详细介绍了本研究中使用的关键术语。

RFPSO算法

RFPSO算法将RF的预测优势与PSO的搜索能力相结合，为优化问题提供了从初始化到搜索全过程的全面增强解决方案。该框架由五个组件构成：基于优先队列的拓扑排序、粒子编码、RF初始化、自适应参数调整和局部搜索增强。RFPSO算法的具体实现在算法中详细说明。

实验与分析

本节建立了实验环境和比较方案，提供了实验设计和配置、基线算法、性能评估指标以及综合比较实验设计的详细信息。

结论

本研究提出了RFPSO算法以解决多云计算环境中由严格截止时间约束和资源性能、定价及任务依赖关系的动态变化所导致的任务执行时间不确定性挑战。RFPSO将随机森林与改进的PSO算法相结合，有效实现了截止时间约束下的工作流调度成本最小化。RFPSO引入了随机森林回归模型以辅助生成高质量的初始解。

CRediT作者贡献声明

张龙心：写作——审阅与编辑，写作——初稿，方法论，资金获取，形式化分析。杜丽丽：写作——审阅与编辑，写作——初稿，方法论。郭梦颖：方法论，数据整理。温志华：软件，方法论。欧阳爱佳：软件，数据整理。彭吉武：验证，方法论。李科勤：指导，方法论。

利益冲突声明

作者声明不存在任何已知的可能影响本文所报告工作的竞争性经济利益或个人关系。

致谢

作者感谢三位匿名审稿人提出的改进稿件的建议。本研究部分由湖南省研究生科研创新项目（项目编号：CX20251653, CX20261658）、中国湖南省自然科学基金（项目编号：2023JJ50204, 2024JJ7143）、中国湖南省教育厅科学研究基金（项目编号：25A0422）、国家重点研发计划（项目编号：张龙心|杜丽丽|郭梦颖|温志华|欧阳爱佳|彭吉武|李科勤 湖南工业大学计算机科学与人工智能学院，湖南株洲 412007）资助。