自然界是人类创新灵感的不竭源泉。自然界生物具有非凡的适应能力和智慧：蚁群如何找到距离食物源的最短路径，大雁觅食时怎么飞距离最短，生物怎么进化出各种性状……合理利用这些规律，可以处理……数学问题？
没错，而且是处理传统数学理论不易解决的问题。
优化问题与启发式算法
首先，来看个数学问题：
计算如下一元二次函数的最值
对这种简单的目标函数，可直接套用公式：当自变量x=-b/2a时，目标函数的最值为（4ac-b^2）/4a（忘了请自行联系高中数学老师）。这种能直接表达为公式的解，称为解析解（Analytic Solution）。
对于简单问题，可一步得到答案
这种求某函数的最大值/最小值的问题，就是优化问题，这一函数称为目标函数（Objective Function）。优化算法，就是计算目标函数最值的算法。
实际中，优化问题的目标函数往往比较复杂，无法得到解析解，因此常利用梯度（多元函数的导数），进行迭代求解。
然而，对于某些更为复杂的目标函数，无法使用梯度方法。例如，计算如下函数的最小值
复杂的目标函数，无法套用公式
若利用常规的梯度方法，容易收敛于局部最优（Local Optimum），即某一范围内的最值点，而不是全局最优（Global Optimum），即全局范围内的最值点。
梯度方法容易陷入局部最优
优化类似的复杂函数，一直是难点问题。科学家在受到某些自然规律的启发后，模拟自然体算法，提出了若干启发式算法（Heuristic Algorithm），用于处理传统数学理论不易解决的优化问题。
例如，模拟蚁群寻找、搬运食物的规律，提出蚁群算法（Ant Colony Algorithm）；模拟大雁在空中觅食的规律，提出粒子群优化算法（Particle Swarm Optimization Algorithm）；模拟生物遗传与进化规律，提出遗传算法（Genetic Algorithm）……
算法科学家怎么看生物遗传与进化？
本文介绍的启发式算法，是模拟生物遗传与进化规律提出的，那么，算法科学家眼中的遗传与进化是怎样的？这里先以长颈鹿的进化为例（注意，遗传算法只是对已知进化规律的模仿，并不一定等同于生物规律）。
自然界的生物多种多样，其性状由基因和外部因素共同决定，但基因占主导作用，因此这里忽略外部因素。例如，基因确定，长颈鹿的脖子长短也随之确定。
基因是生物的遗传物质，由多位核苷酸组成，类似于“AaBbCc”。种群的进化，必然意味着基因的变化。
自然选择并不直接作用于基因，而是作用于性状。个体的性状不同，其生存能力不同。例如，鹿脖子越长，吃到的树叶越多，生存能力越强。将生存能力进行量化，称为适应度。
适应度本应由多个因素共同决定，例如鹿的脖子长短、体力、视力等因素。但这里仅考虑脖子长短，脖子越长，适应度越高。
（本文默认：基因决定性状，再决定生存能力）
从前，有群普通的鹿，大家的基因各不相同，因此性状也不同（这里的性状特指脖子长短），将这一代的鹿群记为“鹿群0”。
在“鹿群0”中，脖子长的个体能吃到更多的树叶，更可能生存下去，因此适应度高。而脖子短的个体更可能被淘汰，适应度低。将这一过程称为选择，经过选择生存下来的鹿才能够进行交配。
（图片来源：望墨溢，一位灵魂画家）
雄鹿在与雌鹿交配时，不是简单地复制自己的基因，而是与雌鹿的基因发生交叉后再结合（这里认为基因=染色体）。例如，“Aa BbCc”+“aa bbcc”=“Aa bbcc”+“aa BbCc”。
当然，在两条基因进行结合时，基因的一位或若干位核苷酸可能发生变异。例如，某位基因b变异成B。
基因交叉
基因变异
这样，“鹿群0”就产生了新的一代，记为“鹿群1”。一般而言，经过选择处理的“鹿群1”，适应度的最大值和平均值会提高，也就是脖子长短的最大值和平均值有所提高。
经过一代又一代的繁衍，由于基因的变化，“鹿群N”的脖子将会显著长于“鹿群0”，适应度更高。这时，我们可以说物种进化了。
种群趋向最优
当然，最优的脖子长短还与环境有关，这里环境特指树冠高度。脖子高于树冠，没有好处反而有坏处。而只要环境不发生显著变化，“鹿群N”之后，种群的基因不会发生显著变化，适应度也不会发生显著变化，种群稳定在最优解。
遗传算法，到底怎么算？
美国的John Holland，模拟达尔文生物进化论的自然选择和遗传学机理，提出一种启发式优化算法——遗传算法。
该算法将自变量转换成个体，通过编码将个体与基因对应起来，将待求解的目标函数作为适应度函数，保留了交叉、变异，经多次迭代后，可使种群（多个个体）趋于最优解。
以求解目标函数F(x)=x+8sin(5x)+5cos(4x)的最大值为例，遗传算法会分六步走来解决问题：
1. 初始化
遗传算法将自变量可能的取值视为个体，在设置好种群总数后，生成初始化种群。例如，设置种群个体共100个，在[0,8]区间内随机选择100个初始值。
在自变量的某个区间内，随机生成初始种群
2. 编码与解码
自变量个体本身无法视为基因，需将其进行某种转换，通常将个体转换为一串二进制的数，称为编码，这串二进制的数即可视为基因。
例如，规定用4位二进制表示整数部分，用2位二进制表示小数部分，则3.25可表示为“001101”，“001101”就是该个体的基因。
个体的3.25的二进制表示001101，就是对基因的模拟
编码是为了模拟基因，从而进行后续的交叉、变异。而解码，就是将基因（二进制）再转换为个体（十进制）。十进制数才能代入适应度函数中，从而计算适应度。
3. 适应度计算
但在将基因（二进制）转化为个体（十进制）后，将十进制个体代入目标函数，即可得到适应度。
不难理解，适应度函数常常就是待求解的目标函数F(x)=x+8sin(5x)+5cos(4x)。
4. 选择
每个个体，根据适应度大小，进行选择。适应度大的，更可能被保留下来，适应度小的，更可能被淘汰。这一过程，通常用“轮盘赌”模型进行。
当然，在选择的过程中，我们还得保证个体数量不变。为保证这一点，适应度大的，不仅被保留，还会被复制。
适应度大的个体自然更可能存活
5. 交叉与变异
保留下来个体，经编码得到基因后，进行交叉。例如，“001 101”+“010 010”=“001 010”+“010 101”。一般而言，交叉点是随机选择的。
这里，两个基因交叉得到两个新的基因（相当于父母必生双胞胎）。因此，交叉不改变种群数量。
在交叉后，每个基因还可能发生变异。一般而言，变异点也是随机的。例如，某位的1变为0，或0变为1。
二进制数的交叉
二进制数的变异
在经过选择后，相比前一代，种群适应度的最大值和平均值都会有所提高。具体而言，就是所有的个体都会向目标函数的高处集中。经多次迭代后，就会集中于最大值处。
6. 是否结束
既然是优化算法，必然需要设置结束条件，不能让算法无限次地循环下去（死循环）。最简单的方法，就是设置算法运行次数。例如，令算法循环50次后结束。
这里给出遗传算法一般的流程图
随着进化的进行，即算法的循环，种群的平均适应度势必逐代提高，最终收敛于某一最大值，这一点就是我们要找的目标函数的最大值点。
遗传算法循环50次后的种群分布：集中于一点
随着算法的迭代，种群的平均适应度也在提高
每一步都有小策略
要想提高遗传算法的效率，在上述步骤中其实都有小技巧。
1.初始化
若可获得关于最值点的先验信息，即最值点所在的大致范围。则可在这一范围内生成初始种群。若没有，则需要在更大范围内随机生成。
初始值的选择，会影响算法的收敛速度。初始值选得越靠近最优解，收敛速度越快。另外，不合适的初始值，可能使得算法陷入局部最优。
这样是不是能更快地找到最优解~
2. 编码与解码
在数字信号处理中，度量必然存在最小值和最大值，即变量的取值不是连续、无限的，而是不连续，有限的，由于度量产生的误差称为量化误差（Quantization Error）。
例如，我们用4位二进制表示整数部分，用2位二进制表示小数部分，那么自变量最大只能取15.75（对应二进制为111111），且小数部分只能分辨出0.25的差异。度量的最小值又被称为分辨率（Resolution Ratio）。
F(x)=x+8sin(5x)+5cos(4x)的最优解在7.860处，但算法只能收敛于7.875
当然，我们可令基因的长度很长，例如用100位二进制表示整数部分，10位二进制表示小数部分，即可扩大自变量取值范围，提升分辨率。然而，这样会增加算法的运算量和存储量。
3. 选择
在选择过程中，若一定保留、复制适应度最高的个体，则称为精英保留（Elite Reservation）；若不一定保留适应度最高的个体，其依旧有可能被淘汰，则称无精英保留。
实验证明，有精英保留的遗传算法，收敛至最优值的速度更快，且更为稳定。
4. 交叉与变异
交叉可分为单点交叉，也可多点交叉，变异也可分为单点变异和多点变异。交叉和变异是为了提高基因多样性，加速收敛速度，且可跳出局部最优。
例如，当所有个体都集中至局部最优附近时，突然有个个体变异了，“跳”至全局最优附件，则种群就可进一步进化。
对于种群而言，稳定比多样更为重要，因此交叉和变异往往单点进行即可，且变异概率往往非常低。
5. 是否结束
通过设置算法运行次数，来控制算法结束，虽然简便，但存在如下两个问题：
（1）若算法收敛较慢，例如50次并未使得种群集中到某一最优解，那么结果必然不正确；
（2）若算法收敛较快，例如20次即可使得种群集中到某一最优解，那么就浪费了很多的计算资源。
另一种更为可靠的方法，是判断相邻2次运算间，种群的平均适应度差异大小，即是否小于某个门限。如果是，则认为算法已经收敛，可终止；如果否，则认为算法还未收敛，应继续循环。
根据平均适应度差异来控制算法终止，更为可靠
遗传算法不仅能画画，还能告诉你这些
以遗传算法为例的启发式算法，没有极其严格的数学推导，但自然界已用这些规律解决了无数的问题。现在，遗传算法已广泛应用于我们生活中的多个领域，例如，如何设计车辆外形，以减少空气阻力；如何安排机器人的工作流程，以提高工作效率；如何进行线路规划，使快递运输路程最短……
之前，有人在GitHub上传了一个项目，就是用遗传算法来绘制特定的图片，下面是一个仿真实例，看遗传算法是如何对照上面的照片“画”出下面的作品的：
（图片来源：https://github.com/anopara/genetic-drawing）
首先，给出多个初始色条，组成色条画面，并以色条画面与原图片的差作为目标函数。然后利用遗传算法，迭代求解色条的排列，使得目标函数最小，即色条画面与原图片“最像”，从而实现用多个色条“画”出原图片。
PS：如果你不是码农，暂时也不需要用到遗传算法，但是仍可从遗传算法中学到若干智慧：
●没有完美的算法，保证精度，就得增加计算量。一切策略，都是在多个因素间寻找平衡的艺术。
●只追求稳定，会无法进步；只追求多样，会无法积累优势。因此，我们需要在稳定和多样间寻找平衡。但是，从长远来看，稳定（积累、传承）往往比多样更重要一些。
●精英保留很重要，但也绝不能轻视精英以外的普通个体。没有普通个体，变异就失去了土壤，种群也就走向了单调。而单调，往往意味着脆弱。
参考文献：
[1] 郑树泉. 工业智能技术与应用[M]. 上海: 上海科学技术出版社.
[2] 李德毅, 于剑. 中国科协新一代信息技术系列丛书 人工智能导论[M]. 北京: 中国科学技术出版社.
作者：望墨溢
作者单位：西北工业大学 航海学院
热门跟贴