随机优化方法：遗传算法与粒子群优化算法解析

### 随机优化方法：遗传算法与粒子群优化算法解析 #### 1. 遗传算法概述 遗传算法（Genetic Algorithm，GA）是一种基于生物进化原理的随机优化算法。它从搜索空间 $\mathcal{D}$ 中随机选择 $N$ 个个体作为初始种群，且种群大小 $N$ 通常在各代保持不变。在每一代（或迭代）中，遗传算法会执行以下主要步骤： 1. **评估（Evaluation）**：评估当前种群中每个个体 $x$ 的适应度，这需要计算每个个体的代价函数 $J(x)$。 2. **选择（Selection）**：根据个体的适应度，从当前种群中随机选择多个个体。 3. **繁殖（Reproduction）**：使用“遗传算子”（主要是交叉和变异）对选定的个体进行修改，形成新的种群，用于下一次迭代。 这个过程会重复进行，直到满足某个停止规则，通常是达到最大迭代次数或没有进一步的改进。 #### 2. 遗传算法的主要步骤详细解析 ##### 2.1 评估与适应度函数 每个当前种群的个体通过所谓的适应度函数 $F(x)$ 进行评估。根据定义，更好的解决方案具有更高的适应度。 - **最大化问题**：适应度函数与准则 $J(x)$ 相同，即 $F(x) = J(x)$。 - **最小化问题**：最佳个体是使代价函数尽可能小的个体，此时适应度函数是准则 $J(x)$ 的倒数，即 $F(x) = \frac{1}{J(x)}$。 ##### 2.2 选择及其算子 在每次迭代中，从当前种群中选择 $N$ 个个体来生成父代种群。个体的选择是基于适应度的过程，更好的解决方案更有可能被选中。通常，选择方法会设计为也选择一小部分适应度较低的解决方案，以保持种群的多样性，防止过早收敛到较差的解决方案。最广泛使用的选择算子是轮盘赌选择和锦标赛选择。 - **轮盘赌选择（Roulette Wheel Selection）**： - 个体从当前种群中有放回地随机抽取，抽取概率随其适应度增加。 - 确定一个实值区间 $[0, S]$，其中 $S$ 是当前种群中个体适应度的总和： \[S = \sum_{i=1}^{N} F(x^i)\] - 个体被映射到 $[0, S]$ 范围内的连续段，每个个体段的大小等于其适应度。 - 通过生成一个在区间 $[0, S]$ 上均匀分布的随机数进行选择，其段跨越该随机数的个体被选中。这个过程重复进行，直到获得所需数量的个体。这种方法类似于轮盘赌，每个切片的大小与适应度成比例。 - **锦标赛选择（Tournament Selection）**： - 从当前种群中随机选择 $N'$ 个个体，从这个组中选择最佳个体作为父代。 - 这个过程重复进行，直到获得所需数量的个体。锦标赛选择的参数是锦标赛大小 $N'$，该参数取值范围为 $2$ 到 $N$（即种群大小）。 ##### 2.3 繁殖及其算子 重复从同一种群中选择只会产生原始包含个体的副本，为了实现改进，必须对父代种群进行一些变异。繁殖步骤的目的是从当前种群中选择的父代产生新的种群。为此，可以使用两种算子：交叉算子（或重组算子）和变异算子。 - **交叉算子（Crossover Operator）**： - 成对的父代通过交叉操作组合形成两个新个体（子代），子代继承了父代的许多特征。 - 在实值遗传算法中，最简单的形式是所谓的算术交叉。对于每对父代，以给定的概率 $p_c$ 进行算术交叉。 - 如果发生交叉，两个子代通过父代的加权平均值生成： \[\begin{cases} x' = w_1x + (1 - w_1)y \\ y' = w_2x + (1 - w_2)y \end{cases}, w_1, w_2 \in [0, 1]\] 其中 $w_1$ 和 $w_2$ 是权重，$x$ 和 $y$ 是父代。权重 $w_1$ 和 $w_2$ 通常根据区间 $[0, 1]$ 上的均匀分布生成。交叉概率 $p_c$ 是用户定义的参数，通常选择在区间 $[0.5, 0.95]$ 内，这意味着对于选定的一对父代，有 $50\%$ 到 $95\%$ 的交叉机会。如果不进行交叉操作，两个子代与它们的父代相同。 - **变异算子（Mutation Operator）**： - 变异的主要目标是提供无法通过其他方式生成的新个体。这一步至关重要，因为它允许探索可能找到良好解决方案的新区域。 - 与选择和交叉算子专注于搜索空间的有希望区域不同，变异算子允许探索新区域。这两个方面（探索和利用）对于增加找到全局最优解的概率至关重要。 - 种群中通过交叉获得的每个个体以给定的概率 $p_m$ 进行变异。在实值向量的情况下，最常用的变异算子是通过向向量解 $x$ 添加随机向量 $V = (v_1, \cdots, v_{n_x})^T$ 来改变解： \[x' = x + V\] 随机向量 $V$ 通常根据零均值高斯分布 $\mathcal{N}(0, \alpha)$ 生成，其中 $\alpha$ 是用户定义的参数，用于确定解 $x$ 每个分量允许的最大变化。变异概率 $p_m$ 也是用户定义的参数，通常选择远低于交叉概率，以优先进行利用阶段。实际中常见的值范围为 $0.001$ 到 $0.07$。 #### 3. 标准遗传算法 虽然遗传算法的实现有很多变体，但下面介绍一种相当标准的形式。 **算法 2.6 遗传算法** 1. **初始化（Initialization）**：随机生成 $N$ 个个体的初始种群：$x^1, \cdots, x^N$（$N$ 为偶数），并评估适应度函数 $F(x^i)$，$i = 1, \cdots, N$。 2. **父代选择（Parent selection）**：从当前种群中有放回地选择 $N$ 个父代，并将它们随机分组。父代根据其适应度进行选择，适应度值较高的个体更常被选中。 3. **繁殖：交叉（Reproduction: crossover）**：对于步骤 2 中得到的每对父代，生成一个在区间 $[0, 1]$ 上均匀分布的随机数 $r$。如果 $r \leq p_c$，则根据上述算术交叉