遗传算法零基础教程

本教程依据课件《3-智能优化算法》中关于“优化、智能优化算法、遗传算法、背包问题、路径规划/TSP”等内容整理而成。目标读者是没有算法基础的同学，因此会先用生活例子解释概念，再给出公式、表格、例题与解析。

1. 先理解：什么是“优化”？

“优化”就是：在很多可选方案中，找到一个尽量好的方案。

生活里有很多优化问题：

场景	想优化什么	可能的目标
一个月生活费怎么花	花钱方案	满足需求的同时尽量省钱
小超市商品定价	价格方案	利润最大
外卖配送路线	送餐顺序和路径	总路程最短
工厂生产安排	生产计划	成本最低、利润最高、效率最高

从数学上看，优化通常可以写成：

在约束条件下，使目标函数取得最大值或最小值

例如：

max f (x)

表示寻找一个方案 $x$ ，让目标函数 $f (x)$ 尽可能大。

如果是“成本越低越好”，则可以写成：

min f (x)

2. 什么是智能优化算法？

传统优化方法通常依赖严密数学推导，例如梯度下降法、牛顿法等。这类方法常常希望目标函数可导、表达式明确。

智能优化算法不一定要求这些条件。它更像一种“聪明的搜索”：只要能评价一个方案好不好，就可以不断尝试、比较、改进。

课件中提到，智能优化算法也常被称为：

名称	含义
启发式算法	不保证每一步都严格最优，但用经验规则提高搜索效率
仿生算法	模仿自然界、生物群体或物质变化过程
演化算法 / 进化算法	模仿生物进化过程

常见智能优化算法包括：

算法	灵感来源
遗传算法	达尔文进化论：自然选择、生物遗传
粒子群算法	鸟群觅食和群体协作
蜂群算法	蜜蜂寻找蜜源
鱼群算法	鱼群觅食、聚群、追尾

本教程重点学习遗传算法。

3. 遗传算法的核心思想

遗传算法，英文是 Genetic Algorithm，简称 GA。

它模仿的是达尔文进化论中的两个核心机制：

自然选择：适者生存，优秀个体更容易留下后代。
生物遗传：后代继承父母基因，同时可能发生变异。

对应到算法里，就是：

随机产生一批解 \to 评价优劣 \to 选择优秀解 \to 交叉和变异 \to 得到新一代解

这个过程不断重复，直到找到最优解或足够好的近似最优解。

4. 生物概念和算法概念的对应关系

遗传算法里很多词来自生物学。可以用下表理解：

生物遗传概念	遗传算法中的含义	零基础解释
个体 Individual	一个候选解	一个可行方案
染色体 Chromosome	解的编码	用字符串、二进制串、实数向量等表示方案
基因 Gene	编码中的一个分量	方案中的一个小决定
种群 Population	一组候选解	同时保留很多方案一起比较
适应度 Fitness	方案好坏的评分	分数越高，越值得保留
选择 Selection	选出优秀个体	好方案更可能进入下一代
交叉 Crossover	两个个体交换部分基因	把两个方案的优点组合起来
变异 Mutation	随机改变部分基因	偶尔尝试新方案，避免卡住

一句话总结：

遗传算法不是一次性算出答案，而是让一批方案像生物种群一样“一代代进化”。

5. 遗传算法的一般流程

遗传算法通常包含以下步骤：

编码：把现实问题的解表示成染色体。
初始化种群：随机生成若干个染色体。
计算适应度：评价每个染色体的好坏。
判断是否停止：如果达到最大迭代次数，或结果已经足够好，就停止。
选择：根据适应度选择父代个体。
交叉：父代染色体交换部分基因，产生子代。
变异：以较小概率随机改变某些基因。
形成新种群，回到第 3 步继续迭代。

可以写成伪代码：

text

初始化种群 P
计算 P 中每个个体的适应度

while 没有满足停止条件:
    根据适应度选择父代
    对父代执行交叉，产生子代 
    对子代执行变异
    计算新种群适应度
    更新种群

输出当前最优个体

6. 五个基本要素

课件中总结了遗传算法的五个基本要素：

