08 遗传算法#

1. 本章定位#

遗传算法是智能优化算法。考试重点是基本流程、编码、适应度、选择/交叉/变异、模式定理、参数影响和应用。

2. 智能优化算法#

智能优化算法又称现代启发式算法，特点：

具有全局优化性能。
通用性强。
适合并行处理。
通常能在一定时间内找到最优解或近似最优解。

常见算法：

遗传算法 GA。
模拟退火 SA。
禁忌搜索 TS。

3. 遗传算法思想#

遗传算法由 J. Holland 于 1975 年提出，借鉴自然选择和自然遗传机制。

基本搜索过程：

保留一组候选解。
根据适应度选择较优个体。
通过选择、交叉、变异产生新一代。
重复迭代直到满足收敛条件。

4. SGA 基本组成#

基本遗传算法 SGA 包括：

编码与初始种群。
适应度函数。
遗传算子：选择、交叉、变异。
运行参数。

5. 编码#

SGA 常用二进制串编码。

函数优化示例：

f(x)=x\sin(10\pi x)+2.0,\quad x\in[-1,2]

若精度要求为 $10^{-6}$ ，区间长度为 3，需要：

2^{21}<3\times 10^6<2^{22}

因此至少需要 22 位二进制编码。

6. 适应度函数#

适应度函数评价个体好坏，是遗传算法进化过程的驱动力。

原则：

适应度越大，解质量越好。
适应度设计要结合具体问题。
对约束问题可加入惩罚函数。

7. 选择算子#

选择实现优胜劣汰。适应度高的个体进入下一代概率更大。

轮盘赌选择：

P_i=\frac{F_i}{\sum_{i=1}^{n}F_i}

步骤：

计算所有个体适应度。
计算每个个体选择概率。
用随机数模拟赌盘确定下一代个体。

8. 交叉算子#

交叉按交叉概率 $P_c$ 对两个配对染色体交换部分基因，产生新个体。

SGA 常用单点交叉。

作用：遗传算法产生新个体的主要方式，也是区别于许多其他进化算法的重要特征。

9. 变异算子#

变异按变异概率 $P_m$ 改变编码串中的某些基因。

二进制编码中：

0 -> 1
1 -> 0

text

作用：

增强局部搜索能力。
保持种群多样性。
防止过早收敛。

10. SGA 流程#

产生初始种群。
判断是否满足停止准则。
计算个体适应度。
比例选择。
单点交叉。
基本位变异。
产生新一代种群。
循环直到停止。

11. 遗传算法特点#

常见简答题答案：

群体搜索，易于并行化。
不是盲目穷举，而是启发式搜索。
适应度函数不要求连续、可微。
适用范围广。
具有全局搜索能力。

12. 模式定理#

模式：基因串中的相似样板，用 $\{0,1,*\}$ 表示，其中 $*$ 表示任意字符。

例：

10**1

text

模式阶：

O(10**1)=3

定义距：

\delta(10**1)=4

模式定理：

具有低阶、短定义距、平均适应度高于种群平均适应度的模式，在子代中呈指数增长。

13. 积木块假设#

积木块假设：

遗传算法通过短定义距、低阶、高平均适应度的模式，在遗传操作下相互结合，最终接近全局最优解。

模式定理解释“优良模式会增加”，积木块假设解释“优良模式能组合出更好的解”。

14. 收敛性影响因素#

因素	影响
种群规模 $M$	太小采样不足，太大计算慢
选择操作	高适应度个体保留，提高收敛性
交叉概率 $P_c$	太大破坏优秀个体，太小搜索停滞
变异概率 $P_m$	太小缺少新模式，太大变随机搜索

最优保存策略：保留父代最佳个体，不参加交叉和变异，直接进入下一代，有利于防止最优解丢失。

15. 遗传算法改进#

遗传欺骗问题：超常个体过早控制选择过程，使算法陷入局部最优。

改进方向：

编码方式：格雷编码、浮点数编码。
遗传算子：排序选择、均匀交叉、逆序变异。
控制参数：自适应 $P_c$ 、 $P_m$ 。
执行策略：混合遗传算法、小生境遗传算法、并行遗传算法等。

Schaffer 建议范围：

M=20\sim100

T=100\sim500

P_c=0.4\sim0.9

P_m=0.001\sim0.01

16. 应用#

常见应用领域：

组合优化。
函数优化。
自动控制。
生产调度。
图像处理。
机器学习。
数据挖掘。

PID 参数优化中，可把 $K_p,K_i,K_d$ 编码为染色体，适应度由控制性能指标构造。例如 ITAE：

J=\int t|e(t)|\,dt

通常希望 $J$ 越小越好，可把适应度设计为 $1/J$ 或相关变形。

17. 本章考点#

必背：

SGA 的组成和流程。
轮盘赌选择公式。
交叉和变异的作用。
遗传算法特点。
模式定理与积木块假设。
参数 $M,T,P_c,P_m$ 的影响。
遗传算法在 PID 优化中的应用思路。