想象你是一家顶级餐厅的主厨，要研发一道招牌菜。调料克数、火候档位、下锅顺序的组合有上亿种，你不可能一道一道试。于是你让学徒们随手写下一批菜谱，试菜员品尝打分，把好吃的留下，再把两道好菜的做法各取一半拼在一起，偶尔把某位调料的用量微调一下——如此一代一代进化，最终逼近那道近乎完美的菜。这套“进化研发法”，正是 AI 编译器 Ansor 和 MetaSchedule 用来从浩瀚的调度空间里“采样”出高性能执行方案的秘密武器。本文会用这个后厨故事，带你拆解遗传算法如何生成与筛选调度候选，理解适应度评估、交叉与变异的设计细节，并看到它们如何被工程化地集成进真实系统。

岗位关联

对 AI 从业者而言，掌握演化搜索驱动的调度采样，就是掌握让算子自动变快、让模型上线不再依赖手工调参的核心能力——这是 AI 编译与推理优化方向的高价值技能。

目录
  1. 可视化演示
  2. 遗传算法基础
  3. 调度编码表示
  4. 适应度评估
  5. 交叉算子设计
  6. 变异算子设计
  7. 种群迭代流程
  8. 系统集成应用
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

展示线性回归的拟合过程，通过交互调节斜率和截距，观察残差变化与R²拟合优度，理解最小二乘法的优化原理。

本节配有交互动效（进入视口后自动加载，约 3KB）。

散点数据分布 紫色点为观测数据，存在线性趋势和随机噪声 切换模式查看回归线拟合和残差分析 y = β₀ + β₁x + ε 线性回归假设因变量与自变量呈线性关系，ε为随机误差

遗传算法基础

新主厨把菜谱研发交给了学徒们：每人凭直觉随手写一道菜谱，于是满桌子摆满了五花八门的草案，有的离谱，有的有模有样——这就是“初始种群”。这些菜谱良莠不齐没有关系，进化机制会负责筛选与改良。

在 Ansor 的调度搜索里，“菜谱”就是调度方案，“学徒”就是随机采样器。遗传算法（GA）从随机初始化的种群出发，不断重复“评估适应度→选择→交叉→变异”的循环，让候选调度逐代逼近高性能区域。适应度（fitness）是进化的指挥棒：每个调度被编译并测量，耗时越短、适应度越高，就越有资格把基因传下去。

选择操作通常按适应度比例决定谁成为亲本，这就像一个“轮盘赌”：得分高的个体占据轮盘上更大的扇区，被抽中的概率更高。Ansor 的演化搜索中，种群规模通常是几十到几百，演化若干代后收集所有访问过的候选，交给下游成本模型统一筛选。

就像只让好吃的菜谱拥有“生儿育女”的权利，高适应度的调度更容易把优秀基因传下去，种群的整体水平因此一代比一代高——这便是进化在调度搜索中的核心价值。

P(i)=f(i)∑j=1Nf(j)P(i)=\frac{f(i)}{\displaystyle\sum_{j=1}^{N}f(j)}
轮盘赌选择：个体 $i$ 被选为亲本的概率等于它的适应度占整个种群适应度总和的比例。
  1. 个体得分第 $i$ 个候选调度的适应度，Ansor 中常用实测耗时的倒数，越快得分越高。
    f(i)=1Tif(i)=\frac{1}{T_i}
  2. 分母求和把种群中全部 $N$ 个候选的适应度加起来，作为归一化的总分数。
    ∑j=1Nf(j)\sum_{j=1}^{N}f(j)
  3. 选择概率个体得分除以总分，得到它被选中当亲本的概率，好菜谱获得更多“繁衍权”。
    P(i)=f(i)∑j=1Nf(j)P(i)=\frac{f(i)}{\sum_{j=1}^{N}f(j)}

调度编码表示