要素	要解决的问题	例子
参数编码	怎样把问题答案变成染色体	背包问题用 0/1 表示是否选择物品
初始群体设定	一开始生成多少个方案，怎么生成	随机生成 20 个方案
适应度函数设计	怎样评价方案好坏	总价值越大，适应度越高
遗传操作设计	怎样选择、交叉、变异	轮盘赌选择、一点交叉、位点变异
控制参数设定	种群规模、迭代次数、交叉概率、变异概率	种群规模 50，最大迭代 200

下面逐个学习。

7. 第一步：编码

编码就是把现实问题中的“方案”翻译成遗传算法能处理的“染色体”。

编码很重要，因为编码方式会影响：

影响点	说明
能不能表示所有可行解	编码必须覆盖问题的解空间
搜索效率	好编码能更快找到优秀解
交叉和变异是否方便	编码要便于执行遗传操作
解的精度	对连续变量来说，编码长度会影响精度

7.1 二进制编码

二进制编码用 0 和 1 表示染色体。

例如背包问题中有 6 个物品：

text

染色体：1 0 0 1 1 0

含义是：

物品编号	1	2	3	4	5	6
基因值	1	0	0	1	1	0
是否放入背包	是	否	否	是	是	否

优点：

优点	说明
简单直观	只有 0 和 1
易于交叉变异	改一个位点即可
接近生物染色体思想	方便解释遗传过程

缺点：

缺点	说明
相邻数可能差别很大	例如 15 和 16 的二进制差异较大
需要提前确定精度	位数越多，精度越高，但搜索空间也越大
高维问题效率低	参数多时染色体很长

7.2 Gray 编码

Gray 编码，也叫格雷码，是由二进制编码转换而来的一种编码方式。

它的特点是：相邻两个数的编码通常只相差一位。

这可以减少二进制编码中“相邻数变化很大”的问题，使搜索更平滑。

7.3 实数编码

实数编码直接用实数表示染色体。

例如：

text

染色体：[0.2, 1.3, 4.5, 1.0, 2.1, 3.2]

适合连续优化问题，例如：

min f (x_{1}, x_{2}) = x_{1}^{2} + x_{2}^{2}

其中 $x_{1}$ 、 $x_{2}$ 是连续变量，直接用实数编码会更自然。

8. 第二步：初始种群

种群就是一组候选解。

例如背包问题中，初始种群可以是 4 条染色体：

个体	染色体
A1	100110
A2	011001
A3	010100
A4	111000

初始种群可以：

完全随机生成。
根据已有知识，在可能出现好解的范围内生成。
随机生成较多方案，再挑选较好的方案加入初始种群。

种群规模太小，容易早熟，陷入局部最优；种群规模太大，计算量会变大。

9. 第三步：适应度函数

适应度函数是遗传算法的“评分标准”。

一般希望：

适应度越大，个体越优秀

如果原问题是最大化问题，可以直接令：

F (x) = f (x)

其中 $F (x)$ 是适应度函数， $f (x)$ 是原目标函数。

如果原问题是最小化问题，需要转换成“越大越好”的形式。常见做法是：

F (x) = \frac{1}{f (x) + ϵ}

其中 $ϵ$ 是一个很小的正数，用来避免分母为 0。

也可以使用：

F (x) = C_{max} - f (x)

但要保证：

F (x) \geq 0

10. 第四步：选择

选择就是决定哪些个体可以作为父代，参与交叉产生下一代。

核心原则：

适应度越高，被选择的概率越大

10.1 适应度比例选择

假设种群有 $N$ 个个体，第 $i$ 个个体的适应度是 $F_{i}$ ，则它被选择的概率可以定义为：

p_{i} = \frac{F_{i}}{\sum_{j = 1}^{N} F_{j}}

这表示：一个个体的分数占总分的比例，就是它被选择的概率。

10.2 转盘赌选择

转盘赌选择可以这样理解：

把所有个体画到一个转盘上。
适应度越高，占的扇区越大。
随机转动指针。
指针停在哪个区域，就选择哪个个体。

示例：

个体	适应度 $F_{i}$	选择概率 $p_{i}$
A1	40	0.40
A2	30	0.30
A3	20	0.20
A4	10	0.10
合计	100	1.00

如果随机数是 0.81，可以按累计概率判断：

