本章目录

遗传算法（Genetic Algorithm，GA）解决的是搜索和优化问题：把一批候选解编码成染色体，按适应度选择父代，通过交叉和变异产生新解，再重复评价。它适合不容易求导、变量关系复杂、允许近似解的问题。它不是“算一次就保证全局最优”的公式，而是一套带随机性的搜索程序。

本章对应 EE4285-Computational-Intelligence-4-AY2023S2.pdf，下文简称 GA 课件，页码均为 PDF 页码；练习对应 Tut-6.pdf。先理解编码，再计算适应度，最后动手完成选择、交叉和变异。

1 从候选解到染色体

一个个体（individual）代表一个候选解，一组个体构成种群（population）。染色体（chromosome）是解的编码；基因（gene）是编码中的一个组成部分；基因座（locus）是位置；等位值（allele）是该位置允许的取值。基因型（genotype）指编码，表现型（phenotype）指解码后的实际方案。[GA 课件 pp14–25]

例如用四位二进制 0111 表示整数 7，0111 是基因型，7 是表现型，而目标函数值还要另算。不要把“解码后的 x”和“目标值 f(x)”混为一谈。一般 GA 可以采用二进制、整数、实数或排列编码；课件中的经典遗传算法 CGA 特指固定种群、二进制编码和基本选择交叉变异算子。[GA 课件 pp16–20]

二进制解码公式

若变量在闭区间内取值，以 L 位二进制表示，令整数编码为 k，则端点包含式映射为：

其中最右边是最低位 b₀。公式中的分母是 2ᴸ−1，因为整数 k 从 0 到 2ᴸ−1，一共有 2ᴸ 个可表示点，相邻点之间只有 2ᴸ−1 段。分辨率为：

若要求相邻可表示点间隔不超过 ε，位数应满足：

这最后一式是由课件 p25 的映射公式推导得到的位数条件；如果题目直接给整数范围，也可按“需要多少个不同整数”确定编码位数。

例1 自编 解码和精度

在区间 [−2,6] 使用 4 位编码，染色体 1010 对应 k=10：

这时分辨率为 8/15≈0.5333。若要求间隔不超过 0.1，需要 2ᴸ−1≥80，即 L≥7。注意“四位二进制整数 10”并不表示实际变量 x=10，实际变量还要经过区间映射。

2 目标函数和适应度函数

目标函数描述原问题，例如路线长度、分类误差或收益。适应度函数（fitness function）描述 GA 中个体有多值得被选中。二者可以相同，也可能需要转换。[GA 课件 pp26–27]

若最大化的目标值均为非负数，可以直接采用 F(x)=f(x)。若最小化非负代价 J(x)，课件给出的常见转换是：

J 越小，F 越大。但必须检查定义域：若 J 可能为负，直接套用这个式子可能产生负适应度、除零或排序问题。已知下界 Jmin 时，可以采用：

这是一种明确的平移转换示例，不是所有优化问题唯一的适应度定义。排名选择和锦标赛选择也不要求把原始目标值直接当概率。

Tut6 Q4 的题意检查

题目给出 z=x²−2y+3，称自变量为 x 和 y，随后却写“variables x, and z are in the range 0–7”。这处变量描述有歧义。若按常见出题意图，假设 x、y 都是在 0 到 7 的整数，则每个变量 3 位，拼接成 6 位染色体即可；这个假设需要写明，不能悄悄把题目中的 z 改成 y。[Tut6 p1 Q4]

在上述假设下，z 的最小值是 −11，于 x=0、y=7 处取得；最大值是 52，于 x=7、y=0 处取得。因此可取：

对最优候选，F=1；对最差候选，F=1/64。直接写 1/(1+z) 则不合适。若题目真正约束的是 x 与 z，而未规定 y 的范围，上述 6 位整数编码就不能直接使用。

3 轮盘赌选择到底算什么

轮盘赌选择（roulette-wheel selection）按适应度占比分配概率：

适用条件是每个 Fᵢ≥0 且总和大于 0。N 是种群数量；pᵢ 是一次抽样选到个体 i 的概率；nᵢ 是重复抽 N 次后该个体的复制次数；平均适应度为 F̄。期望复制次数可以是小数，实际复制次数一定是整数。[GA 课件 pp28–34]

如果所有适应度都为零，上式没有定义，应预先规定均匀选择等处理办法。如果适应度有负值，也不能直接除以总和。最优个体概率较大，但并不保证每一代都被选中；若要保留当前最优解，需要额外采用精英保留（elitism）。

例2 课件算例复算

最大化 f(x)=x²，x 取 0–31 的整数，使用五位二进制。初始种群见 GA 课件 pp43–49。

染色体 x F=x² 选择概率 N=4 时的期望复制次数
01101 13 169 169/1170≈0.1444 0.5778
11000 24 576 576/1170≈0.4923 1.9692
01000 8 64 64/1170≈0.0547 0.2188
10011 19 361 361/1170≈0.3085 1.2342

总适应度为 1170，平均适应度为 292.5。概率应加起来等于 1，期望复制次数应加起来等于 4；这是两个快速自检点。

沿表格顺序，累积概率约为 0.1444、0.6368、0.6915、1。为了演示实际抽样，另设四个均匀随机数 0.10、0.20、0.60、0.90。它们分别选中第 1、2、2、4 个个体，得到复制次数 (1,2,0,1)。这与课件给出的一组实际次数一致，但这组随机数是本章补充的演示，并非课件记录。

4 交叉与变异

