进化搜索Evolution Search：Ansor自动调优算法

可视化演示

展示Ansor进化搜索的种群迭代、交叉变异基因重组，以及代价模型预测与实测反馈机制，揭示自动调优算法核心原理。

搜索空间：调度方案的“宇宙”

安师傅的厨房里挂着一本厚重的《招牌菜做法大全》，每一页都写着一种做法：第 37 页把肉切成 64 像素见方、大火爆炒 2 分钟、出锅前撒一把葱花；第 38 页则切成 128 见方、中火慢炖。食材、刀工、火候、下锅顺序，每一栏都有好几个选项，随意组合就能翻出天文数字的新页。安师傅咽了咽口水：“照我这本册子的厚度，一页页试根本不可能。”

这本“菜谱”在编译器世界里对应着调度方案的搜索空间。给定一个算子（比如矩阵乘法），编译器可以用多种方式生成目标代码：循环分块（tiling）、向量化（vectorization）、并行化（parallelization）、循环重排（reordering）等，每一种叫做一条调度原语（schedule primitive）。每条原语选取不同取值，就构成一个具体的调度方案，即一个程序变体（program variant）。所有变体的集合，就是搜索空间 S。在进化过程中，每个调度方案会被编码成一条紧凑的序列或向量（编码表示），交叉与变异就在这份“基因序列”上操作。

搜索空间的大小可以用简单的乘法估算。假设共有 k 种调度原语，第 i 种原语有 n_i 种可选取值，则总方案数为：

安师傅盯着菜谱册子叹气，但他转念一想：不需要翻完所有页，我只需要找到最优的那一两页——而“进化”能帮我快速逼近它。于是，他开始了第一批实验。

初始种群：从随机开始的第一代

安师傅没有继续对着菜谱空想，而是挽起袖子，闭着眼从册子里随机抽了 20 页，照着做了 20 道菜，一字排开。有的切块大得离谱，有的火候忽大忽小，卖相难看，但安师傅很满意：“这才叫广撒网，哪个方向都别漏。”

进化搜索的第一步，就是生成这样的“第一批试验品”，称为初始种群（population）。种群中的每个方案是一个个体（individual），它们从搜索空间中随机采样（random sampling）得到。为了保证不遗漏任何可能有希望的区域，采样还要尽量均匀，避免 20 道菜全挤在同一种口味上——这就是多样性（diversity）。

假设种群规模为 P，第 0 代种群写作：

“第一批 20 道菜虽然大多难以下咽，但重要的是它们长满了整个口味地图。”安师傅把试吃结果记在本子上，心里已有了下一锅的灵感——好的方向，慢慢浮出水面。

适应度评估：老厨师的直觉与食客的舌头

试菜是有成本的。安师傅的招牌菜工序复杂，一道菜从备料到出锅要 5 分钟，20 道就是 100 分钟，这还不算顾客等菜的不耐烦。聪明的安师傅想了个办法：先凭自己几十年的经验（直觉）快速扫一眼，把明显不行的菜直接划掉；只有少数看着有潜力的菜，才真正做给食客们试吃（实测）。食客的反馈，又反过来修正他的直觉。

这就是代价模型（cost model）与实际测量（measurement）的双轨评估。Ansor 训练一个代价模型 \(f_\theta(x)\) 来预测调度方案 x 的运行性能，用它给种群中所有个体打分排序；排名前 k 的候选才上真机实测。实测获得的真实性能数据会加入训练集，微调模型参数 θ，让“老厨师的直觉”越来越准。

评估流程可以表示为：

“光靠直觉会看走眼，光靠试吃要等到天黑。”安师傅的双轨策略，让每次试吃都花在刀刃上，而他的经验也在一次次反馈中进化——这正是 Ansor 能快速锁定好方案的关键。

进化算子：交叉、变异与选择

第一轮试吃结束，安师傅对着成绩单琢磨：第 3 道菜的火候堪称完美，第 11 道菜的刀工让人惊艳，可惜它们各自都有短板。他灵机一动，把第 3 道的火候和第 11 道的刀工拼到一道新菜里——这就是“交叉”。偶尔，他还会故意手一抖多撒一把盐，给新菜加点“意外”——这就是“变异”。

进化算子（evolution operator）是驱动种群升级的引擎。选择（selection）负责决定谁有资格当父母：锦标赛选择（tournament selection）从种群中随机抽出几个个体“比武”，适应度最高的胜出。交叉（crossover）把两个父代方案的调度特征拼接成子代。变异（mutation）以一定概率随机扰动某个参数，比如把分块大小从 64 改成 128。精英保留（elitism）则把每代最优个体原封不动地放进下一代，防止好方案失传。子代生成规则可写成：

安师傅的新菜一批批出锅：火候基因、刀工基因在种群中像口碑一样传开，偶尔的“手抖”又带来惊喜。好味道在一代代进化中不断叠加，离那道完美招牌菜越来越近。

迭代收敛：有限预算内的逼近

安师傅给自己立下规矩：最多试 50 锅，每锅 20 道，预算用光就收工。另外，如果连续几锅都没能做出比之前更好的菜，说明已经接近这道菜的“天花板”，再耗下去也是浪费。他把规则贴在厨房墙上，提醒自己：进化的目的是在有限时间内端出最好的菜，而不是永远试下去。