个体	概率区间
A1	$[0, 0.40)$
A2	$[0.40, 0.70)$
A3	$[0.70, 0.90)$
A4	$[0.90, 1.00]$

因为：

0.81 \in [0.70, 0.90)

所以选择 A3。

10.3 锦标赛选择

锦标赛选择的思路是：

从种群中随机抽出若干个个体。
比较它们的适应度。
选出其中最好的个体。
重复这个过程，直到选够父代。

它实现简单，也很常用。

10.4 最佳个体保存

最佳个体保存，也叫精英保留。

做法是：把当前种群中最好的个体直接复制到下一代，避免优秀解在交叉和变异中被破坏。

11. 第五步：交叉

交叉就是让两个父代染色体交换一部分基因，产生新的子代。

11.1 一点交叉

假设有两个父代：

text

父代 1：100110
父代 2：010100

如果交叉点在第 3 位之后：

text

父代 1：100 | 110
父代 2：010 | 100

交换交叉点后的部分，得到：

text

子代 1：100100
子代 2：010110

11.2 二点交叉

二点交叉随机选择两个交叉点，然后交换两个交叉点之间的片段。

例如：

text

父代 1：10 | 011 | 0
父代 2：01 | 010 | 0

交换中间片段：

text

子代 1：10 | 010 | 0 = 100100
子代 2：01 | 011 | 0 = 010110

12. 第六步：变异

变异是在染色体上随机改变某些基因。

例如位点变异：

text

变异前：100100
变异后：100101

最后一位从 0 变成 1。

变异的作用是保持种群多样性，避免算法陷入局部最优。

课件中提到的常见变异方式包括：

变异方式	说明	适用例子
位点变异	随机改变一个或多个基因值	二进制编码
逆转变异	选择两点，把中间片段反向排列	路径规划、TSP
插入变异	取出一个基因，插入到另一个位置	排列编码
互换变异	随机交换两个基因	排列编码
移动变异	把某个基因向左或向右移动	排列编码

13. 第七步：迭代和终止

一次选择、交叉、变异只能产生一代新种群。遗传算法需要不断迭代：

text

第一代：A1, A2, A3, A4
第二代：B1, B2, B3, B4
第三代：C1, C2, C3, C4
...

通常新种群规模和初始种群规模相同。

常见停止条件包括：

停止条件	说明
达到最大迭代代数	例如最多进化 300 代
找到满足要求的解	例如路径长度已经低于目标值
连续多代没有明显改进	说明可能已经收敛

14. 控制参数怎么设置？

课件给出了常见参数范围：

参数	常用范围	作用	太小的问题	太大的问题
种群规模	20 到 100	同时保留多少个候选解	多样性不足，易局部最优	计算量大，收敛慢
最大进化代数	100 到 500	最多迭代多少代	搜索不充分	浪费时间
交叉概率	0.4 到 0.99	多大概率执行交叉	更新不充分	可能破坏优秀结构
变异概率	0.0001 到 0.1	多大概率发生变异	多样性不足	随机性太强，破坏好解

初学时可以先用：

参数	推荐初始值
种群规模	30 或 50
最大进化代数	100
交叉概率	0.8
变异概率	0.01

然后根据结果再调整。

15. 例题一：背包问题

15.1 问题描述

有一个背包，最多能装 $30$ kg。现在有 6 个物品，每个物品有重量和生存点数。希望选择一些物品放入背包，使总重量不超过 $30$ kg，同时总生存点数尽量高。

可以把问题建模为：

max f (x) = \sum_{i = 1}^{6} p_{i} x_{i}

约束条件：

\sum_{i = 1}^{6} w_{i} x_{i} \leq 30

其中：

x_{i} \in {0, 1}

含义是：

符号	含义
$x_{i}$	第 $i$ 个物品是否放入背包
$x_{i} = 1$	放入
$x_{i} = 0$	不放入
$w_{i}$	第 $i$ 个物品的重量
$p_{i}$	第 $i$ 个物品的生存点数

15.2 编码

用 6 位二进制串表示一个方案：

text

表示选择第 1、4、5 个物品。

15.3 适应度函数

因为目标是总生存点数越大越好，所以可以定义：

