3.2 进化算法搜索

3.2 进化算法搜索

本节摘要：进化算法把架构当作种群个体，用选择、交叉、变异模拟自然进化。本节讲清"初始化种群→适应度评估→选择→交叉→变异→迭代"六步流程，展开 AmoebaNet 的规则化锦标赛选择与年龄正则化、ENAS 的进化+参数共享组合，并分析其全局搜索强、并行性好、但成本高、收敛慢、超参数敏感的三重代价。

本节要回答的问题

阅读完本节，你应当能够：

1. 复述进化算法搜索的六步流程，并说明每一步在 NAS 语境下的含义
2. 解释轮盘赌选择与锦标赛选择的区别
3. 说清 AmoebaNet 的规则化锦标赛选择与年龄正则化各自解决什么问题
4. 评价进化算法在全局搜索、并行性、计算成本三个维度的表现

一、问题与直觉：让架构像物种一样进化

生物进化有个朴素又有效的逻辑：遗传变异加自然选择，几亿年造出千万物种。进化算法 NAS 把这套逻辑搬到架构搜索上——架构就是个体，性能就是适应度，好架构繁殖、差架构淘汰，种群一代代变强。

这个思路能成立，靠的是三个生物学的"先见之明"。第一，进化不用梯度——它不要求空间可微，这是它比梯度方法宽容得多的地方，任何编码形态的架构都能进化。第二，进化天然并行——种群里的个体互相独立，评估可以铺在多卡上同时跑。第三，进化擅长全局探索——交叉和变异保证种群多样性，不容易一头扎进局部最优坑里出不来。

但代价也写在基因里：进化是靠"死得多"来"活得好"的。每个个体都要评估，种群规模一大，评估账单就吓人。SOURCe 的原话是：计算成本高、收敛速度慢、超参数敏感。进化的"慢"不是算法慢，而是评估慢——它把预算都花在"试"上，而每次试都可能是上万 GPU 小时。

二、核心原理：六步流程与两个关键技巧

流程。初始化种群——随机生成一组架构当初始种群。评估适应度——在验证集上评估每个个体，性能就是适应度。选择——按适应度挑父母，轮盘赌（适应度高的个体被选概率大）或锦标赛（随机抽几个个体，留最优）都常用。交叉——把两个个体"基因"组合出后代，在 NAS 里就是对结构、连接、超参数做组合。变异——随机改一点（换个操作、加条连接），保持种群多样性，防局部最优。迭代——循环评估-选择-交叉-变异，直到收敛或达到迭代上限。

关键技巧一：规则化锦标赛选择。AmoebaNet 用了一种"简化版"进化——规则化锦标赛选择。流程是：维护一个架构种群，每次随机挑两个个体做锦标赛，胜者被复制一份并变异，然后塞回种群，同时把种群中最老的个体淘汰。这个设计的妙处：它绕开了传统进化的复杂交叉操作，只用"锦标赛+复制+变异+淘汰最老"四个动作，简单到容易实现，且性能与 NASNet 相当。淘汰"最老"而不是"最差"，给新个体留了成长空间。

关键技巧二：年龄正则化。AmoebaNet 的另一个创新。给每个个体记一个"年龄"——在种群中存活的时间。变异产生的新个体年龄小，有优先权；老个体即使当前表现好，也可能被新个体顶替。这逼着种群持续探索新结构，而不是锁死在某个局部最优附近反复打磨。年龄正则化是对"利用过头"的刹车，它主动牺牲一点"当下最优"，换"未来可能更好"。

组合打法：ENAS 的进化+参数共享。ENAS 通常被归为强化学习，但它的 DAG 子图搜索也可以用进化驱动。ENAS 维护一个覆盖所有可能结构的超网络，进化搜索在其中找最优子图。关键是参数共享——不同子图复用超网络权重，避免了"每个个体从头训"的巨额成本。这个组合展示了进化的模块性：进化管"选哪条路"，参数共享管"路怎么便宜地评估"，两个模块各干各的、互不干扰。

三、工程实践要点：进化的调参与权衡

超参数怎么定。种群规模、交叉概率、变异概率三个参数决定搜索行为。经验法则：种群规模别太小（至少几十），否则多样性不足；变异概率别太大（0.1-0.3 量级），否则进化退化成随机搜索；交叉概率可以高（0.7 左右），它是"继承好基因"的主力。但这些数字必须结合评估成本调整——评估越贵，种群越小、变异越大，用牺牲质量换可行性。

并行是进化的最大红利。种群评估天然可并行，多卡时几乎线性加速。这是进化相对贝叶斯优化的核心优势——贝叶斯的代理模型更新是串行的，进化的评估是并行的。算力够、要抢时间，进化是个好选择。

别忽视局部最优。SOURCE 明说进化"容易陷入局部最优"——这不矛盾吗？全局搜索强还能局部最优？原因在于：进化找到好区域后，变异幅度通常变小（否则会破坏好基因），于是新个体都聚在已发现的好解附近，整个种群"内卷"，不再探索远处。年龄正则化就是治这个病的，但参数没调好时会失效。

⚠️ 常见坑：把交叉操作直接套在图结构上。图交叉如果实现得粗暴（比如随机切边拼接），很容易产生无效架构（断连的图）。要么用规范的图编码（第 2.4 节），要么像 AmoebaNet 一样干脆不做交叉。

