广东科学中心「院士说」 | 人工智能算法之四：遗传算法

本篇内容源自广东科学中心，整体被划分为五个部分，而本文正是其中第四部分的具体阐述。

听到“遗传”这两个字

读者们也许会想到达尔文的进化论

达尔文

在1859年11月24日这一天，达尔文推出了其备受推崇的著作《物种起源》。

达尔文已年满五十，身为英国皇家学会的一员。他耗时二十余载完成这部著作。此刻开元棋官方正版下载，他正居家静候暴风雨的降临。《物种起源》首版仅1250册，却在一日之内销售一空。

后人评论《物种起源》至少有六个论点：

世界始终处于不断进化之中，而非停滞不前；它并非在短时间内被创造而成；世界本身并无既定目标；人类的存续亦无既定目的；事物的演化可以通过物质进化过程来阐述；事物的本质是持续变化的，而非一成不变。

这六个观点各自与《圣经》中的教义相悖。在那时，无论是政治理念还是经济财富，教会都处于绝对主导地位，其发表的言论所引发的争议和风波，不难想象。

1886年伦敦漫画《猴子达尔文》

达尔文的《物种起源》改变了世界

学者们沿着达尔文开创的道路深入研究

发现了一个重要问题

物种进化是通过什么来实现的？

格雷戈尔·孟德尔

格雷戈尔·孟德尔，全名格雷戈尔·约翰·孟德尔，生于1822年，逝世于1884年，他首次提出了“基因”这一科学概念。

孟德尔诞生于奥匈帝国的海因策道夫，如今该地属于捷克，名为亨奇采。他的父亲是一名农夫，因此孟德尔自幼便掌握了园艺技艺。家境的贫寒促使他加入教会，借此机会获得奖学金以继续学业。“格雷戈尔”这个名字是他受洗时教会所赐，寓意着警醒。在维也纳大学求学期间，他的物理学导师正是发现了多普勒效应的克里斯蒂安·多普勒。他渴望成为一名物理教师，然而，两次考试均未能如愿。因此开yunapp体育官网入口下载手机版，他不得不转而投身教会，成为一名牧师。在教会中，生活节奏平缓且井然有序，他得以延续在大学期间进行的农艺实验。

孟德尔（Gregor Mendel）

在1856至1863年这段时间里，孟德尔进行了超过28000次的豌豆杂交实验，并基于这些实验结果，提出了关于遗传因子（即基因）的全新概念，以及两个重要的遗传定律——基因分离定律与基因自由组合定律。到了1866年，他将这些研究成果公布于一个地方性的学术期刊，然而，这些成果并未受到应有的关注。随后在1868年，孟德尔晋升为当地教会的主事，自此，他的实验工作也随之终止。在1900年，孟德尔的论文被重新挖掘出来，随之，“基因”以及“遗传规律”的概念也迅速在全球范围内传播开来。然而，孟德尔本人早已离世多年。

是不是感叹大神们的伟大成就

别急别急

还有呢

詹姆斯·沃森

1953年，詹姆斯·沃森与弗朗西斯·克里克共同揭示了DNA的双螺旋结构。这一发现使得人类得以窥见基因的奥秘。

Deoxyribonucleic Acid简称为DNA，其对应的中文名称是脱氧核糖核酸。这种大分子由众多脱氧核苷酸构成。脱氧核苷酸是一种由碱基、脱氧核糖和磷酸三种成分组成的小型化合物。组成DNA的基本单元包括四种碱基，分别是腺嘌呤，其简称为A；胸腺嘧啶，简称为T；胞嘧啶，简称为C；以及鸟嘌呤，简称为G。

DNA的双螺旋结构

如上图所示，两条脱氧核苷酸链环绕同一中心轴线进行螺旋状排列，构成了我们所熟知的双螺旋结构。在这螺旋结构的外围，可以观察到脱氧核糖-磷酸链的分布，而碱基则朝向内部。这两条链以反向互补的方式排列，它们之间通过氢键实现碱基的配对，即A与T相配，C与G相配。这种配对方式确保了结构的稳定性。碱基的尺寸大约是0.2纳米，这相当于10的负6次方毫米。而碱基对之间的间隔，也就是DNA双螺旋之间的距离，大约在2.2到2.6纳米之间。

基因是怎样传递遗传信息的呢？

以细胞分裂为实例，我们可以阐述这一过程。大多数动物与植物的细胞尺寸大约在0.01至0.1毫米之间。在这些细胞的细胞核内，蕴藏着全部的遗传信息。对于人类而言，我们拥有大约19,000至20,000个基因，这些基因由大约30亿个碱基对组成，若将它们串联起来，其长度可达2米。这些基因经过折叠后，分布在23条染色体上。在2001年，科学家们成功完成了人类基因的测序工作，然而时至今日，他们尚未能够全面掌握每个基因的具体作用。