F (x) = \sum_{i = 1}^{6} p_{i} x_{i}

如果某个方案超重，可以给它惩罚，例如：

F (x) = 0, 当 \sum_{i = 1}^{6} w_{i} x_{i} > 30

15.4 课件中的两个染色体比较

课件给出：

text

A1 = 100110
A2 = 011001

并给出计算结果：

染色体	总重量	是否可行	适应度
A1	$15 + 5 + 9 = 29$ kg	可行	$15 + 5 + 8 = 28$
A2	$2 + 5 + 9 = 16$ kg	可行	$2 + 5 + 9 + 16 = 23$

因为：

28 > 23

所以 A1 比 A2 更优秀，更可能被选择进入下一代。

15.5 交叉示例

课件中的父代：

text

A1 = 100110
A3 = 010100

交叉后：

text

B1 = 100100
B2 = 010110

解释：

text

A1 = 100 | 110
A3 = 010 | 100

B1 = 100 | 100
B2 = 010 | 110

15.6 变异示例

课件中的变异：

text

B1 = 100100
B3 = 100101

最后一位从 0 变成 1，表示第 6 个物品从“不放入”变成“放入”。

变异后还要重新检查：

总重量是否超过 30 kg。
适应度是否变高。

15.7 本题完整思路

步骤	做什么
编码	每个物品对应一个 0/1 基因
初始化	随机生成若干个 6 位二进制串
适应度	计算总生存点数，超重则惩罚
选择	优先选择适应度高的染色体
交叉	交换两个染色体的部分基因
变异	随机翻转某一位 0/1
迭代	重复进化，直到满足停止条件

16. 例题二：手算一次转盘赌选择

16.1 题目

某一代种群有 4 个个体，适应度如下：

个体	适应度
A1	28
A2	23
A3	16
A4	33

请计算每个个体的选择概率，并判断随机数 $r = 0.65$ 时选择哪个个体。

16.2 解析

总适应度为：

28 + 23 + 16 + 33 = 100

所以：

个体	适应度	选择概率	累计区间
A1	28	0.28	$[0, 0.28)$
A2	23	0.23	$[0.28, 0.51)$
A3	16	0.16	$[0.51, 0.67)$
A4	33	0.33	$[0.67, 1.00]$

因为：

0.65 \in [0.51, 0.67)

所以选择 A3。

注意：A4 的适应度最高，但不是每次都一定被选中；它只是被选中的概率最大。

这正体现了遗传算法的特点：

保留优秀个体的优势，同时保留一定随机性，避免过早失去多样性。

17. 例题三：旅行商问题与充电路线规划

课件中提到 2020 年“深圳杯”数学建模挑战赛 C 题：无线可充电传感器网络充电路线规划。

它可以抽象成类似旅行商问题，简称 TSP：

给出若干个节点，规划一条访问路线，使总路程尽量短。

17.1 和遗传算法的对应关系

生物学/遗传算法名称	TSP 中的含义
初始种群	随机生成的一批城市路径
染色体	一条访问城市的顺序
基因	路径中的一个城市编号
交叉	组合两条路径的部分城市顺序
变异	交换、逆转或移动路径中的城市
新染色体	新生成的一条路径
新种群	新生成的一批路径
适应度	路径总长度的倒数

17.2 编码示例

假设有 5 个城市：

text

1, 2, 3, 4, 5

一条染色体可以是：

text

1-3-5-2-4

表示访问顺序是：

1 \to 3 \to 5 \to 2 \to 4

17.3 适应度函数

因为路径越短越好，而遗传算法通常希望适应度越大越好，所以可以定义：

F = \frac{1}{L + ϵ}

其中：

符号	含义
$L$	路径总长度
$ϵ$	很小的正数，避免分母为 0

路径越短， $L$ 越小， $F$ 越大。

17.4 TSP 中为什么不能随便交叉？

背包问题的染色体是 0/1 串，交叉后通常仍然是合法串。

但 TSP 的染色体是城市排列，例如：

text

1-3-5-2-4

如果随便交叉，可能出现：

text

1-3-3-2-4

这里城市 3 出现了两次，城市 5 丢失了，这不是合法路径。

所以 TSP 常使用更专门的交叉方法，例如部分匹配交叉 PMX，或者交叉后进行修复。

