自然界是人类革新想法的不竭源泉。自然界生物具备非凡的适应能力和智慧：蚁群怎么样找到距离食物源的最短路径，大雁觅食时如何飞距离最短，生物如何进化出各种性状……合理借助这类规律，可以处置……数学问题？

（图片来源：veer图库）

没错，而且是处置传统数学理论不容易解决的问题。

优化问题与启发式算法

第一，来看个数学问题：

计算如下一元二次函数的最值

对这种简单的目的函数，可直接套用公式：当自变量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)+5cosplay(4x)的最大值为例，遗传算法会分六步走来解决问题：

1. 初始化

遗传算法将自变量可能的取值视为个体，在设置好种群总数后，生成初始化种群。比如，设置种群个体共100个，在[0,8]区间内随机选择100个初始值。

在自变量的某个区间内，随机生成初始种群

2. 编码与解码

自变量个体本身没办法视为基因，需将它进行某种转换，一般将个体转换为一串二进制的数，称为编码，这串二进制的数即可视为基因。

比如，规定用4位二进制表示整数部分，用2位二进制表示小数部分，则3.25可表示为“001101”，“001101”就是该个体的基因。

个体的3.25的二进制表示001101，就是对基因的模拟

编码是为了模拟基因，从而进行后续的交叉、变异。而解码，就是将基因（二进制）再转换为个体（十进制）。十进制数才能代入适应度函数中，从而计算适应度。

3. 适应度计算

但在将基因（二进制）转化为个体（十进制）后，将十进制个体代入目的函数，即可得到适应度。

不难理解，适应度函数常常就是待求解的目的函数F(x)=x+8sin(5x)+5cosplay(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)+5cosplay(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] 李德毅, 于剑. 中国科协新一代信息技术系列丛书 AI导论[M]. 北京: 中国科技出版社.

本文源自“科学大院“公众号，转载请注明公众号出处

Tags：目标函数