# 遗传算法（GA）

遗传算法（Genetic Algorithm, GA）如今已经发展出了许多分支。

# 一. 简介

遗传算法大致可以分为：单目标 GA、多目标 GA、改进型 GA、特殊结构 GA。

# 1. 单目标 GA（基础版）

最常见的形式，用来优化单个目标函数。

代表算法：

算法名称	简介
Basic GA（经典遗传算法）	选择 + 交叉 + 变异进行进化
Real-coded GA（实数编码 GA）	个体不是二进制，而是连续变量（更适合工程优化）
微分进化 DE（Differential Evolution, DE）	GA 的变体，性能很强，核心操作常被称为“差分变异”

# 2. 多目标遗传算法（MOEA）

多目标问题不是一个目标，而是多个目标同时优化：

$$\min (f_1(x), f_2(x), \dots, f_k(x))$$

例如：

• 减少温度
• 增加效率
• 降低成本

这些目标往往相互冲突，所以通常不存在唯一“最优解”，而是得到一条帕累托前沿（Pareto Front）。

代表算法：

算法	特点	常用程度
NSGA-II	非支配排序 + 拥挤距离	非常常用
NSGA-III	适用于高维多目标（目标数较多）	常用
SPEA2	强度指标 + 密度估计	较少
MOEA/D	将多目标分解为多个单目标子问题	常用

# 3. 改进型 GA（智能/高级 GA）

一些常见的改进策略：

算法	思想	作用
精英策略 GA（Elitism GA）	每代保留最优个体	防止退化
自适应遗传算法 AGA	自动调整变异率、交叉率	无需固定参数
免疫遗传算法 IGA	加入免疫算子（抗体、亲和度等）	维持多样性，避免早熟
混合 GA（Hybrid GA）	与梯度下降/粒子群/模拟退火等结合	提升收敛速度
星火遗传算法（Spark GA / Firefly-GA）	引入“吸引”机制（受萤火虫算法启发）	强化局部搜索

# 4. 特殊结构 GA（编码方式/结构变化）

为特定问题设计的编码与算子：

算法	应用
Permutation GA	旅行商问题（TSP）、排序优化
Binary GA	0-1 组合优化
Tree GA（遗传规划 GP）	用树结构进化“程序/表达式”

# 二. 传统 GA 流程

# 问题目标

假设要优化：

$$\min_{x} f(x)$$

遗传算法的目标是找到使 $f(x)$ 尽可能小的 $x$。

# 种群表示（Population）

一个解 $x$ 被称为“个体”（Individual）。$N$ 个解组成一代种群：

$$P^{(t)} = \{ x_1^{(t)}, x_2^{(t)}, \dots, x_N^{(t)} \}$$

$t$ 表示当前是第几代。

# 适应度函数（Fitness）

遗传算法常把目标函数 $f(x)$ 转成“适应度”。常见做法（越大越好）：

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

若本身是最大化问题，也可直接使用：

$$F(x) = f(x)$$

# 选择（Selection）

让适应度更高的个体更容易被选中。

# 轮盘赌选择（Roulette Wheel）

每个个体被选中的概率：

$$p_i = \frac{F(x_i)}{\sum_{j=1}^{N} F(x_j)}$$

即：越优秀的个体，概率越大。

# 交叉（Crossover）

随机选出两个父代：

$$x_a = (x_{a1}, x_{a2}, \dots, x_{ad})$$

$$x_b = (x_{b1}, x_{b2}, \dots, x_{bd})$$

单点交叉：选择一个位置 $k$，生成子代：

$$ext{Child}_1 = (x_{a1}, \dots, x_{ak}, x_{b(k+1)}, \dots, x_{bd})$$

$$ext{Child}_2 = (x_{b1}, \dots, x_{bk}, x_{a(k+1)}, \dots, x_{ad})$$

交叉概率 $P_c$ 通常取 $0.6 \sim 0.9$。

# 变异（Mutation）

对某些位置加小扰动以保持探索性。

实数编码常用：

$$x_{ij}^{(new)} = x_{ij}^{(old)} + \epsilon,\quad \epsilon \sim \mathcal{N}(0, \sigma^2)$$

二进制编码常用位翻转：

$$0 \rightarrow 1,\quad 1 \rightarrow 0$$

变异概率 $P_m$ 常取 $0.01 \sim 0.1$。

# 生成下一代（Reproduction）

用“选择 + 交叉 + 变异”生成的新个体组成下一代：

$$P^{(t+1)} = \{ x_1^{(t+1)}, x_2^{(t+1)}, \dots, x_N^{(t+1)} \}$$

# 停止条件

重复迭代直到：

$$t = t_{\max}$$

或适应度不再提升（收敛）。

# 整体流程

$$P^{(t+1)} = \text{Mutation}(\text{Crossover}(\text{Selection}(P^{(t)})))$$

一句话概括：

下一代 = 选择优秀父代 + 交叉组合 + 随机变异。

# 例子

优化：

$$f(x)=x^2$$

适应度：

$$F(x)=\frac{1}{1+x^2}$$

轮盘赌选择：被选概率与 $F(x)$ 成正比。
交叉产生新个体（示意）：

$$x_{new} = \alpha x_a + (1-\alpha) x_b$$

变异添加噪声：

$$x_{new} = x_{new} + \epsilon$$

迭代后 $x$ 会更接近 $0$（最优点）。