18. 遗传算法容易遇到的问题

18.1 局部最优

局部最优是指：当前方案在附近看起来很好，但不是全局最好的方案。

可以理解为爬山：

text

你爬到了附近最高的小山丘，但远处还有更高的山峰。

遗传算法用变异来帮助跳出局部最优。

18.2 早熟收敛

早熟收敛是指：种群太早变得非常相似，失去多样性。

表现为：

现象	可能原因
很多代都没有改进	变异概率太低
个体越来越像	选择压力过强
很快卡在一般解	种群规模太小

18.3 参数不好调

遗传算法有随机性，同一组参数多次运行结果可能不同。

实际使用时常见做法是：

多运行几次。
比较平均结果和最好结果。
调整种群规模、交叉概率、变异概率和迭代次数。

19. 遗传算法和粒子群算法的简单区别

课件最后还介绍了粒子群优化算法。它的灵感来自鸟群觅食。

遗传算法和粒子群算法都属于智能优化算法，但思路不同：

对比项	遗传算法 GA	粒子群算法 PSO
灵感来源	生物进化	鸟群觅食
候选解名称	个体、染色体	粒子
主要操作	选择、交叉、变异	更新速度和位置
信息来源	适应度和遗传操作	个体最优 pbest、群体最优 gbest
适合直观理解的例子	背包选择、路线规划	连续函数寻优

粒子群算法的位置和速度更新公式为：

v_{i}^{n + 1} = w v_{i}^{n} + c_{1} r_{1} (p b e s t_{i}^{n} - x_{i}^{n}) + c_{2} r_{2} (g b e s t^{n} - x_{i}^{n})

x_{i}^{n + 1} = x_{i}^{n} + v_{i}^{n + 1}

这里只作为扩展了解。本教程重点仍是遗传算法。

20. 初学者学习路线

建议按下面顺序学习：

顺序	学习内容	达到的目标
1	什么是优化	知道 GA 要解决什么问题
2	生物概念和算法概念对应	理解基因、染色体、种群、适应度
3	编码	能把问题方案表示成染色体
4	适应度函数	能评价一个方案好坏
5	选择、交叉、变异	知道一代如何产生下一代
6	参数设置	知道种群规模、交叉概率、变异概率的影响
7	背包问题	能手算一个简单 GA 过程
8	TSP 路线规划	理解 GA 在实际建模中的用法

21. 课后练习

练习 1：判断编码含义

有 5 个物品，染色体为：

text

请问选择了哪些物品？

答案：

选择了第 1、3、4 个物品。

解析：

物品编号	1	2	3	4	5
基因值	1	0	1	1	0
是否选择	是	否	是	是	否

练习 2：计算适应度

背包容量为 10 kg，物品如下：

物品	重量	价值
1	2	6
2	4	8
3	5	10
4	3	5

染色体为：

text

请计算总重量和适应度。

答案：

选择第 1、3、4 个物品。

总重量：

2 + 5 + 3 = 10

总价值：

6 + 10 + 5 = 21

因为没有超过容量，所以适应度为：

F = 21

练习 3：判断交叉结果

父代为：

text

P1 = 110010
P2 = 001101

如果在第 3 位后执行一点交叉，得到的两个子代是什么？

答案：

text

P1 = 110 | 010
P2 = 001 | 101

C1 = 110101
C2 = 001010

练习 4：选择概率

某种群有 3 个个体：

个体	适应度
A	10
B	20
C	70

请计算它们的选择概率。

答案：

总适应度：

10 + 20 + 70 = 100

选择概率：

个体	选择概率
A	0.10
B	0.20
C	0.70

练习 5：最小化问题如何设计适应度？

某路径规划问题中，路径长度 $L$ 越短越好。请写出一种适应度函数。

答案：

可以定义：

F = \frac{1}{L + ϵ}

其中 $ϵ$ 是很小的正数。

解析：

路径越短， $L$ 越小，分母越小，适应度 $F$ 越大。

22. 一页速记

内容	记忆句
优化	从很多方案里找最好的
遗传算法	让一批方案一代代进化
编码	把方案变成染色体
适应度	给方案打分
选择	好方案更容易当父母
交叉	两个方案交换部分信息
变异	随机做小改变，保持多样性
迭代	重复选择、交叉、变异
终止	达到代数、满足要求或长期不改进