每道菜谱都写在一张标准卡片上：上半部分是步骤框架——先腌再炸，还是先焯再炒；下半部分是数字参数——油温 180 度、盐 3 克。框架决定“怎么做”，数字决定“做多细”。

Ansor 把调度也拆成“框架 + 参数”两层：框架叫 sketch（结构草图），参数叫 annotation（注释）。sketch 决定循环的嵌套结构和计算分块方式，比如“先对空间维分块，再对归约维拆分”；annotation 则具体指定每个决策点的取值，比如 tile 尺寸是 64 还是 128。

在遗传算法眼中，一个调度被编码成一个决策向量，这就是它的“基因型”。每个决策的取值范围是离散集合，比如 tile 尺寸只能从 {16, 32, 64, 128} 里选，向量化宽度从 {1, 2, 4, 8} 里选。基因型通过解码器还原成真实的 TVM 调度语句——tile、reorder、vectorize——交给编译器生成可执行代码。

这张“基因卡片”是交叉与变异操作的舞台：框架不动，动的只是数字和顺序，因此无论怎么组合，产出的都还是一道“能做的菜”——一个合法可执行的调度。

s=(t1,t2,…,tn),tk∈Aks=(t_1,t_2,\ldots,t_n),\qquad t_k\in\mathcal{A}_k
调度的基因型：一个由 $n$ 个决策值组成的向量，每个决策值必须从自己的取值域中选择。
  1. 决策向量调度被抽象为 $n$ 个决策值 $t_k$，如 tile 尺寸、向量化宽度、并行因子，写在一张“基因卡片”上。
    s=(t1,t2,…,tn)s=(t_1,t_2,\ldots,t_n)
  2. 取值域每个决策 $t_k$ 只能从离散集合 $\mathcal{A}_k$ 中取值，比如 tile 尺寸的取值域是 $\{16,32,64,128\}$。
    tk∈Akt_k\in\mathcal{A}_k
  3. 搜索空间所有可行调度组成所有取值域的笛卡尔积，这是进化搜索要探索的“菜谱宇宙”。
    S=A1×A2×⋯×AnS=\mathcal{A}_1\times\mathcal{A}_2\times\cdots\times\mathcal{A}_n

适应度评估

试菜很贵：每道菜都要真刀真枪做出来让食客品尝。主厨于是请来一位老师傅，先闻香味、看色泽，用几十年的经验预判“这菜大概几分”，只把最有希望的几道端上餐桌。

在 Ansor 中，“端上餐桌”就是编译加硬件实测，每次动辄几百毫秒甚至数秒。演化搜索每代产生大量候选，全部实测不现实。于是系统先训练一个成本模型（常用 XGBoost），输入调度的结构化特征，预测它的运行延迟，这就是那位“闻香识菜”的老师傅。

完整的适应度评估是两阶段的：成本模型对所有候选打分排序，取预测最优的 top-k 送到硬件实测；实测得到的真实耗时被记为适应度，既用来指导进化选择，又作为新样本帮助微调成本模型，形成“预测—筛选—实测—再训练”的闭环。

老师傅的鼻子代替不了食客的舌头，但能把 100 道菜筛到 3 道——成本模型不能替代实测，却能决定“谁值得上桌”，让昂贵的硬件测量花在刀刃上。

f(s)=1T(s),Pk={s(1),s(2),…,s(k)}f(s)=\frac{1}{T(s)},\qquad P_k=\{s_{(1)},s_{(2)},\ldots,s_{(k)}\}
真实适应度是实测延迟的倒数；成本模型负责给候选排序，只把预测最靠前的前 $k$ 名送去实测。
  1. 真实适应度调度 $s$ 在硬件上实测得到的耗时 $T(s)$ 越小，适应度 $f(s)$ 越大。
    f(s)=1T(s)f(s)=\frac{1}{T(s)}
  2. 预测排序成本模型为每个候选输出预测延迟，按从小到大排列出顺序。
    T^(s(1))≤T^(s(2))≤⋯≤T^(s(n))\hat{T}(s_{(1)})\le\hat{T}(s_{(2)})\le\cdots\le\hat{T}(s_{(n)})
  3. Top-k 截取只保留预测排名最靠前的 $k$ 个候选，送入硬件实测，其余直接淘汰。
    Pk={s(1),s(2),…,s(k)}P_k=\{s_{(1)},s_{(2)},\ldots,s_{(k)}\}

