2.4 搜索空间的编码方式

2.4 搜索空间的编码方式

本节摘要：编码方式决定架构如何"说"给算法听，直接影响搜索效率与结果质量。本节先讲编码的完备性、有效性、可区分性、可扩展性四条标准，再对比直接编码（定长/变长）、图编码（DAG/邻接矩阵）、DSL 语法编码、Cell/Block 编码、嵌入编码五类方案，最后给出按空间规模、算法类型、可解释性需求选编码的决策框架。

本节要回答的问题

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

1. 说出好编码的四条标准：完备性、有效性、可区分性、可扩展性
2. 对比定长字符串、变长字符串两种直接编码的适用场景
3. 解释图编码为什么是 Cell 空间的主流表示，以及图同构问题的麻烦
4. 根据搜索空间规模、搜索算法类型、可解释性需求选出合适编码

一、问题与直觉：架构是"蓝图"，编码是"语言"

你想让一位画家临摹一幅画，不能直接把画传过去，得先把它描述成文字或草图。NAS 也一样——搜索算法是"画家"，架构是"画"，编码就是描述这幅画的"语言"。语言好不好用，直接决定画家能不能准确、高效地临摹出来。

这个类比带出一个容易忽视的事实：编码不是中立的。同样的架构集合，用不同编码表示，搜索算法看到的"地形"完全不一样。固定长度字符串编码下的搜索空间，和 DAG 图编码下的搜索空间，对进化算法的交叉、变异操作而言是两种不同的世界。选择编码本质上是选择"算法将在什么形态的搜索空间里工作"。

SOURCE 给出了好编码的四条标准，正好当本节的组织框架：完备性——能表示空间里所有架构，不漏解；有效性——信息能高效传给算法，方便搜索优化；可区分性——不同编码对应不同架构，无歧义；可扩展性——能适应不同规模的空间，支持灵活扩展。

二、核心原理：五类编码方案

直接编码：定长字符串/向量。把架构的属性直接映射到编码的各个维度。定长编码像填表，每个位置代表一层类型，比如"CV-MP-RE-FC-SM"表示"卷积-最大池化-ReLU-全连接-Softmax"五层结构。优点简单直观、便于遗传算法交叉变异；缺点表达能力有限——定长表填不出复杂连接关系，而且冗余（有些位置的编码不影响架构）。适合结构相对固定的简单空间。变长编码放松了长度限制，用 RNN 等生成器输出变长序列，可以表达跳跃连接（如 ADD(1,3) 表示第 1 层和第 3 层输出相加）。表达能力增强，但解码复杂、搜索难度上升。

图编码：DAG 与邻接矩阵。节点代表计算层/操作，边代表数据流。Cell 空间的 DAG 表示天然贴合"节点-边-操作"的语言，图神经网络还能直接消费这种表示做性能预测。优点：灵活表达任意拓扑、可视化友好、能接图算法；缺点：编码解码复杂、搜索空间庞大、需要处理图同构问题（不同图可能表示同一架构，导致重复搜索）。

DSL 语法编码。定义一套形式文法来描述架构生成规则，编码是一系列推导步骤。比如 <Network> ::= <Layer> | <Layer> <Network> 这种产生式，一步步推导出具体网络。优点：结构化表达、语法约束能挡掉无效架构、可解释性强；缺点：语法设计本身费劲、语法约束可能误伤潜在好解、编解码要写解析器。

Cell/Block 编码。把架构分解成重复单元，编码描述单元内部连接与操作。这是 NASNet、DARTS 的实际工作方式——空间小、可迁移、结构化，是图像任务在算力受限时的高性价比选择。Block 编码粒度更大，能表达残差块、密集块这类更复杂的组合。

嵌入编码。用图神经网络或自编码器把架构映射到连续低维向量，相似架构在嵌入空间里距离近。优点：语义表达强、连续空间能用梯度优化、便于可视化；缺点：训练嵌入网络成本高、嵌入质量直接决定搜索效果、解码回具体架构困难。DARTS 的连续松弛在精神上与它一脉相承——都是把离散空间"泡进"连续空间。

三、工程实践要点：按场景选编码

看空间规模。小空间、结构简单——定长字符串/向量够用，实现成本最低。大空间、结构复杂——图编码或 Cell/Block 编码，表达力才够。超大空间、要探索新范式——嵌入编码值得投，但代价是训练嵌入网络。

看搜索算法。梯度优化要求编码空间连续可微，直接排除离散的定长字符串，嵌入式编码或 DARTS 式连续松弛才对路。进化算法对编码形态最宽容，字符串、图都能交叉变异。贝叶斯优化要能定义"架构之间的距离"（核函数），图编码或嵌入编码更好算距离。

看可解释性需求。要事后分析"为什么搜出这个架构"——DSL 语法编码最强，推导步骤就是设计理由；图编码次之，可视化直观；嵌入编码最弱，向量说不出人话。

趋势提醒。SOURCE 预判编码会走向自动化：自动学习编码方式（让算法自己学怎么表示架构）、混合编码（语法与嵌入结合）、自适应编码（按搜索反馈动态调）、面向硬件的编码。这些方向说明"编码"这个环节本身也开始被自动化——但当前工程实践中，手工选对编码仍是收益最高的一步。

