智能优化算法（1）——遗传算法

1.1 遗传算法

遗传算法（Genetic algorithm, GA），模拟生物在自然环境中遗传和进化的自适应（对遗传参数的自适应调整）全局优化（随机变异不断寻找全局最优解）算法，基本思想是“优胜劣汰”，是应用最广泛和效果最显著的智能优化算法。

1.1.1 编码方法

算法模型通过对个体（individual，也即solution）进行二进制编码（01编码）、自然数编码、实数编码和树型编码。在对个体进行适应度计算时需要进行解码，实现问题的解空间与算法搜索空间的相互转换。

1.1.2 适应度函数

每个个体都有一个适应度函数（Fitness），对这个个体的优劣进行定量评价，适应度函数是算法执行“适者生存、优胜劣汰”的依据。适应度函数需要根据目标函数进行设置，令 $g(x)$表示目标函数，令 $G(x)$表示适应度函数，从目标函数 $g(x)$映射到适应度函数 $G(x)$的过程称为标定。

对于最大值优化问题，可直接将 $g(x)$设定为适应度函数 $G(x)$，即 $G(x)=g(x)$；对于最小值优化问题， $G(x)=-\min g(x)$；在遗传算法规定中，适应度函数为正值，但上述二式无法保证，因此需要加上最小值或者最大值以及分段函数。

1.1.3 选择操作

选择（Selection）是从当前群体中选择适应度函数值大的个体，这些优良个体有可能作为父代繁殖下一代，个体适应度函数越大，被选择作为父代的概率越大（有可能！）

选择算法有很多，最基本的是轮盘赌算法：

$$P_i = \frac{F_i}{\sum_{i=1}^{N}F_i}$$

其中， $P_i$表示个体被选择的概率； $F_i$表示个体的适应度函数值； $N$表示种群规模。

根据选择概率 $P_i$将圆盘形赌轮分为 $N$份，第 $i$个扇形的中心角为 $2\pi P_i$。随机产生0到1之间服从均匀分布的数 $r$，落在第 $i$个扇形的累计概率为 $Q_i = \sum_{j=1}^i P_j$，则选择个体 $i$，重复 $N$次，就可以选择 $N$个个体。

1.1.4 交叉操作

两个个体通过交叉（Crossover）互换染色体部分基因而重组产生新的个体，也就是产生新解。交叉前需要进行随机配对。

一般情况下，对二进制编码的个体采用点交叉的方法，也就是在两个配对字符串随机选择一个或者多个交叉点，互换部分子串从而产生新的字符串

两个个体是否进行交叉操作由交叉概率决定，较大的交叉概率可以使遗传算法产生更多新解，保持群体多样性，并能防止算法过早成熟，但是交叉概率过大会使算法过多搜索不必要的解区域，消耗过多的计算时间，一般取值在0.9左右。

1.1.5 变异操作

生物进化中，某些染色体可能会发生基因突变（Mutation），从而产生新的染色体，这也是产生新解的另外一种重要方式。交叉操作相当于进行全局探索，变异操作相当于进行局部开发，这也是智能优化算法必备的两种搜索能力。

个体能否变异取决于变异概率，过低会使得部分有用基因无法进入染色体，不能提高解的质量；过大会使子代丧失父代优良基因，导致算法失去从过去搜索经验的学习能力，一般情况下，变异概率取值为0.005左右。

值得注意的是，Rudolph通过马尔科夫链相关理论证明仅采用选择、交叉和变异三个操作的遗传算法不能收敛到全局最优解，而采用精英保留策略的遗传算法是全局收敛的。

算法的整体流程如下图所示：

1.1.6 算法分析

一个好的智能算法，关键在于全局探索和局部开发能力的平衡。全局探索的目的是对解空间进行更全面的探索，局部开发主要目的是对已知区域进行更精细的搜索，希望获得质量更好的新解。

遗传算法可以通过设置选择压力实现全局探索和局部开发的平衡。在算法运行初始阶段，设置较小的选择压力可以使算法具有较好的全局探索能力，进行广域搜索；算法运行后期，设置较大的选择压力可以使算法进行比较精细的局部搜索。

选择压力的设置可以从适应度函数标定和选择策略。

适应度函数标定，在算法早期，应当缩小个体适应度差距，减少淘汰率；算法运行最后阶段，扩大个体适应度差距，保证算法能在高适应度个体对应解区域进行集中搜索，加快算法收敛速度。常用方法有：

• 线性尺度变换 $H = aF+b$
• $\sigma$截断法 $H = F+(\hat F - c\sigma)$
• 幂律尺度变换 $H = F^\alpha$

选择策略，低选择压力可选择多种类型的个体，加强对未知解区域的搜索，避免算法陷入局部极值，但算法优化速度会变得缓慢；高选择压力可选择优良个体，加快优化速度但群体多样性会下降，减少搜索到全局最优值的概率。除了轮盘赌算法外，选择策略还有：

• 分级选择法
• 锦标赛选择法
• Boltzmann选择法