💡 关键直觉：进化的核心变量不是"变异多聪明"，而是"淘汰谁"。AmoebaNet 用"淘汰最老"替代"淘汰最差"，本质是把时间维度引入选择——这是它对传统进化的最大贡献。

四、进化算法的变体与调参实践

三种常见进化变体

SOURCe 在 3.2 节末尾的对比里提到遗传算法（GA）和差分进化（DE），第 6 章还会提到进化策略，这里把三者讲清。遗传算法最经典：架构编码成"基因"（通常是第 2.4 节的字符串或图编码），选择、交叉、变异三个算子齐全，交叉是主力（把两个父母的基因片段组合出孩子）。进化策略（ES）更像"只变异不交叉"的版本——它围绕一个或几个个体做随机扰动，用扰动的适应度指导下一轮方向，参数少、实现简单，AmoebaNet 的"复制+变异"就是它的简化版。差分进化介于两者之间：用一个差分向量（两个个体的差）指导变异方向，适合连续编码的架构参数优化。三者的共同骨架都是"评估-选择-变异"，区别在交叉怎么用、变异怎么扰——理解骨架比记变体名字重要。

调参的实操顺序

进化算法的超参数不少：种群规模、代数、交叉概率、变异概率、选择方式、淘汰策略。一次全调是灾难，按优先级来：第一优先定"评估预算"——总共能评估多少架构，这决定了种群规模与代数的乘积上限；第二定种群规模——经验上从几十到几百，太小多样性不足，太大评估扛不住；第三定变异概率——先给一个保守值（0.1-0.3），观察种群是否过早收敛（收敛则调大变异）；最后才碰交叉概率和选择方式。SOURCe 提醒进化"超参数敏感"，所以每次只动一个旋钮、记录效果，是标准操作。

过早收敛的识别与对策

进化算法最典型的翻车是"种群内卷"：所有个体长得越来越像，最终锁死在某个局部最优附近。识别方法很简单——看种群多样性（不同架构的个数或距离），多样性塌缩就是信号。对策按效果排序：加大变异概率（直接注入随机性）；换淘汰策略（像 AmoebaNet 那样淘汰"最老"而不是"最差"，给新个体留空间）；重置部分种群（每隔若干代随机引入一批新个体）。年龄正则化正是"淘汰最老"的机制化，它解决的就是这个问题。

进化算法的适用场景速查

什么时候值得为进化算法付出评估账单？三个条件同时满足时：搜索空间大且形态复杂（链式、多分支、图结构都能进化）；评估可以被便宜化（权重共享、代理任务配合，第 4 章）；计算资源允许并行评估（多卡）。反之，如果空间小、评估贵、又赶时间，进化的性价比就很低，梯度或贝叶斯更合适——这个判断在 3.7 节会再收束一次。

五、FAQ：进化算法搜索的常见疑问

进化算法和随机搜索的区别到底在哪？

两者都会"随机采样"，但性质不同。随机搜索每次采样完全独立，不利用历史结果；进化算法每次变异都在已有好个体的基础上做局部扰动，这是对历史信息的利用——虽然粗放（只记住"谁好"，不记"为什么好"），但确实不是纯随机。可以这样记：随机搜索是"从零抽签"，进化是"在好签周围多抽几支"。

交叉在 NAS 里为什么常常被弱化？

理论上交叉是进化的核心算子（组合好基因），但在架构搜索里，交叉的实现很难——图结构的交叉如果切得不好，会产生无效架构（断连、环）。AmoebaNet 干脆不做交叉，只用"复制+变异"，效果依然顶尖。工程上的经验是：如果交叉实现不顺手，先删掉它，纯变异版本通常已够用——进化的主力是"选择谁"和"淘汰谁"，不是交叉本身。

进化算法能找到 DARTS 搜不到的结构吗？

方向不同。DARTS 类梯度方法要求空间可微，结构形态被可微性约束住；进化算法对空间形态几乎没有限制，理论上可以探索更多样的拓扑。SOURCe 对进化的评价是"可以探索非梯度可微的搜索空间"——这是它相对梯度方法的独特价值。所以"进化和梯度谁强"没有答案，它们探索的是不同形状的空间。

种群规模到底多大合适？

没有标准答案，但有一个判断公式：种群规模 × 代数 ≈ 总评估预算 ÷ 单次评估成本。预算定了、单次评估成本定了，两者乘积就定了。在这个约束下，小种群多代数适合"变异多、探索密集"的路线，大种群少代数适合"并行评估、广度优先"的路线。记住这个公式，就不会凭空纠结种群规模该设几。

• 六步流程：初始化→评估→选择→交叉→变异→迭代
• 选择方法：轮盘赌重概率，锦标赛重排序，AmoebaNet 用随机两两锦标赛
• 规则化锦标赛：只做"复制+变异+淘汰最老"，简单到极致
• 年龄正则化：用时间维度逼种群探索新结构
• ENAS 组合：进化选路径 + 参数共享降评估成本
• 并行红利：评估天然并行，多卡近线性加速
• 三代价：计算成本高、收敛慢、超参数敏感

下一节看强化学习搜索——让一个 RNN 控制器学会"生成好架构"。

图3-2 进化算法搜索的循环流程