单点交叉（one-point crossover）选定一个切分位置，交换两个父代该位置之后的部分；双点交叉（two-point crossover）交换两个切分位置之间的片段；均匀交叉（uniform crossover）按掩码决定每一位继承哪个父代。[GA 课件 pp35–37]

继续上面的种群，交配池为 01101、11000、11000、10011。按课件 p49 的切分位置：

父代1  0110|1       子代1  0110|0 = 12
父代2  1100|0       子代2  1100|1 = 25

父代3  11|000       子代3  11|011 = 27
父代4  10|011       子代4  10|000 = 16

若本轮没有实际发生变异，新种群适应度为 144、625、729、256，总和 1754，平均值 438.5，最大值 729。课件 p49 把平均值取整写成 439；写精确计算应保留 438.5。这一轮的最佳值从 576 提升到 729，但还没有到理论最大值 31²=961。

变异（mutation）在二进制编码中通常指逐位独立翻转 0 与 1。如果有 N 个个体，每个 L 位，每位变异概率为 pm，则：

对本例 N=4、L=5、pm=0.001，期望变异位数为 0.02，至少一位变异的概率约为 1.9811%。不能据此说“20 位太少所以一定不会变异”。课件 p51 用“每 1000 位变异一次”作直观描述，应理解为长期平均，而不是每累计 1000 位就强制翻转一次。

5 Tut6 Q3 完整手算

此题不是二进制编码，而是八个取值在 0–9 的数字基因。适应度定义为：

这里公式中的字母 f 同时被用作函数名和第六个基因，阅读时要分清。[Tut6 p1 Q3]

个体 染色体 展开计算 适应度
x₁ 65413532 (6+5)−(4+1)+(3+5)−(3+2) 9
x₂ 87126601 (8+7)−(1+2)+(6+6)−(0+1) 23
x₃ 23921285 (2+3)−(9+2)+(1+2)−(8+5) −16
x₄ 41852094 (4+1)−(8+5)+(2+0)−(9+4) −19

所以从优到劣为 x₂、x₁、x₃、x₄。第一问只要求评价和排序，出现负适应度本身不妨碍排序；若后续要使用轮盘赌，则需先处理负值。

在中点交叉最优的两个个体：

8712|6601 + 6541|3532
→ 8712|3532 和 6541|6601

得到 87123532 和 65416601，适应度分别为 15 和 17。子代未必超过最优父代的 23，交叉也不是“成绩保证器”。

再对第二优 x₁ 与第三优 x₃ 在 b 和 f 之后切开并交换中间段：

65|4135|32 + 23|9212|85
→ 65|9212|32 和 23|4135|85

得到 65921232 和 23413585，适应度分别为 −2 和 −5。题目只说“points b and f”，答题时最好画出切线，明确自己采用的是在这两个基因后切分的约定。

6 编码必须尊重问题结构

Tut6 Q2 的三种配料数量可以直接用整数向量 (q₁,q₂,q₃) 表示，也可将每个数量分别编码再拼接。模糊规则可以使用离散符号编码，例如 (red, small, round, apple)，其各基因允许的取值集合不必相同。

旅行商问题（TSP）的解是城市排列，例如 (3,5,7,2,1,6,4,8)。这里每个城市必须恰好出现一次，普通单点拼接可能产生重复城市和漏访，因此需要保持排列合法的交叉算子。[GA 课件 pp56、62–64]

课件 p63 的 Order1 例子可按以下方式理解：固定父代1在位置 3–6 的片段 (7,2,1,6)，从父代2的第7位开始循环扫描，跳过已经固定的城市，将剩余 (3,4,5,8) 依次填入子代空位 7、8、1、2，得到 (5,8,7,2,1,6,3,4)。交换两个城市是一种合法的排列变异，因为它仍保证每个城市恰好出现一次。

7 停止条件与考试表达

停止条件可以是达到代数上限、最佳适应度连续若干代没有明显提高、达到可接受目标值，或种群多样性降低。课件也介绍按基因趋同程度判断收敛。[GA 课件 pp42、54]

“收敛”不等于“已证明全局最优”。没有精英保留时，最佳个体还可能丢失；即使保存历史最优，当前种群平均值也可能下降。课件中的种群数、交叉率和变异率是示例设置，不能作为所有问题的固定标准。

遇到一代进化题，按 编码与解码 → 目标与适应度 → 概率与复制次数 → 父代配对与切分 → 变异 → 新种群评价 写出中间过程。最常见失分是分母误写成 2ᴸ、把期望次数当实际次数、对负适应度直接做轮盘赌、以及漏写切分位置。

8 自测与答案

  1. 用五位二进制表示 [0,31] 内整数，10110 是多少？适应度若为 x²，又是多少？
  2. 三个个体的正适应度为 2、3、5，抽取 10 次，第三个个体的期望复制次数是多少？是否保证恰好出现该次数？
  3. 10 个个体，每个 8 位，每位变异概率为 0.01，期望变异位数是多少？

答案：1. x=22，F=484。2. 概率为 0.5，期望为 5 次，实际不保证是 5。3. 期望为 10×8×0.01=0.8 位，实际位数仍为整数。

本章来源

  • EE4285-Computational-Intelligence-4-AY2023S2.pdf：pp14–25 编码；pp26–34 适应度与选择；pp35–42 算子与停止；pp43–55 数值例；pp56–64 TSP。
  • Tut-6.pdf：p1 Q1–Q4。本文给出的习题结果为独立推导，非官方答案。