⚠️ 常见坑：图编码不处理图同构问题，同一架构被当作多个候选反复评估，浪费算力还污染性能统计。用规范化表示（如按拓扑序排列邻接矩阵）能缓解。

💡 关键直觉：编码方式没有绝对优劣，只有"与算法配不配"。给遗传算法一个连续嵌入空间，给梯度方法一个离散字符串空间，都是灾难——编码必须和搜索算法背靠背设计。

四、编码实例深读：从字符串到连续权重

把定长字符串编码走到底

SOURCe 给的例子 "CV-MP-RE-FC-SM" 是理解直接编码的最好起点。它每个位置代表一层类型，5 个位置就是 5 层。它的优点和缺陷都写在形式上：优点是可解释、可交叉（遗传算法把两个字符串切开拼接就生成新架构）；缺陷是长度僵化——一旦搜到第 6 层，这个编码就用不了了。SOURCe 指出固定长度编码"难以表达复杂和变长的架构，无法表示不同层之间复杂的连接关系"，这句话点破了直接编码的天花板。如果要表达跳跃连接，就得用变长编码，比如 "CV(3x3)-RE-MP-CV(5x5)-RE-ADD(1,3)-FC-SM"，其中 ADD(1,3) 表示把第 1 层和第 3 层的输出相加——注意这个"第几层"的编号是相对位置的，一旦前面插入新层，编号全部失效，这就是变长编码在交叉操作时的痛点。

把图编码走到底：邻接矩阵与操作矩阵

图编码的工程形态通常是"邻接矩阵 + 操作矩阵"的组合：邻接矩阵记录"谁连谁"，操作矩阵记录"每条边的操作类型"。这种双矩阵表示可以直接喂给图神经网络做性能预测（第 4.5 节零成本代理的一种实现），也可以被进化算法的交叉变异直接操作。它的经典难题是图同构：同一个架构可能有多种矩阵表示（节点编号顺序不同），导致搜索重复评估。缓解手段是用规范化表示——按拓扑序给节点编号，让同一个架构只有一种矩阵写法。

从离散编码到连续权重：DARTS 的桥梁

第 2.4 节讲了五种编码，但 DARTS 的编码不在其中——它是一种"连续松弛编码"：不是"选哪个操作"，而是"每个操作一个权重、softmax 后加权混合"。严格说，DARTS 没有把架构"编"成一个静态字符串或矩阵，而是把架构参数直接作为可学习变量嵌进网络。这个设计绕开了"编码-解码"的循环，代价是丢失了编码的可解释性。工程上的选择逻辑是：要可解释、要跨算法兼容，用离散编码（字符串/图/DSL）；要极致的搜索效率，用连续松弛。两种路线在第 3.4 节会正面相遇。

五、FAQ：编码方式选型的高频问题

字符串编码和图编码能互相转换吗？

能，但有信息损耗。字符串编码天然适合"逐层描述"，表达链式结构很自然，表达复杂图结构就吃力；图编码反过来。转换时要小心：从图到字符串的线性化会丢失并行分支结构，从字符串到图则可能引入多余的连接。SOURCe 提示的"图同构问题"在转换时最容易被忽略——不同字符串可能映射到同一张图。

为什么 DSL 编码可解释性最强？

因为 DSL 编码是"规则的推导"，它记录的不是架构快照，而是"架构是怎么一步步生成出来的"——每个推导步骤都是设计理由。SOURCe 强调语法编码"可解释性强，可以分析架构的生成过程和设计原理"。代价是设计语法本身就是个费力的工程，而且语法约束可能误伤空间外的潜在好解。

嵌入编码是万能的吗？

不是。嵌入编码（把架构映射成连续向量）的吸引力在于"语义空间 + 连续可微"，但它有三个硬伤：训练嵌入网络要额外算力和数据；嵌入质量直接决定搜索效果；把向量解码回具体架构往往很难。SOURCe 明确指出"嵌入向量的质量直接影响搜索效果，需要仔细设计嵌入网络和训练策略"。工程上，嵌入编码适合"空间极大、需要语义检索"的场景，小规模空间用不上它。

收束：编码是空间与算法的"翻译官"

把本节与第 2.1 节连起来看，编码的本质就清楚了：空间是"架构的集合"（数学对象），编码是"架构的语言"（计算对象），搜索算法只能通过语言与集合对话。语言选得不好，算法的能力就翻译不出来——给梯度方法翻译成离散字符串，给遗传算法翻译成连续向量，都是"话不投机"。所以编码选型的最终标准只有一条：它与搜索算法的匹配度。这条标准会一直带到第 3 章：读到每个策略时，回想它需要什么样的编码才能发挥全力。

• 四条标准：完备性、有效性、可区分性、可扩展性
• 直接编码：定长简单但僵化，变长灵活但复杂
• 图编码：Cell 空间主流，要处理图同构问题
• DSL 编码：约束强、可解释强，但设计成本高
• 嵌入编码：连续空间利于梯度优化，但训练与解码贵
• 选型三问：空间多大、算法要什么形态、要不要可解释
• 编码与算法匹配：背靠背设计，别分开拍板

下一章进入第二根支柱——搜索策略。空间已经画好，现在要看怎么在空间里高效移动。

图2-2 架构编码方式对比矩阵