等预算下蒙特卡洛树搜索与随机重启列表调度在DAG工作流上的对照计算研究
事件
蒙特卡洛树搜索常被提议用于有向无环图（DAG）工作流调度，但多数研究从未在同等搜索代价下与更简单的方法做对照。该研究在受控协议下补上了这一比较：所有实验组获得完全相同的预算，即构建并评估相同数量的候选调度方案。主实验组为MCTS调度方法，对照组为不带搜索树的随机重启列表调度器，另设教科书式UCT的MCTS作为后续验证组。分析方案在数据收集前锁定，独立核查确认全部768个确认阶段调度有效且完成时间正确。
在2048个候选调度的主预算下，MCTS比随机重启差2.88%（95%置信区间[-3.62%,-2.15%]），该结论基于96个留出实例中基线相对余量为正的72个。差距并非预算不足：在单独的探索池上，随机重启自我改进1.85%，而MCTS仅提升0.24%；MCTS的720个首次结果中有700个只是其被赋予的热启动。所研究的选择规则确定性地锁定在首个扩展子节点上，使试验相互关联，而随机重启则从尾部采样获益；其与完工时间之间的因果联系仍属推断。
结构图谱进一步定位了树搜索失效的边界：随机重启在稀疏不规则工作流上占优，在规则分层工作流上无显著差异，在稠密工作流上则没有改进空间。将选择规则换成教科书式UCT后，大部分差距消失（-0.26%，95%置信区间[-0.71%,+0.23%]），但符号未反转。结果仅限于受控合成域（任务数8、16、32，处理器2至8个，预算至2048），作者不对更大预算作任何断言。
来源
本条目由采集管线自动抓取并发布，完整内容见下方来源链接。
*采集源：arXiv cs.AI*