遗传算法的核心公式可以记住两个：

选择概率：

p_{i} = \frac{F_{i}}{\sum_{j = 1}^{N} F_{j}}

最小化问题转适应度：

F (x) = \frac{1}{f (x) + ϵ}

最后用一句话收尾：

遗传算法的本质，是用“评价 + 随机搜索 + 群体进化”的方式，在复杂问题中逐步逼近优秀解。

遗传算法零基础教程 ​

1. 先理解：什么是“优化”？ ​

2. 什么是智能优化算法？ ​

3. 遗传算法的核心思想 ​

4. 生物概念和算法概念的对应关系 ​

5. 遗传算法的一般流程 ​

6. 五个基本要素 ​

7. 第一步：编码 ​

7.1 二进制编码 ​

7.2 Gray 编码 ​

7.3 实数编码 ​

8. 第二步：初始种群 ​

9. 第三步：适应度函数 ​

10. 第四步：选择 ​

10.1 适应度比例选择 ​

10.2 转盘赌选择 ​

10.3 锦标赛选择 ​

10.4 最佳个体保存 ​

11. 第五步：交叉 ​

11.1 一点交叉 ​

11.2 二点交叉 ​

12. 第六步：变异 ​

13. 第七步：迭代和终止 ​

14. 控制参数怎么设置？ ​

15. 例题一：背包问题 ​

15.1 问题描述 ​

15.2 编码 ​

15.3 适应度函数 ​

15.4 课件中的两个染色体比较 ​

15.5 交叉示例 ​

15.6 变异示例 ​

15.7 本题完整思路 ​

16. 例题二：手算一次转盘赌选择 ​

16.1 题目 ​

16.2 解析 ​

17. 例题三：旅行商问题与充电路线规划 ​

17.1 和遗传算法的对应关系 ​

17.2 编码示例 ​

17.3 适应度函数 ​

17.4 TSP 中为什么不能随便交叉？ ​

18. 遗传算法容易遇到的问题 ​

18.1 局部最优 ​

18.2 早熟收敛 ​

18.3 参数不好调 ​

19. 遗传算法和粒子群算法的简单区别 ​

20. 初学者学习路线 ​

21. 课后练习 ​

练习 1：判断编码含义 ​

练习 2：计算适应度 ​

练习 3：判断交叉结果 ​

练习 4：选择概率 ​

练习 5：最小化问题如何设计适应度？ ​

22. 一页速记 ​

遗传算法零基础教程

1. 先理解：什么是“优化”？

2. 什么是智能优化算法？

3. 遗传算法的核心思想

4. 生物概念和算法概念的对应关系

5. 遗传算法的一般流程

6. 五个基本要素

7. 第一步：编码

7.1 二进制编码

7.2 Gray 编码

7.3 实数编码

8. 第二步：初始种群

9. 第三步：适应度函数

10. 第四步：选择

10.1 适应度比例选择

10.2 转盘赌选择

10.3 锦标赛选择

10.4 最佳个体保存

11. 第五步：交叉

11.1 一点交叉

11.2 二点交叉

12. 第六步：变异

13. 第七步：迭代和终止

14. 控制参数怎么设置？

15. 例题一：背包问题

15.1 问题描述

15.2 编码

15.3 适应度函数

15.4 课件中的两个染色体比较

15.5 交叉示例

15.6 变异示例

15.7 本题完整思路

16. 例题二：手算一次转盘赌选择

16.1 题目

16.2 解析

17. 例题三：旅行商问题与充电路线规划

17.1 和遗传算法的对应关系

17.2 编码示例

17.3 适应度函数

17.4 TSP 中为什么不能随便交叉？

18. 遗传算法容易遇到的问题

18.1 局部最优

18.2 早熟收敛

18.3 参数不好调

19. 遗传算法和粒子群算法的简单区别

20. 初学者学习路线

21. 课后练习

练习 1：判断编码含义

练习 2：计算适应度

练习 3：判断交叉结果

练习 4：选择概率

练习 5：最小化问题如何设计适应度？

22. 一页速记