迭代（iteration）是进化搜索的主循环：评估当前种群 → 选择父代 → 交叉变异生成下一代 → 再评估，如此循环 T 代。整个过程中，算法始终记录着历史最优个体。收敛判定通常看相邻两代最优适应度的提升量 \(\Delta f_t\) 是否跌破阈值 ε，若长期无改善则提前终止。Ansor 的实际运行也受总时长、总测量次数预算约束。最终返回的最优方案为：

50 锅很快用完，安师傅端出那盘集大成之作。它不是菜谱册子里每一页都试过的“理论最好”，却是试过的几千道菜里最棒的一盘——这正是工程世界的聪明活法。

对比优势：为何碾压网格搜索

如果安师傅是个死心眼的“网格搜索”厨师，他会怎么做？把菜谱册子从第 1 页开始，一页一页全部做一遍。以每道 5 分钟算，做完 \(10^{20}\) 道菜需要千亿年。如果是个“随机搜索”厨师，他每天随机抽几页做，做完就忘，永远不知道哪道更好——没有记忆，就没有进步。

网格搜索（grid search）枚举搜索空间中所有组合，开销为完整空间大小；随机搜索（random search）虽然能覆盖一些点，但每轮彼此独立，没有利用已发现的好区域。进化搜索通过选择压力把算力集中在有希望的区域，同时保留一定探索能力，实际评估次数只是种群规模 P 与代数 T 的乘积：

安师傅的进化菜谱最终成了餐厅招牌。同样的思路，在 Ansor 中对 ResNet、BERT 等真实模型做了验证，开发者们发现：曾经需要手工调好几天的算子，进化搜索自动跑几十分钟就能逼近甚至超越人工调优的性能。这就是“聪明试错”对“笨拙穷举”的全面碾压。

AI 应用场景

Python 演示

import random # 搜索空间: 每种调度参数的可选值TILE = [16, 32, 64, 128, 256]     # 分块大小VEC = [2, 4, 8, 16]               # 向量化宽度STAGE = [1, 2, 3, 4]              # 流水级数POP_SIZE = 12GENERATIONS = 20MUT_RATE = 0.2CACHE = {}                        # 测量缓存, 同一方案只实测一次 def random_sample():    # 从搜索空间均匀随机采样一个调度方案    return (random.choice(TILE), random.choice(VEC), random.choice(STAGE)) def cost_model(s):    # 模拟代价模型: 预估运行耗时, 越小越好    t, v, st = s    return 4000.0 / t + v * 2.0 + st * 3.0 + random.uniform(0, 5) def real_measure(s):    # 模拟真实测量: 在预估基础上加噪声波动, 并缓存结果    if s not in CACHE:        CACHE[s] = cost_model(s) + random.gauss(0, 3)    return CACHE[s] def fitness(s):    # 耗时越小适应度越高, 进化搜索按适应度最大化来排    return -real_measure(s) def crossover(a, b):    # 均匀交叉: 每个维度随机取自一个父代    return tuple(a[i] if random.random() < 0.5 else b[i] for i in range(3)) def mutate(s):    # 变异: 以一定概率扰动每个维度    t, v, st = s    if random.random() < MUT_RATE:        t = random.choice(TILE)    if random.random() < MUT_RATE:        v = random.choice(VEC)    if random.random() < MUT_RATE:        st = random.choice(STAGE)    return (t, v, st) def tournament_select(pop, k=3):    # 锦标赛选择: 随机挑 k 个, 取适应度最高者    best = None    for _ in range(k):        ind = random.choice(pop)        if best is None or fitness(ind) > fitness(best):            best = ind    return best def evolve():    # 初始化种群    pop = [random_sample() for _ in range(POP_SIZE)]    for gen in range(GENERATIONS):        pop.sort(key=fitness, reverse=True)        elites = pop[:2]                    # 精英保留        next_gen = elites[:]        while len(next_gen) < POP_SIZE:            p1 = tournament_select(pop)            p2 = tournament_select(pop)            child = mutate(crossover(p1, p2))            next_gen.append(child)        pop = next_gen        best = max(pop, key=fitness)        print('gen', gen, 'best cost %.1f' % -fitness(best), best)    return max(pop, key=fitness) if __name__ == '__main__':    best = evolve()    print('best schedule:', best, 'cost %.1f' % -fitness(best))

1. CACHE = {}测量缓存池，模拟 Ansor 中“同一调度方案只实测一次”的工程约束，避免重复测量浪费预算
2. pop = [random_sample() for _ in range(POP_SIZE)]初始化种群，从搜索空间均匀随机采样 12 个候选调度
3. pop.sort(key=fitness, reverse=True)按适应度从高到低排序，让优秀方案排在最前
4. elites = pop[:2]精英保留：最优秀的 2 个方案原样进入下一代，防止好基因丢失
5. child = mutate(crossover(p1, p2))先交叉再变异，把两个父代的调度特征重组并引入随机扰动
6. if s not in CACHE:实测前先查缓存，命中则直接返回已测结果，节省昂贵测量开销

常见误区

面试题