细胞的有丝分裂（Mitosis）

上图展示了细胞进行有丝分裂的整个过程。在图中，部分细胞呈现出二倍体的染色体形态。细胞分裂时，其双螺旋的DNA结构解开，脱氧核苷酸链上的碱基与周围环境中的互补碱基配对，进而形成两个完全相同的双螺旋结构，从而使得原本的一对染色体分裂成两对。随后，细胞依据基因的编码指令合成新的细胞成分。随着细胞的不断增长，最终分裂成两个个体，从而实现了细胞分裂的完整过程。这一遗传复制过程极为可靠，新生成的两个细胞与原始细胞完全相同。

借助基因科学家的研究，我们能够探寻生命的起源，洞察物种的演变过程，并创造出新的生物种类。

进化造就了世界，能不能用进化论的思想来解决工程问题呢？

这便是源自于我母校——密西根大学——的约翰·荷兰（John Henry Holland，1929-2015）教授所创立的遗传算法（Genetic Algorithm）。

可惜我在母校读书时没有去上过他的课。

约翰·荷兰

约翰·荷兰

遗传算法的核心原理相当直观：首先在群体中挑选出一对父母，让他们繁衍后代。这些后代会经历一系列的修改，并接受评估。评估结果不仅基于个体本身，还参考了整个群体的表现。群体中表现最差的个体将被淘汰。这个过程不断重复，直至群体达到最佳状态。

遗传算法框图

以遗传算法为例，探讨推销员行程规划的案例：推销员需访问N座城市，每座城市仅访问一次，并力求行程最短。这一难题最早由爱尔兰数学家威廉·密尔顿爵士（Sir William Rowan Hamilton，1805-1865）提出。表面上看，问题似乎简单，然而其计算复杂度高达N的阶乘。= N(N-1)(N-2) … (2)(1)。

当N取值为25时，其阶乘N!的结果达到了1.551121004乘以10的25次方，这个数值极其庞大，即便是功能强大的超级计算机也难以处理。然而，遗传算法却能在较短的时间内找到这个问题的答案。

我们来看一个N = 8个城市的情况。

首先进行城市编码：北京为1开元ky888棋牌官网版，上海为2，广州为3，深圳为4，天津为5，重庆为6，苏州为7，西安为8。

那么可能的旅程包括

共8！= 40320个

我们先随机地选出两个旅程作为“父母”：

接着，我们让这对父母交配，产生“子女”：

子女需承袭父母的遗传特征，同时确保每座城市仅访问一次。

然后我们让子女有所改变（红字部分）：

最终，我们对调整后的行程进行评估，这包括将广州至天津、天津至重庆……直至深圳的总里程数相加，并与父母的行程进行对比。接着，我们移除最长里程的行程，并重复上述步骤，这个过程会一直持续，直到里程数不再发生变化。

用遗传算法解决推销员的旅途问题

上图是N = 30个城市的计算例子。图（a）展示了30个城市的分布情况；（b）为进行10次搜索后的结果，依旧显得混乱无序；（c）是经过100次搜索后的效果，其中存在一些明显不合理的较大距离跳跃；（d）是搜索至1000次后的情形，大致轮廓已显现；（e）是搜索达到10000次后的结果，环绕一周的形态已非常接近最佳解；（f）显示了每次搜索时的距离变化，从图中可以观察到，在完成20000次搜索后，距离基本保持稳定。相应的结果就是最优的旅程。

我们曾运用遗传算法对多个工程设计问题进行求解，并取得了显著的成效。

今日，遗传算法已跻身人工智能算法领域中的关键流派。与此同时，与之相似的算法亦衍生出众多分支，诸如：

相较于我们先前所提及的贝叶斯算法、逻辑决策模型以及神经网络，遗传算法在收敛速度上更为迅速，且出错率较低。但在面对复杂问题时，它往往难以达到最佳解。遗传算法的这些限制或许正是进化过程本身所赋予的。以恐龙为例，尽管它们在地球上生存了长达1.65亿年，却未能进化出智能。而人类的智能则是一个偶然的进化产物。正是这个偶然，最终改变了世界的面貌。未来人类还会不断进化、不断地拓展自己的智能。

人工智能可以解决人类计算能力的不足，其发展也将是必然。

撰稿：杜如虚

排版：廖勉钰

往期精彩回顾：

广东科学中心「院士说」 | 人工智能算法之一：贝叶斯算法

广东科学中心「院士说」 | 人工智能算法之二：逻辑决策

广东科学中心「院士说」 | 人工智能之三：神经元网络