遗传算法入门

果需要建模的问题太复杂，无法套用已知的线性、非线性或随机优化之类的数学式求解方法解决，那么这个时候可以考虑遗传算法（也叫进化算法，Genetic Algorithms，GAs）。

image

遗传算法是什么？

遗传算法是一种受生物进化论（特别是自然选择和遗传学）启发的搜索和优化算法。它模拟了“物竞天择，适者生存”的过程，用于解决复杂的优化问题，尤其是在传统数学方法难以奏效的情况下。

遗传算法是模仿遗传繁衍的繁衍过程来实现的，所以可以回顾一下生物物种进化的过程。

物种进化

梳理一个生物物种的进化过程：

一个种群中有许多个体。

每个个体都有其独特的基因（DNA），决定了它的性状（比如身高、速度、智力......）。

环境资源有限，个体之间需要竞争。更适应环境的个体有更大概率能生存下来并繁衍后代（自然选择）。

后代通过交叉（父母的基因混合）基础父辈基于 和 变异（基因发生微小随机变化）更新基因。

经过一代又一代的繁衍，整个种群的适应度会越来越高，因为优良的基因被保留和组合，最终进化出更能适应环境的个体。

遗传算法就是将这个过程数字化，以寻找问题的最优解。

目标： 找到一个问题的最优解；

做法： 用数字化模拟这个过程。

数字模拟化的过程：

28605448bbd42043d973dbee57c83729

遗传算法的工作流程其实是一个循环迭代的过程，可以概括为以下五步：

1 初始化： 随机生成一个由多个“个体”（潜在解）组成的初始种群。

2 评估： 用适应度函数计算种群中每个个体的适应度分数。

3 选择： 根据适应度高低，择优选择“父母”个体。高适应度个体有更高概率被选中繁衍后代。

4 交叉： 模拟基因重组，将选中的“父母”的染色体部分交换，产生新的“后代”个体。

5 变异： 以很低概率随机改变后代染色体中的部分基因，引入新特性。

∞ 循环： 新产生的后代形成新的种群，取代旧的种群。然后重复步骤 2-5，直到满足终止条件（如找到足够好的解或达到最大迭代次数）。

提示：这些只是理论上的流程，具体参数和流程需要在设计算法的时候考虑和调整以获得更好的结果。

案例——背包问题

一些术语了解：

个体与染色体：在算法中，一个可能的解决方案（比如一个设计参数、一个时间表）被看作一个“个体”。这个个体的完整“基因蓝图”就是它的染色体，通常用一串数字（二进制或十进制）表示。

种群：不是单个个体在进化，而是一群个体（一个种群）在一起进化，这模拟了自然界中的生物种群。

环境与适应度：待解决的问题本身（如“成本最低”、“效率最高”）就是算法的“环境”。衡量一个解决方案好坏的标准被量化为适应度函数。个体越适应环境（解决方案越好），其适应度得分就越高。

......

场景设定：

你是一个要去野营的孩子，你有一个容量有限的背包。你面前摆着5件物品，每件物品的价值和体积都不同。

你的目标是：在背包容量限制下，选择一些物品装进去，使得背包里所有物品的总价值最高。

物品列表如下：

物品 价值（元） 体积（升）

水壶 10 2

书 5 4

零食 15 3

外套 20 5

手电筒 12 2

第一步 — 初始化

核心是：将一个数学优化问题，转化为一个用“数字基因”表示的“虚拟生物”的生存与繁衍问题。（这一步也叫编码过程）

我们如何用一个“基因”来表示一种装包方案？

我们用一串二进制代码（0和1）来表示，长度等于物品的数量。

1 代表“拿”这个物品

0 代表“不拿”这个物品

例如：

染色体 10101 表示：拿水壶(1)、不拿书(0)、拿零食(1)、不拿外套(0)、拿手电筒(1)。

染色体 01010 表示：不拿水壶、拿书、不拿零食、拿外套、不拿手电筒。

我们随机生成几种不同的装包方案，作为初始的“想法”或“种群”。

假设我们初始的4个“个体”（装包方案）是：

个体A: 1 0 1 0 1 (拿水壶、零食、手电筒)

个体B: 0 1 1 0 0 (拿书、零食)

