MCTS调度竟输给随机重启2.88%，相同预算下700/720次结果只是热启动！
Equal-Budget Monte Carlo Tree Search versus Randomized-Restart List Scheduling for DAG Workflows: A Controlled Equal-Budget Computational Study
📖 AI 总结
这项研究在严格等预算条件下，对比了蒙特卡洛树搜索（MCTS）与随机重启列表调度在DAG工作流调度中的表现。所有方法均构建并评估相同数量的候选调度方案，分析方案在数据收集前即已锁定，并由独立检查者验证了768个确认阶段调度的有效性。主要发现是：在2048次评估的主预算下，MCTS比随机重启方法差2.88%（95%置信区间[-3.62%,-2.15%]），且这一劣势并非源于预算不足——在探索池中重启方法自我改进1.85%，而MCTS仅提升0.24%，MCTS的720个首次结果中有700个只是其被赋予的热启动。研究进一步指出，所考察的选择规则会确定性地锁定在首个扩展子节点上，导致试验高度相关，而重启方法则从尾部采样中获益。结构分析显示，重启方法在稀疏不规则工作流上占优，在规则分层工作流上无显著差异，在密集工作流上则无改进空间。将选择规则替换为标准UCT后，劣势大幅缩小至-0.26%（95%置信区间[-0.71%,+0.23%]），但方向未变。该结果限于受控合成域（任务数8至32，处理器2至8，预算上限2048），作者未对更大预算作出推断。
🔑 关键词速览
| Monte Carlo Tree Search (MCTS) | 蒙特卡洛树搜索，一种通过随机模拟构建搜索树来求解决策问题的启发式算法。 |
| DAG Workflows | 有向无环图工作流，由任务节点和有向边组成的无环依赖图，用于表示计算任务间的依赖关系。 |
| Randomized-Restart List Scheduling | 随机重启列表调度，一种通过多次随机重启并采用列表调度启发式来生成候选调度的方法。 |
| UCT | 上限置信区间树，一种基于UCB1公式的蒙特卡洛树搜索选择策略，用于平衡探索与利用。 |
| Makespan | 完工时间，调度中所有任务完成所需的总时间，是调度优化的常见目标。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