[Paper] PHWSOA：一种基于Pareto的混合鲸‑海鸥调度用于云计算中的多目标任务

Source: arXiv - 2512.09568v1

概览

本文提出了 PHWSOA，一种将鲸鱼优化（WOA）和海鸥优化（SOA）相结合的混合元启发式算法，并引入基于帕累托的多目标处理。通过同时优化完工时间（makespan）、虚拟机负载均衡和成本，作者旨在为云运营商提供比传统单指标方法更平衡、更贴近实际的调度器。

主要贡献

• 混合算法设计 – 将WOA的全局搜索与SOA的局部开发相融合，克服各自的弱点。
• 基于帕累托的多目标框架 – 使用支配排序同时优化三个相互冲突的目标（完工时间、负载均衡、经济成本）。
• Halton序列初始化 – 用低差异采样为种群提供种子，以提升多样性并加快收敛。
• 帕累托引导的变异 – 基于非支配解注入多样性，避免过早停滞。
• 并行执行与动态VM负载再分配 – 加速搜索过程，并在运行时持续平衡工作负载。
• 大规模CloudSim评估 – 使用NASA‑iPSC和HPC2N真实轨迹，展示相较于最先进基线（WOA、GA、PEWOA、GCWOA）可实现最高 72 % 完工时间缩短、37 % 更佳负载均衡 与 24 % 成本节约。

方法论

1. 种群播种 – 与随机启动不同，算法从Halton序列中抽取初始候选调度，使点在搜索空间中均匀分布。
2. 混合搜索算子
   • 鲸鱼阶段：模拟泡网捕食，以广泛探索VM‑任务分配。
   • 海鸥阶段：采用“群聚”更新规则，对有前景的调度进行局部微调。
3. 帕累托排序 – 对每个候选在三个目标上进行评估，非支配解构成当前的帕累托前沿。
4. 帕累托引导的变异 – 靠近前沿的解会受到有针对性的扰动，鼓励对未充分探索的区域进行探索。
5. 并行评估 – 所有候选的适应度计算并行执行（利用多核CPU），显著降低墙钟时间。
6. 动态负载再分配 – 在仿真过程中，若某VM出现过载，任务会依据当前帕累托前沿迁移至利用率较低的VM，以保持平衡。

结果与发现

• 完工时间：PHWSOA 相比经典WOA和GA可将总执行时间缩短最高 72.1 %。
• 负载均衡：VM利用率的方差下降 36.8 %，表明任务在云池中的分布更均匀。
• 成本：通过缩短执行时间并减少资源过度配置，算法实现 23.5 % 的费用节约。
• 收敛速度：并行处理和Halton初始化将达到近最优前沿所需的代数减少约 30 %。
• 鲁棒性：在两套真实工作负载（NASA‑iPSC、HPC2N）上，PHWSOA 始终优于基线，显示出良好的泛化能力。

实际意义

• 云编排平台（如OpenStack、Kubernetes）可将PHWSOA 作为插件调度器嵌入，实现自动平衡延迟、资源使用和计费。
• DevOps流水线在为批处理作业（CI构建、数据处理）临时启动VM时，可在无需人工调参的情况下获得更快的周转和更低的云支出。
• 边缘‑云混合部署受益于动态负载再分配组件，能够根据实时负载在边缘节点和中心云之间迁移工作负载。
• SLA感知服务可利用帕累托前沿选择满足特定权衡的调度方案（例如在非高峰时段优先考虑成本而非延迟）。
• 该算法的并行特性使其适合集成到已有的多核管理节点上运行的自动伸缩控制器中。

局限性与未来工作

• 对大规模集群的可扩展性 – 实验仅在几百台VM上进行，千级节点的表现尚未验证。
• 静态工作负载假设 – 虽然方法包含动态再分配步骤，但主要优化仍基于固定批次任务；对持续流式工作负载仍需进一步改进。
• 参数敏感性 – 混合算法引入了多个超参数（如变异率、鲸鱼与海鸥阶段的平衡），可能需要针对具体领域进行调优。
• 能耗考虑 – 当前成本模型侧重于金钱支出，未来可扩展至加入功耗模型，以实现更绿色的云运营。

总体而言，PHWSOA 将理论严谨性与实际收益相结合，具备成为下一代云调度器有力候选者的潜力。

作者

• Zhi Zhao
• Hang Xiao
• Wei Rang

论文信息

• arXiv ID: 2512.09568v1
• 分类: cs.DC
• 发表时间: 2025年12月10日
• PDF: Download PDF