个体C: 1 1 0 1 0 (拿水壶、书、外套)

个体D: 0 0 0 1 1 (拿外套、手电筒)

第二步 — 适应度评估

目的：设计一个适应度函数 来评估每个个体对环境的适应程度，即解的好坏。适应度越高，个体越优秀。

我们的“适应度函数”就是计算这个方案的总价值。2个关键：

如果总体积超过8升，这个方案就是无效的，我们给它很低的分数（比如0分）。

谁的总价值高，谁就保留谁下来。

我们来计算一下：

个体A 10101：物品 = 水壶(2L) + 零食(3L) + 手电筒(2L)。总体积 = 7L (<8L)，总价值 = 10+15+12 = 37元。适应度 = 37。

个体B 01100：物品 = 书(4L) + 零食(3L)。总体积 = 7L，总价值 = 5+15 = 20元。适应度 = 20。

个体C 11010：物品 = 水壶(2L) + 书(4L) + 外套(5L)。总体积 = 11L (>8L)！超重了！ 适应度 = 0。

个体D 00011：物品 = 外套(5L) + 手电筒(2L)。总体积 = 7L，总价值 = 20+12 = 32元。适应度 = 32。

第三步 — 遗传操作（进化核心：选择、交叉、变异）

a. 选择

根据适应度高低来选择父母。个体A和D分数高，更可能被选中。个体C因为无效，最容易被淘汰。

假设我们选中了 个体A (10101) 和 个体D (00011) 作为父母。

b. 交叉

我们让他们在中间某个位置（比如第2位之后）交换基因。

父母A: 10 | 101

父母D: 00 | 011

交换后，得到两个孩子：

孩子1: 10 | 011 -> 10011 (拿水壶、不拿书、不拿零食、拿外套、拿手电筒)

孩子2: 00 | 101 -> 00101 (不拿水壶、不拿书、拿零食、不拿外套、拿手电筒)

c. 变异

以很小的概率，随机改变孩子某个位子的选择。

假设孩子1 10011 的第三位（零食）发生了变异，从0变成了1。

孩子1就变成了 10111。

∞ 循环

形成新种群与终止检查：

我们用新生的孩子（10111, 00101等）替换掉老一代中较差的个体（如个体B和C），形成新一代种群。

检查终止条件：

我们计算新种群中每个个体的适应度。比如 10111（拿水壶、零食、外套、手电筒）总体积=12L，超重！适应度为0。而 00101（拿零食、手电筒）总体积=5L，价值=27元。

我们发现还没有一个方案的价值能超过第一代个体A的37元，或者我们设定的迭代次数还没到。

于是，我们回到第2-3步，继续评估、选择、交叉、变异...

在不断的迭代中，算法可能会组合出像 10101（价值37）或 10001（拿水壶和手电筒，价值22，但体积小，为后续组合留空间）这样的优秀基因，并最终可能找到一个比37元更优的解（如果存在的话）。

总结

通过背包问题，可以看到遗传算法如何聪明地探索所有可能的组合：

它不会盲目地尝试所有

2

5

=32种可能。而是通过保留高价方案（选择）、组合不同方案的优点（交叉）、以及偶尔尝试新选择（变异），像搭积木一样，一步步地“进化”出接近最优的装包方案。

遗传算法已经成功应用于车辆路线、破产预测、Web搜索...等高度复杂的现实问题。

局限性

并非所有问题都可以用遗传算法来构建，它也是有一定的限制性的：

在一些情况下，来自少数相对高度适应(但不是最优)的个体的“基因”可能会主导种群，导致其收敛于局部最大值。当种群已经收敛时，遗传算法就不再具备继续寻找更好解的能力了。

大多数遗传算法都依赖于每次模型运行时产生不同结果的随机数生成器，虽然两次运行之间可能具有高度的一致性，但是它们也可能会有所不同。（即使参数相同，随机选择、交叉和变异可能引导算法走向不同路径。）

找到适用于特定问题的好变量是很困难的。获取数据以填充变量同样要求很高。

选择系统进化的方法需要思考和评估。如果可能解的范围很小，那么遗传算法就会很快收敛到一个解上。当进化进行得太快，以致太快改变好的解这可能会错过最优解。