交叉算子设计

两道招牌菜各有绝活：A 的火候控制炉火纯青，B 的香料配比惊艳四座。主厨突发奇想：把 A 的前半段流程和 B 的后半段流程拼起来，能不能集两家之长？

交叉算子正是“流程拼接”的数学实现。Ansor 随机选择一个切点，把两个亲本调度的注释向量在切点处切开，交换尾部片段，生成两个新的子代调度。切点之前的决策值继承亲本 A，切点及之后的继承亲本 B，这样两个好方案的“基因片段”得以组合。

最常见的单点交叉之外，Ansor 也支持多点交叉：把向量切成多段后交替拼接。关键约束是“结构保留”——交叉只发生在注释层（数字参数层面），sketch 结构保持不动，从而避免拼出非法调度。组合策略上，GPU 调度的交叉点多选在并行与向量化段，CPU 调度的交叉点多选在 tile 段，让交叉更可能产生有意义的组合。

交叉就像“集两家之长的联姻”，但前提是两家菜谱的框架得兼容——注释级交叉保证了拼出来的子代永远是合法调度，进化可以放心大胆地“乱点鸳鸯谱”。

ci={pi(A),i<cutpi(B),i≥cutc_i=\begin{cases}p_i^{(A)}, & i<\text{cut}\\[2pt]p_i^{(B)}, & i\ge\text{cut}\end{cases}
单点交叉：子代的每个基因位按切点位置决定继承哪个亲本，切点前归 A，切点后归 B。
  1. 随机切点在 $1$ 到 $n-1$ 之间均匀随机选择切点位置 $\text{cut}$，把两个亲本向量一分为二。
    cut∼Uniform{1,2,…,n−1}\text{cut}\sim\mathrm{Uniform}\{1,2,\ldots,n-1\}
  2. 前段继承 A切点之前的基因位 $c_i$ 全部来自亲本 A 的对应位置 $p_i^{(A)}$。
    ci=pi(A),i<cutc_i=p_i^{(A)},\quad i<\text{cut}
  3. 后段继承 B切点及之后的基因位全部来自亲本 B，完成“前半段 A + 后半段 B”的拼接。
    ci=pi(B),i≥cutc_i=p_i^{(B)},\quad i\ge\text{cut}

变异算子设计

光靠拼菜谱还不够，主厨还会偶尔把盐从 3 克改成 4 克，或者把“先炒后炖”调成“先炖后炒”。这些看似随意的微调，有时会带来意想不到的惊喜。

变异算子负责注入新基因，防止种群过早收敛到局部最优。它会对调度向量中的个别决策做随机扰动：修改 tile 尺寸、交换循环顺序、调整向量化宽度。没有变异，种群会在几代之后变得千篇一律，失去继续探索的能力。

变异的触发由变异概率 $p_m$ 控制，Ansor 中通常取值 0.1~0.3——保证种群有探索力又不至于变成随机漫步。针对不同类型的基因，变异操作也不一样：数值型基因（tile 尺寸）常用缩放扰动，随机乘以 0.5~2.0 的系数；顺序型基因（循环顺序）随机交换两个位置；类别型基因（并行策略）则重新采样一个新值。

变异的原则是“微调而非重做”——小概率、小幅度的扰动，让好经验得以保留，同时给种群留一扇探索新口味的窗，避免进化冲进死胡同。

P(ti→ti′)=pm,ti′∼Ai, ti′≠tiP(t_i\to t_i')=p_m,\qquad t_i'\sim\mathcal{A}_i,\ t_i'\neq t_i
变异：每个基因以概率 $p_m$ 被替换为取值域中的另一个值，给种群注入新鲜多样性。
  1. 变异概率每个基因位以很小的概率 $p_m$ 触发变异，保证大部分好基因原样保留。
    P(ti→ti′)=pmP(t_i\to t_i')=p_m
  2. 重新采样发生变异时，从该基因的取值域 $\mathcal{A}_i$ 中随机抽一个新值 $t_i'$，且必须不同于原值。
    ti′∼Ai,ti′≠tit_i'\sim\mathcal{A}_i,\quad t_i'\neq t_i
  3. 数值微扰对 tile 尺寸这类数值基因，常用缩放扰动，随机乘一个 0.5 到 2.0 之间的系数 $q$。
    ti′=ti×q,q∼Uniform(0.5,2.0)t_i'=t_i\times q,\quad q\sim\mathrm{Uniform}(0.5,2.0)

种群迭代流程

一轮试菜会结束后，主厨不会把好菜谱扔掉，而是把最顶尖的几道直接收进档案库珍藏，其余学徒则拿着好菜谱互相拼接、微调，再战下一轮。如此周而复始。

这就是种群的代际更新。Ansor 的演化搜索由多轮组成，每轮包含四个动作：评估适应度、保留精英、从精英中选亲本做交叉变异、生成下一代。精英保留比例通常为 5%~20%，保证当前最优解永远不会在迭代中丢失。

迭代轮数与种群规模共同决定采样预算：$B=n_{\text{sketch}}\times n_{\text{pop}}\times n_{\text{gen}}$。Ansor 还会做早停控制——如果连续多代最优适应度没有提升，就提前终止当前 sketch 的搜索，把预算留给其他 sketch。搜索结束后，所有代访问过的候选调度被统一收集，送到底层成本模型做筛选。

代际更替让厨师团队“站在前人的肩膀上”——每一代都比上一代更懂这道菜，而精英档案保证了最顶尖的手艺绝不失传，差的菜谱则被自然淘汰。

Pt+1=E(Pt) ∪ M ⁣(C ⁣(E(Pt)))P_{t+1}=\mathcal{E}(P_t)\ \cup\ \mathcal{M}\!\left(\mathcal{C}\!\left(\mathcal{E}(P_t)\right)\right)
代际更新：下一代种群 = 精英保留的个体 ∪ 对精英做交叉和变异后产生的新后代。
  1. 精英保留把当前代适应度最高的少数个体直接选出来，原封不动进入下一代，防止最优解丢失。
    E(Pt)={s∈Pt:f(s) 排名前 e}\mathcal{E}(P_t)=\{s\in P_t:f(s)\text{ 排名前 }e\}
  2. 亲本交叉从精英集合中随机选两两配对，执行交叉算子，生成一批后代。
    C(E(Pt))={crossover(p1,p2):p1,p2∈E(Pt)}\mathcal{C}(\mathcal{E}(P_t))=\{crossover(p_1,p_2):p_1,p_2\in\mathcal{E}(P_t)\}
  3. 后代变异对交叉产生的每个后代以概率 $p_m$ 做变异，注入多样性。
    M(C)={mutation(c):c∈C}\mathcal{M}(C)=\{mutation(c):c\in C\}
  4. 合并成下一代精英与变异后的后代合并，构成完整的下一代种群 $P_{t+1}$。
    Pt+1=E(Pt)∪M(C(E(Pt)))P_{t+1}=\mathcal{E}(P_t)\cup\mathcal{M}(\mathcal{C}(\mathcal{E}(P_t)))

系统集成应用

整套进化研发法最终被固化成一间“流水线厨房”：主厨定框架（sketch）、学徒团演化试菜（演化搜索）、老师傅闻香筛选（成本模型）、试菜员实测打分（测量），最后把新积累的经验写回手册（微调模型）。

Ansor 的完整流程正是如此：程序被切分成一个个子图后，为每个子图生成多个 sketch；对每个 sketch，用随机采样加演化搜索生成大量候选调度；成本模型筛出 top-k 实测，实测结果既作为适应度指导进化，又作为训练样本。MetaSchedule 把同样的演化搜索带进了 TVM 的统一生态，支持用户用 Python DSL 描述搜索空间和自定义变异规则。

两者都离不开“迁移微调”：之前任务积累的（调度，实测耗时）数据被用来训练或更新成本模型，使新任务的第一轮搜索就能借助历史经验，显著减少冷启动代价。成本模型用梯度下降最小化预测误差，学习率控制每次更新的步长；工程上还支持异步并行实测、多设备扩展和超时保护，让进化搜索规模化地跑在集群上。

当流水线转动起来，最珍贵的不是某一道招牌菜，而是整套“会进化的研发机制”——换食材、换厨房（硬件）都不怕，进化总能重新找到最优解。这正是 Ansor 与 MetaSchedule 带给 AI 编译世界的礼物。

L(θ)=1∣D∣∑(s,T)∈D(T^θ(s)−T)2,θ←θ−α ∇θL(θ)\mathcal{L}(\theta)=\frac{1}{|D|}\sum_{(s,T)\in D}\left(\hat{T}_\theta(s)-T\right)^2,\qquad\theta\leftarrow\theta-\alpha\,\nabla_\theta\mathcal{L}(\theta)
迁移微调：成本模型在历史数据 $D$ 上最小化预测误差，用梯度下降更新参数，把旧任务的经验迁移到新任务。
  1. 历史样本集$D$ 是收集到的（调度 $s$，实测耗时 $T$）数据对，来自之前所有调优任务的积累。
    D={(s1,T1),(s2,T2),…}D=\{(s_1,T_1),(s_2,T_2),\ldots\}
  2. 均方误差模型预测延迟 $\hat{T}_\theta(s)$ 与实测延迟 $T$ 之差的平方平均，衡量预测的准确度。
    1∣D∣∑(s,T)∈D(T^θ(s)−T)2\frac{1}{|D|}\sum_{(s,T)\in D}\left(\hat{T}_\theta(s)-T\right)^2
  3. 梯度下降沿损失函数的梯度反方向更新参数，$\alpha$ 是学习率，决定每步走多远。
    θ←θ−α ∇θL(θ)\theta\leftarrow\theta-\alpha\,\nabla_\theta\mathcal{L}(\theta)

AI 应用场景

新芯片上的推理引擎自动调优

阶段：模型部署与算子优化

解决的问题：传统上 matmul、conv 等算子的调度靠工程师手工调参，遇到新架构（如自研 NPU）时经验失效，手工试组合动辄数周；演化搜索自动生成并采样候选调度，几天内逼近手调性能。

具体案例：某端侧团队把 MobileNet 部署到自研 NPU，先用 sketch 生成 5 个结构模板，每个模板演化 10 代、每代 20 个种群，成本模型筛出 top-30 实测，最终 conv 算子延迟比手工方案快 1.6 倍。整个过程就像流水线厨房自动试菜，无需人工干预。

云厂商算子库的持续性能迭代

阶段：训练与推理基础设施优化

解决的问题：云端 GPU 型号多、驱动版本更新频繁，算子库需要持续重新调优。人工维护成本高，且每次硬件升级都要推倒重来；演化搜索加成本模型微调可以把历史调优经验迁移到新任务，让冷启动变热启动。

具体案例：某云厂商在 GPU 驱动升级后，用 MetaSchedule 对全部公开算子重新搜索，利用历史调优数据微调成本模型，使重调优周期从两周缩短到三天，推理服务性能整体提升 8%。

推理基准榜单的性能冲刺

阶段：端到端推理调优

解决的问题：MLPerf 等基准比拼的是单个算子乃至融合算子的极致延迟，手工调参难以覆盖多算子联合优化空间；演化搜索能同时对多个算子的调度组合做联合采样，找到全局更优的融合方案。

具体案例：一支参赛队伍用 Ansor 对 ResNet-50 的 18 个算子做联合演化采样，把端到端推理延迟压进榜单前五。赛后复盘发现，最优调度来自一个由交叉操作偶然组合出的“混血方案”——两个平凡调度拼在一起，性能却远超各自。

Python 演示

python51 行
"""进化搜索调度采样演示：用遗传算法找最优 (tile, vec, par)。"""import random POP_SIZE = 20      # 每代种群大小ELITE_NUM = 4      # 精英保留个数GENERATIONS = 12   # 演化代数MUT_PROB = 0.25    # 变异概率 TILE_CHOICES = [16, 32, 64, 128, 256]VEC_CHOICES = [1, 2, 4, 8, 16]PAR_CHOICES = [1, 2, 4] def random_schedule():    return [random.choice(TILE_CHOICES),            random.choice(VEC_CHOICES),            random.choice(PAR_CHOICES)] def fitness(s):    tile, vec, par = s    delay = abs(tile - 64) / 64.0 + abs(vec - 4) / 4.0 + abs(par - 2) / 2.0    return 1.0 / (1.0 + delay) def crossover(a, b):    cut = random.randint(1, len(a) - 1)    return a[:cut] + b[cut:] def mutate(s):    if random.random() >= MUT_PROB:        return s    i = random.randrange(len(s))    pool = [TILE_CHOICES, VEC_CHOICES, PAR_CHOICES][i]    s[i] = random.choice([v for v in pool if v != s[i]])    return s def evolution_search():    pop = [random_schedule() for _ in range(POP_SIZE)]    for gen in range(GENERATIONS):        pop.sort(key=fitness, reverse=True)        elites = pop[:ELITE_NUM]        children = []        while len(children) < POP_SIZE - ELITE_NUM:            p1, p2 = random.choice(elites), random.choice(elites)            children.append(mutate(crossover(p1, p2)))        pop = elites + children    pop.sort(key=fitness, reverse=True)    return pop[0] if __name__ == "__main__":    best = evolution_search()    print("最优调度: tile=%d vec=%d par=%d" % tuple(best))    print("适应度: %.4f" % fitness(best))
目的：用 60 行代码完整实现 Ansor 式演化调度搜索的核心循环——随机初始化种群、适应度排序、精英保留、交叉与变异，最终找到最优的 (tile, 向量化，并行) 参数组合。
  1. delay = abs(tile - 64) / 64.0 + ...模拟硬件耗时函数：调度参数离最优组合（tile=64, vec=4, par=2）越远，耗时越大，适应度越低。
  2. pop.sort(key=fitness, reverse=True)用适应度给整个种群排序，相当于试菜打分后的排行榜。
  3. elites = pop[:ELITE_NUM]保留前 4 名精英直接进入下一代，避免最优解在迭代中丢失。
  4. children.append(mutate(crossover(p1, p2)))交叉把两个精英的调度参数拼成新候选，变异再小幅扰动，一行代码完成“集两家之长 + 微调”。
  5. while len(children) < POP_SIZE - ELITE_NUM用新后代填满种群剩余名额，保持种群规模恒定。
  6. if __name__ == "__main__":让脚本既可被 import 也能直接运行，是工程代码的可执行入口。

常见误区

误区演化搜索不就是不断随机生成调度碰运气吗？多跑几轮随机采样，效果应该也差不多，没必要搞交叉变异这么复杂。

正解随机采样每次独立，没有任何信息积累；遗传算法通过适应度排序保留好基因，再通过交叉把优秀片段组合、变异在小范围扰动，使好解的概率密度逐代升高。Ansor 论文的实验表明，同等预算下演化搜索找到的调度明显优于纯随机采样——就像后厨“记住哪些调料组合好吃”和“每次从零乱试”是天壤之别。

为何常见：因为变异和初始化确实带随机性，初学者只看到随机的一面，忽略了“选择加交叉”带来的方向性积累。

误区成本模型预测是估计值，可能有误差，所以每个候选都应该直接上硬件实测，结果才最可靠。

正解每次实测都要完整编译、运行、收集统计，动辄几百毫秒到数秒；对成千上万个候选全量实测，总开销不可接受。Ansor 用成本模型先筛掉 90% 以上明显差的候选，只对最有希望的 top-k 实测。实测结果仍作为真实适应度指导进化，最终精度不受影响——这正是“老师傅闻香筛菜”的意义。

为何常见：新手把“模型有误差”等同于“不能用”，忽略了它在搜索流程中的定位是过滤器而非最终裁判。

误区变异就是探索新方向，那把变异概率调高一点，是不是就能更快找到全局最优？

正解变异率过高会让个体频繁跳变，好基因刚积累就被破坏，搜索退化为随机漫步。Ansor 把变异率控制在小范围（约 0.1~0.3），配合精英保留，让种群“大步交叉、小步变异”。就像做菜，微调才能保留火候经验，每次把整道菜推倒重做就失去积累了。

为何常见：变异和创新之间的直觉联想，让人误以为“越激进越好”，忽略了探索与利用的平衡。

误区交叉就是把两个调度的代码各取一半拼起来，不需要考虑结构约束，反正都是合法代码。

正解调度有严格的循环嵌套和访存结构，直接拼接代码很容易产生非法或低效的调度。Ansor 在 sketch 结构不变的前提下，只对注释（tile 尺寸、向量化、并行因子等）做交叉，保证交叉点两侧的决策语义兼容。就像菜谱的“步骤框架”不能乱拼，但“火候数值”可以交换。

为何常见：遗传算法教材里交叉常被画成简单的基因串拼接，容易让人忽略领域知识中的结构约束。

误区样本越多搜索越全，把种群设成 10000 个，应该比 100 个强得多。

正解每个个体都要过成本模型甚至硬件实测，种群越大单代开销越高。总预算 $B=n_{\text{sketch}}\times n_{\text{pop}}\times n_{\text{gen}}$ 有限，种群过大反而挤压演化代数，让进化来不及积累优势。Ansor 通过预算控制和按 sketch 分片的小种群策略，在开销与覆盖之间取得平衡。

为何常见：直觉上“更多样本等于更全探索”，忽略了每代评估的固定成本和总预算约束。

面试题

Q1. 在 Ansor 的遗传算法中，“适应度”通常用什么衡量？

单选题 · easy

  • A.编译器的警告数量
  • B.硬件实测耗时的倒数← 正确答案
  • C.调度代码的行数多少
  • D.请求参数的数量大小

答案：B。适应度必须反映“跑得快不快”，因此常用实测耗时 $T$ 的倒数，越快得分越高。警告数、代码行数和参数数量都与运行性能无关，不能作为进化选择的依据。

Q2. Ansor 生成调度候选的第一步是什么？

单选题 · easy

  • A.训练一个成本预测模型
  • B.为算子生成结构草图← 正确答案
  • C.直接测量所有候选方案
  • D.对候选做交叉与变异

答案：B。Ansor 先为算子生成多个 sketch（结构草图），确定循环嵌套框架，之后才在框架上做随机采样和演化搜索。成本模型在候选生成之后才参与筛选，交叉变异是后续的搜索手段而非第一步。

Q3. 成本模型在演化搜索中的主要作用？

单选题 · mid

  • A.取代最终的真实硬件测量
  • B.实测前筛选候选降低开销← 正确答案
  • C.自动生成所有程序草图
  • D.直接决定遗传变异的概率

答案：B。成本模型是“老师傅闻香”，在昂贵的硬件实测之前过滤掉明显差的候选，只保留 top-k 实测。它不能替代实测，也不负责生成草图或控制变异概率，只是评估流水线中的预筛环节。

Q4. 单点交叉生成的子代，切点之前的基因来自？

单选题 · mid

  • A.第二个父本个体
  • B.第一个父本个体← 正确答案
  • C.随机生成的基因值
  • D.上一代最优个体

答案：B。单点交叉中，切点之前的基因继承亲本 A，切点及之后的基因继承亲本 B。随机生成是变异的行为，上一代最优个体是精英保留的对象，与交叉的基因来源无关。

Q5. 下列哪些属于合法的变异操作？

多选题 · mid

  • A.修改循环 tile 的尺寸← 正确答案
  • B.交换两层循环的执行顺序← 正确答案
  • C.把两个父代基因拼接成新子代
  • D.调整向量化的宽度因子← 正确答案

答案：ABD。修改 tile 尺寸、交换循环顺序、调整向量化因子都是对单个调度的局部扰动，属于变异；把两个父代拼接成子代是交叉操作，不是变异。变异的关键特征是“单亲 + 小幅度扰动”。

Q6. 精英保留策略的核心目的是？

单选题 · mid

  • A.防止最优解在迭代中丢失← 正确答案
  • B.增加候选方案的多样性
  • C.加快成本模型的训练过程
  • D.减少每个个体的编译时间

答案：A。精英保留把当代最优的少数个体原样送入下一代，确保交叉变异不会破坏已有的好解。增加多样性是变异算子的职责，模型训练和编译时间与精英保留无关。

Q7. 采样预算 $B=n_{\text{sketch}}\times n_{\text{pop}}\times n_{\text{gen}}$ 中，为什么种群越大单轮开销越高？

单选题 · hard

  • A.每个候选都要评估或实测性能← 正确答案
  • B.交叉和变异的计算量线性增大
  • C.草图生成需要更多内存空间
  • D.编译器的优化轮数会变多

答案：A。每轮迭代中每个候选都要过成本模型打分，top-k 还要编译实测，这才是主要开销。交叉变异是轻量操作，草图生成与种群规模无关，编译器优化轮数也不会因种群增大而增多。

Q8. 关于 MetaSchedule 的演化搜索，正确的说法有？

多选题 · hard

  • A.采用种群选择交叉变异的框架← 正确答案
  • B.完全不需要在硬件上做实测
  • C.与 TVM 的统一调度 DSL 集成← 正确答案
  • D.只做随机采样不做定向进化

答案：AC。MetaSchedule 与 Ansor 一脉相承，用种群、选择、交叉、变异的演化框架搜索调度，并集成在 TVM 生态中，支持 Python DSL 描述搜索空间。它仍然需要硬件实测来获得真实适应度，且包含交叉变异的定向进化，并非纯随机采样。

Q9. 为什么不把所有候选直接送到硬件实测，而要先过成本模型？

单选题 · mid

  • A.硬件实测结果本身不可信
  • B.编译加运行的评估开销很大← 正确答案
  • C.成本模型的预测完全准确
  • D.实测会修改源程序的语义

答案：B。每个候选实测都要编译生成可执行代码并运行取时间，开销极大，全量实测在预算上不可行。实测结果是可信的金标准，成本模型预测也不完全准确，实测更不会改动程序语义。

Q10. 下列哪些属于遗传算法的基本组成要素？

多选题 · easy

  • A.种群与初始化方式← 正确答案
  • B.适应度评估函数← 正确答案
  • C.梯度下降优化器
  • D.交叉与变异算子← 正确答案

答案：ABD。遗传算法四大要素是种群（含初始化）、适应度评估、选择、交叉与变异。梯度下降属于神经网络的训练方法，不是遗传算法的组成部分——进化靠“选择压力”而非“梯度方向”来优化。