UCB1、Greedy、Random、Island:ASI-Evolve 四种父代采样策略对比与选型指南
UCB1、Greedy、Random、Island:ASI-Evolve 四种父代采样策略对比与选型指南
ASI-Evolve 是一个让 AI 自动"读文献—设计方案—做实验—分析结果"并循环演进的智能体框架。它的实验数据库每轮都会从历史候选中挑出若干"父代节点"交给 Researcher 继续改进,这一步的采样策略(UCB1、Greedy、Random、Island)直接决定了进化是稳健推进、过早收敛还是广泛探索。本文用通俗的方式对比这 4 种父代采样策略的原理、参数与适用场景,帮你快速选对策略。
父代采样发生在 ASI-Evolve 循环的哪一步?
ASI-Evolve 的核心循环是:LEARN → DESIGN → EXPERIMENT → ANALYZE,每轮重复。数据库中每个节点(Node)保存着一次尝试的代码、分数、动机和分析结论(定义见 utils/structures.py)。
每一轮开始时,流水线会调用 pipeline/main.py 中的 self.database.sample(sample_n),从 database/database.py 的实验数据库里按指定策略挑出 sample_n 个节点:
- 第 1 个节点作为"基础代码",供 Researcher 做增量修改(diff 模式);
- 被采样节点的
visit_count会 +1,成为后续探索/利用权衡的依据。
四种策略都继承同一个抽象接口 BaseSampler,由工厂函数 get_sampler() 按名字创建,在 config.yaml 中一行切换:
database:
sampling:
algorithm: "ucb1" # ucb1 / random / greedy / island
四种策略速览:一张表看懂差异
| 策略 | 一句话原理 | 关键参数 | 探索程度 | 源码 |
|---|---|---|---|---|
| UCB1 | 得分 + 探索奖励,平衡利用与探索 | c(默认 1.414) |
中 | ucb1.py |
| Greedy | 直接取当前得分最高的前 n 个 | 无 | 极低 | greedy.py |
| Random | 完全均匀随机抽取 | 无 | 极高 | random.py |
| Island | 多个"岛屿"轮流进化 + 定期迁移 + MAP-Elites 特征分箱 | num_islands 等 6 项 |
高且可控 | island.py |
UCB1:默认的"稳中带冲"
UCB1 来自多臂老虎机理论,公式为:
UCB1 = 归一化得分 + c × sqrt(ln(N) / n_i)
N是所有节点总访问次数,n_i是该节点被采样的次数;- 得分越高越好,但被采得越少的节点获得的"探索奖励"越大;从未被采样的节点会被优先选中;
c控制探索强度,config.yaml 默认ucb1_c: 1.414(即 √2)。
适合:已有比较靠谱的进化方向,希望持续压榨高分候选、同时又不漏掉冷门节点的常规场景。这是仓库的默认策略。
Greedy:只认当前最强
实现非常直白——按 score 降序排序,取前 n 个。没有随机性,没有探索项,短期收敛最快,但很容易"钻牛角尖":一旦最高分方向是局部最优,搜索就会卡住。
适合:明确只想在已知最优家族内做短周期精修、且不在乎多样性的收尾阶段。
Random:最朴素的"洗牌"
均匀随机抽 n 个,不看分数。它看似最简单,实际有两个价值:
- 冷启动或数据库还很小时,Random 与 UCB1 行为一致(UCB1 在无访问记录时会退化为随机采样);
- 当你怀疑当前搜索"过拟合"或太窄时,切回 Random 能强行把视野打散。
Island:多岛进化 + MAP-Elites 式多样性
island.py 是功能最丰富的策略,它把节点池切成多个"岛屿",每轮只从当前岛屿采样并轮转,同时混合三种方式:
- 探索(
exploration_ratio,默认 0.2):岛内均匀随机; - 利用(
exploitation_ratio,默认 0.3):从存档(archive)中取历史佳者; - 加权采样(剩余概率):按得分加权,分高者概率大。
此外还有两个特色机制:
- 迁移(migration):每
migration_interval代(默认 10),每个岛屿把得分最高的migration_rate(默认 10%)比例的节点迁移给相邻岛屿,防止各岛各自封闭; - 特征分箱(MAP-Elites 风格):可按
complexity(代码长度)和diversity(代码结构差异)等维度建立特征图,鼓励覆盖不同"家族"的解。
适合:长周期搜索、希望同时保留多种解法风格的任务,是四种策略中最接近 MAP-Elites 的选项。
一键切换:在 config.yaml 中怎么配
所有策略共用 config.yaml 的 database.sampling 段(实验级配置可覆盖仓库默认值):
database:
sampling:
algorithm: "island"
ucb1_c: 1.414 # 仅 ucb1 使用
island: # 仅 island 使用
num_islands: 5
migration_interval: 10
migration_rate: 0.1
exploration_ratio: 0.2
exploitation_ratio: 0.3
feature_dimensions: ["complexity", "diversity"]
feature_bins: 10
官方自带的圆填充演示实验 experiments/circle_packing_demo/config.yaml 就用了 island 策略(并把 exploitation_ratio 提到 0.6),可以当作现成参考。运行方式:
python main.py \
--experiment circle_packing_demo \
--steps 10 \
--sample-n 3 \
--eval-script /path/to/experiments/circle_packing_demo/eval.sh
其中 --sample-n(对应 pipeline.sample_n)控制每轮交给 Researcher 的父代数量。
选型指南:按场景快速决策 🧭
| 你的处境 | 推荐策略 | 理由 |
|---|---|---|
| 刚起步、拿不准 | UCB1 | 默认策略,探索/利用平衡,几乎不会错 |
| 追求多样性、长周期搜索 | Island | 多岛 + 特征分箱,覆盖面最广 |
| 方向已明确,只需冲刺 | Greedy | 纯利用,收敛最快 |
| 搜索显得过窄/重复 | Random | 强行打散视野,重建多样性 |
几条实践建议:
- 默认先用 UCB1,跑通后再调;
- 切换策略后留意日志中的
Sampled N context nodes,以及 island 策略的岛统计信息(get_island_stats会报告各岛规模、最佳分数与特征图覆盖率); - Greedy 只做"短跑",长程任务建议搭配 UCB1 或 Island 保多样性;
- Island 的
feature_dimensions在开跑前定好即可(如complexity、diversity),运行中频繁更换会干扰特征图统计。
小结
- UCB1:默认之选,
c值调节探索强度; - Greedy:只取最优,快速但易陷局部最优;
- Random:均匀随机,冷启动与"破局"两相宜;
- Island:多岛迁移 + 特征分箱,长周期多样性搜索的首选。
四种策略代码量都很小、接口统一,切换成本只是 config.yaml 中一个 algorithm 字段。想深入阅读实现,可以从 database/algorithms/ 目录下的四个文件入手,再对照 database/database.py 里 sample() 的调用方式即可完整掌握。
