4. 编码方案设计与对比

遗传算法并不直接在问题的解上操作，它操作的是解的“表示形式”，也就是染色体。编码方案决定了搜索空间如何被映射、交叉与变异如何生效、约束如何被满足，因此它往往比选择算子、交叉概率更早地决定了算法能否收敛到有意义的解。本节围绕四种最常用的编码——二进制编码、实数编码、排列编码、树编码——说明它们的适用条件、优缺点，以及它们对搜索空间形状和规模的影响。

编码的本质：基因型到表现型的映射

任何编码都包含两层：基因型空间（染色体串本身）与表现型空间（实际问题的解）。二者之间通过解码函数连接。例如二进制编码中，长度为 L 的位串通过解码映射到区间 [a, b] 上的实数；排列编码中，一个 1..n 的排列直接对应一个访问顺序；树编码中，一棵语法树直接对应一个表达式或程序。搜索空间的大小、连通性和“邻域平滑性”都由这个映射决定：如果相邻基因型解码后表现型差异巨大，交叉和变异就会表现得像随机扰动，收敛缓慢；反之，映射平滑则局部搜索更有效。

二进制编码：经典但需警惕精度与悬崖

二进制编码把每个决策变量映射为固定长度的位串。设变量 x ∈ [a, b]，位串长度 L，则解码为 x = a + (b−a)·d / (2^L − 1)，其中 d 是位串对应的十进制整数。它的优点是模式定理（schema theorem）在二进制下表述最自然，交叉与变异算子简单，且天然适合 0-1 决策问题（如特征选择、背包问题）。

缺点同样明显。第一是精度与长度的矛盾：若要求区间内分辨率达到 1e-6，长度需约 20 位以上，多变量时染色体迅速变长。第二是“汉明悬崖”：相邻整数 7（0111）与 8（1000）在表现型上只差 1，但基因型上 4 位全部不同，交叉后子代可能跳到很远的位置，破坏邻域平滑性。第三，对连续优化，二进制编码的搜索空间是离散格点，无法表达格点之间的解。实践中若坚持二进制，可缩短串长、采用格雷码（Gray code）缓解悬崖，或对每个变量独立编码并配合多点交叉。

实数编码：连续优化的默认选择

实数编码直接用浮点数向量作为染色体，基因型与表现型一一对应，没有解码损失。它适合变量为连续实数的优化问题，如函数极值、神经网络权重、控制器参数整定。其搜索空间是连续超矩形，邻域平滑，变异可以按高斯分布 x' = x + N(0, σ) 做局部扰动，交叉可采用模拟二进制交叉（SBX）或算术交叉 c = α·p1 + (1−α)·p2。

实数编码的优点是精度不受串长限制、易于加入边界约束和线性约束、与梯度类局部搜索（如 GA + 拟牛顿混合）衔接自然。缺点是普通单点交叉对实数意义不大，必须专门设计交叉算子；同时连续空间容易在早期被少数高适应度个体占据，导致早熟。工程上常配合精英保留、自适应变异概率和种群多样性度量来缓解。

排列编码：顺序即解

排列编码用 1..n 的一个排列表示解，典型场景是旅行商问题（TSP）、作业车间调度、装配顺序规划。它的搜索空间大小为 n!，增长极快：n=10 时约 363 万，n=20 时已超过 2.4×10^18。排列编码的最大优点是“天然满足约束”——每个城市恰好访问一次、每个工件恰好排一次，无需罚函数。

难点在算子设计。普通单点交叉会把同一元素重复或丢失，产生非法排列，因此必须使用顺序交叉（OX）、部分匹配交叉（PMX）、循环交叉（CX）等保排列算子；变异常用交换、逆序或插入。以 OX 为例：随机选两切点，保留父代 1 的中间段，其余位置按父代 2 中未出现的元素顺序填充，从而保证子代仍是合法排列。排列编码的搜索空间是离散的排列组合，邻域由“交换两个位置”定义，规模随 n 爆炸，因此大规模问题常需结合局部搜索或问题特定启发式。

树编码：面向结构与程序

树编码（遗传编程，GP）用一棵语法树表示解，叶节点是变量或常数，内部节点是运算符或函数。它适合符号回归、表达式发现、分类规则、程序合成等“解本身是变长结构”的问题。搜索空间是所有合法语法树的集合，规模随深度指数增长，且是变长的。

树编码表达力强，但代价高：交叉需交换两棵树的子树，变异需替换子树或节点，且必须保证语法合法（如运算符参数个数匹配）；树容易“膨胀”（bloat），即无意义分支不断增长导致评估昂贵，通常用最大深度限制、惩罚复杂度和简约压力（parsimony pressure）控制。评估一次往往要解释执行整棵树，计算成本远高于前三种编码。

如何选择：从问题结构出发

选择编码的第一原则是看解的自然结构：解是 0-1 组合就选二进制；解是连续向量就选实数；解是顺序就选排列；解是表达式或程序就选树。第二原则是看约束：若约束能被编码天然满足（如排列），就避免用罚函数。第三原则是看搜索空间规模与邻域平滑性：连续问题用二进制会引入悬崖，离散顺序问题用实数则毫无意义。

需要强调的是，编码不是中立的实现细节。它改变了搜索空间的几何形状，也改变了交叉和变异所隐含的“邻域”含义。同一问题用二进制和实数编码，即使种群规模、交叉概率完全相同，收敛轨迹也可能截然不同。因此在设计遗传算法时，应把编码方案与算子设计、约束处理、适应度函数放在一起整体考虑，并通过小规模对比实验（固定随机种子、比较收敛代数与最优值）验证所选编码是否真的适合当前问题。