遗传算法（Genetic Algorithm, GA）

September 24, 2016

遗传算法是一个模拟自然选择过程的人工智能算法，它通过启发式的随机搜索来寻求最优解，可见遗传算法是一个交叉学科的完美融合。

我在前几天的数学建模国赛上就使用了遗传算法，联想到之前接触的神经网络、蚁群算法等，不由得感慨生物界对计算机科学发展的启示。

如果你不曾接触过遗传算法，当你读完本文后一定会感慨自然界的神奇与奥妙。

遗传算法的生物学基础

刚才讲遗传算法是模拟一个自然选择的过程，试想在自然界的发展中，任何物种都是遵循“物竞天择，适者生存”的过程。种群中具备优秀基因的个体得以生存，同时繁殖出更加优秀的下一代的，而劣势个体只能被淘汰。

当某个种群在不断进化时，它的竞争对手（比如狐狸和兔子）也会在进化，这种机制（协同进化）推进了整个自然界的发展。

这就是以自然选择学说为核心的现代生物进化论的基本内容：

1. 种群是生物进化的基本单位
2. 突变和基因重组产生进化的原材料
3. 自然选择决定生物进化的方向
4. 隔离导致新物种的形成
5. 共同进化和生物多样性的形成

遗传算法的步骤

简单遗传算法（simple genetic algorithm, SGA）是遗传算法发展的初级阶段，具有里程碑意义。改良和融合新型技术的遗传算法都是基于 SGA。

用二进制模拟染色体序列，以便进行遗传、变异等处理。

00000000=0→L00000000=1→L+δ00000000=2→L+2δ00000000=3→L+3δ……11111111=2k−1→U\begin{align*} &

00000000=0\rightarrow L\\ &

00000000=1\rightarrow L+\delta \\ &

00000000=2\rightarrow L+2\delta \\ &

00000000=3\rightarrow L+3\delta \\ &

\ldots\ldots \\ &

11111111=2^{k}-1 \rightarrow U\end{align*}​00000000=0→L00000000=1→L+δ00000000=2→L+2δ00000000=3→L+3δ……11111111=2k−1→U​

δ=U−L2k−1\delta=\frac{U-L}{2^{k}-1}δ=2k−1U−L​

对任意二进制串，使用解码公式可以将其转换为十进制，这里不再推导。

比如说 x∈[2,4]x\in \left[ 2,4\right]x∈[2,4] ，用 5 位二进制数编码可得 32 条染色体。若 X22=10101X_{22}=10101X22​=10101 ，对应的十进制为 21。

首先生成一个随机数作为交配点位置，然后在两个个体交配点位置交换部分基因序列，形成两个子个体。

如图是交换后四位的结果，形成两个子代染色体。

为了避免算法迭代后种群过早收敛，遗传算法对基因序列小几率翻转（0 变为 1，1 变为 0），模拟基因突变。

“倒位运算”是指染色体某正常片段发生 180° 颠倒

101000001‾⇒101000100‾101000\underline {001} \Rightarrow 101000\underline{100}101000001​⇒101000100​

个体适应度评估

遗传算法依照与个体适应度成正比的几率决定当前种群中各个个体遗传到下一代群体中的机会。个体适应度大的个体更容易被遗传到下一代。

通常，求目标函数最大值的问题可以直接把目标函数作为检测个体适应度大小的函数。

根据个体适应度大小决定其下代遗传的可能性。若个体适应度高，被选取的几率就大，可能被多次选中，它的基因就会在种群中扩散；反之就会被逐渐淘汰。

---

网上很多人写过使用遗传算法解最优化问题，可以学习几个实例感受下。