UCB1、Greedy、Random、Island:ASI-Evolve 四种父代采样策略对比与选型指南

原创2026-10-27 11:29:071,720 阅读

UCB1、Greedy、Random、Island:ASI-Evolve 四种父代采样策略对比与选型指南

ASI-Evolve 是一个让 AI 自动"读文献—设计方案—做实验—分析结果"并循环演进的智能体框架。它的实验数据库每轮都会从历史候选中挑出若干"父代节点"交给 Researcher 继续改进,这一步的采样策略(UCB1、Greedy、Random、Island)直接决定了进化是稳健推进、过早收敛还是广泛探索。本文用通俗的方式对比这 4 种父代采样策略的原理、参数与适用场景,帮你快速选对策略。

ASI-Evolve 框架概览图:知识—假设—实验—分析闭环

父代采样发生在 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 个,不看分数。它看似最简单,实际有两个价值:

  1. 冷启动或数据库还很小时,Random 与 UCB1 行为一致(UCB1 在无访问记录时会退化为随机采样);
  2. 当你怀疑当前搜索"过拟合"或太窄时,切回 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 强行打散视野,重建多样性

几条实践建议:

  1. 默认先用 UCB1,跑通后再调;
  2. 切换策略后留意日志中的 Sampled N context nodes,以及 island 策略的岛统计信息(get_island_stats 会报告各岛规模、最佳分数与特征图覆盖率);
  3. Greedy 只做"短跑",长程任务建议搭配 UCB1 或 Island 保多样性;
  4. Island 的 feature_dimensions 在开跑前定好即可(如 complexity、diversity),运行中频繁更换会干扰特征图统计。

小结

  • UCB1:默认之选,c 值调节探索强度;
  • Greedy:只取最优,快速但易陷局部最优;
  • Random:均匀随机,冷启动与"破局"两相宜;
  • Island:多岛迁移 + 特征分箱,长周期多样性搜索的首选。

四种策略代码量都很小、接口统一,切换成本只是 config.yaml 中一个 algorithm 字段。想深入阅读实现,可以从 database/algorithms/ 目录下的四个文件入手,再对照 database/database.py 里 sample() 的调用方式即可完整掌握。

登录后查看全文
ASI-Evolve