（图片来源：veer图库）

没错，而且是处理传统数学理论不易办理的问题。

首先，来看个数学问题：

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

对这种大略的目标函数，可直接套用公式：当自变量x=-b/2a时，目标函数的最值为（4ac-b2）/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]. 北京: 中国科学技能出版社.

作者：望墨溢

作者单位：西北工业大学 航海学院

（本文于2021年7月26日首发于科学大院）