3. 遗传算法基本原理与术语

遗传算法（Genetic Algorithm, GA）的直观来源是生物进化，但真正落地到优化模型时，必须把“个体、种群、基因、染色体、适应度、选择、交叉、变异”这些术语翻译成程序里可存储、可运算、可评价的数据结构。理解这一层映射，是后续设计编码方案、算子与终止条件的前提。本节围绕“一个解如何被表示、一群解如何被评价、评价结果如何驱动下一代”这条主线展开。

一、个体与染色体：一个候选解的双重身份

在优化问题中，个体（individual）代表一个候选解。它有两副面孔：对外，它是问题空间中的一个解，例如一组参数 (x₁, x₂, …, xₙ)；对内，它是算法空间中的一条染色体（chromosome），通常表示为一个定长串。染色体上的每一位称为基因（gene），基因的取值称为等位基因。编码方式决定了“串”与“解”之间的换算关系，常见有二进制编码、实数编码、整数/排列编码。

以连续参数优化为例，设变量 x ∈ [−5, 5]，用 8 位二进制编码，则染色体 10110100 对应的解码为：先按无符号整数读得 180，再线性映射 x = −5 + 180 × 10 / (2⁸ − 1) ≈ 2.06。这里 8 位就是基因位，10110100 是染色体，2.06 是该个体在问题空间中的表现型。编码精度由位长决定：位长越长分辨率越高，但搜索空间也越大。实数编码则直接把 x 的浮点值作为基因，省去编解码，适合高精度连续问题。

二、种群：并行搜索的基本单位

种群（population）是若干个体的集合，规模记为 N。GA 不是从单点出发，而是同时维护 N 个候选解，这正是它具备全局探索能力的原因。种群规模是重要参数：N 过小易早熟收敛、多样性不足；N 过大则每代评价成本高、收敛变慢。工程上常取 20～100，评价代价高（如每次评价需跑一次仿真）时可取 10～30，并配合多次独立运行。

种群还承载“多样性”这一隐性资源。若所有个体染色体高度相似，交叉产生的后代也难有突破；反之多样性过高则接近随机搜索。后续的选择压力、变异率，本质上都是在“利用已有优良基因”和“维持多样性”之间做平衡。

三、适应度：把优化目标变成可比较的分数

适应度（fitness）是个体优劣的量化指标，由适应度函数计算。它通常由目标函数改造而来：最大化问题可直接取 f(x)，最小化问题常取 1/(1+f(x)) 或 C − f(x)（C 为足够大的常数），以保证适应度非负且越大越好。若存在约束，可用罚函数把违约量折算进适应度：

fitness(x) = 1 / (1 + f_obj(x) + M * violation(x))
# f_obj 为目标函数，violation 为约束违约量，M 为罚系数

适应度是选择操作的唯一依据，因此它的设计直接决定搜索方向。需要注意两点：一是适应度必须与真实目标单调一致，否则算法会“优化错的东西”；二是要防止超级个体垄断——若某个体适应度远高于其他个体，轮盘赌选择会使其后代迅速占满种群，导致早熟。常用对策是适应度缩放（如线性缩放、秩排序），把原始适应度转换为选择概率时压缩差距。

四、选择、交叉、变异：驱动种群演化的三个算子

选择（selection）按适应度从当前种群中挑出繁殖个体，体现“优胜”。轮盘赌选择中，个体 i 被选中的概率 pᵢ = fᵢ / Σfⱼ；锦标赛选择则随机取 k 个个体、取其中最优者，k 越大选择压力越强。选择只复制，不产生新基因。

交叉（crossover）把两个父代染色体的片段交换，产生新组合，是探索新解的主要手段。单点交叉在随机位置切开、交换尾部；实数编码常用算术交叉，如子代 = α·父代₁ + (1−α)·父代₂。交叉概率 p_c 通常取 0.6～0.9。

变异（mutation）以较小概率随机改变基因值，如二进制位翻转、实数加高斯扰动。它负责引入新基因、维持多样性，防止种群陷入局部最优。变异概率 p_m 一般取 0.001～0.1（按位），过高会退化为随机搜索。

三者的分工可以概括为：选择提供方向，交叉组合已有优良片段，变异补充缺失信息。下图展示了从种群评价到生成下一代的完整信息流，以及各术语在其中的位置。

五、一个可手算的小例子

设最大化问题 f(x) = x²，x 为 0～7 的整数，用 3 位二进制编码，种群 N = 4，初始个体为 001(1)、010(2)、101(5)、111(7)。适应度直接取 x²，得 1、4、25、49，总和 79。轮盘赌选择概率分别为 0.013、0.051、0.316、0.620，可见 111 被选中的机会最大。若对 101 与 111 在第二位后单点交叉，得 101 与 111 交换尾部：101|→101，111|→111 不变；换一对 001 与 111 交叉得 001 与 111 交换后为 011(3) 与 101(5)，子代适应度为 9 与 25，优于原来的 1。若再对 010 的第 3 位变异为 011(3)，适应度由 4 升到 9。经过若干代，种群会向 111 聚集，最终收敛到 x = 7、f = 49。这个例子说明：适应度决定谁被选中，交叉重组片段，变异提供新值，三者共同推动种群向高适应度区域移动。

六、术语在优化模型中的角色对照

需要强调的是，这些术语不是彼此独立的标签，而是一条闭环上的环节：编码决定搜索空间的形状，适应度决定搜索的方向，选择、交叉、变异决定搜索的方式。任何一个环节设计不当，都会以“收敛过早”“收敛过慢”或“结果不可用”的形式暴露出来。因此在进入具体算子实现之前，先把本节这套对象—评价—演化的映射关系理清，后续的参数整定与结果验证才有依据。