人工智能 遗传算法(人工智能遗传算法例题)

 

原作始发于广东科学中心，共分为五部分，本文为第四部分内容。

听到遗传这两个字读者们也许会想到达尔文的进化论

达尔文

1859年11月24日，达尔文出版了他的名著《物种起源》（The Origin of Species）。

这一年达尔文50岁，早已经是英国皇家学会的院士了。他用了二十多年的时间来写这本书。这时他坐在家中等待着风暴的来临。《物种起源》的第一版印了1250本，在一天之内全部售罄。

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

世界是进化的、不是静止不变的；世界不可能是一时之间创造出来的；世界没有目的；人类的存在没有目的；事物可用物质的进化过程来描述；事物的本质是变化的，不是静止不变的

这六个论点每一个都与《圣经》所说的相反。当时不论是政治思想还是经济财富，教会都占有绝对优势，其言论引发的风暴可想而之。

达尔文的《物种起源》改变了世界学者们沿着达尔文开创的道路深入研究发现了一个重要问题物种进化是通过什么来实现的？

格雷戈尔·孟德尔

格雷戈尔·孟德尔（Gregor Johann Mendel，1822-1884）首先提出了基因的概念。

孟德尔出生于奥匈帝国的海因策道夫（Heinzendorf，现为捷克的亨奇采Hynčice）。他的父亲是农民，所以他从小就学会了园艺。由于家境不好，他加入了教会以获取奖学金去读书。格雷戈尔实际上是他的教会名字，意为警醒。他在维也纳大学读书时的物理学导师是多普勒效应的发现者克里斯蒂安·多普勒。他很想当个物理学教师，但两次考试都没有考上。所以只好回到教会当牧师。在教会的生活简单有序，他就把在大学时所做的农艺实验继续做了下去。

在1856-1863年间，孟德尔做了28000多次豌豆杂交实验，并据此提出遗传因子（基因）的概念以及基因遗传两定律：基因分离定律和基因自由组合定律。1866年，他把这些结果发表在一个地方性的学术期刊上，但并没有引起重视。1868年，他升任当地教会的主持，他的实验也就此停止了。1900年，人们重新发现了孟德尔的文章，基因和遗传定律也开始遍传世界。这时他已经过世多年了。

是不是感叹大神们的伟大成就别急别急还有呢

詹姆斯·沃森

1953年，詹姆斯·沃森（James Dewey Watson）和弗朗西斯·克里克（Francis Harry Compton Crick，1916-2004）发现了DNA的双螺旋结构。从此人们看到了基因的奥妙。

DNA是Deoxyribonucleic Acid的缩写，中文名叫做脱氧核糖核酸。DNA是由许多脱氧核苷酸（deoxynucleotide）组成的大分子。脱氧核苷酸是由碱基、脱氧核糖以及磷酸三种物质组成的小分子化合物。碱基有四种：腺嘌呤（adenine，简称A）、胸腺嘧啶（thymine，简称T）、胞嘧啶（cytosine，简称C）和鸟嘌呤（guanine，简称G）。

如上图所示，两条脱氧核苷酸链围绕一个共同的中心轴盘绕，构成双螺旋结构。脱氧核糖-磷酸链在螺旋结构的外面，碱基朝向里面。两条脱氧核苷酸链反向互补，并通过碱基间的氢键形成碱基配对相连，A总是与T配对，C总是与G配对。从而形成稳定的组合。一个碱基约为0.2纳米（nm，即10-6 mm），碱基对之间的距离（即双螺旋之间的距离）约为2.2~2.6纳米。

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

我们用细胞分裂为例来说明这个过程。大部分动物和植物的细胞都是0.01~0.1 毫米（mm）左右大小。细胞的细胞核中藏有完整的基因。我们人类有19,000~20,000个基因，这些基因由约30亿个碱基对构成，连接起来有2米长。它们折叠着分存在23个染色体（chromosome）中。科学家们在2001年完成了人类基因的测序，不过至今还没能完全了解对每个基因作用。

上图描述了细胞的有丝分裂过程。图中有的细胞有一对染色体（Diploid）。当细胞分裂时，双螺旋结构打开，脱氧核苷酸链上的碱基在环境中获取与之相应的碱基，构建出两个相同的双螺旋结构，因此一对染色体就变成了两对。接着细胞按照基因的编码构建出新的细胞材料。细胞越长越大，最后一分为二，完成了细胞分裂。这个遗传复制过程非常稳定，新得到的两细胞都和原来的细胞一模一样。

通过基因科学家们可以追溯生命的起源，了解物种进化，构建新的物种。

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

这就是我的母校密西根大学的约翰·荷兰（John Henry Holland，1929-2015）教授提出的遗传算法了（Genetic Algorithm）。

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

约翰·荷兰

互联网小常识：IP地址经历了四个阶段：标准分类的IP地址、划分子网的三级地址结构、构成超网的无类域间路由技术（CIDR）和网络地址转换NAT技术。

遗传算法的基本思想很简单：在群体中找一对父母，让他们生育出子女。子女会经过修改，然后加以评价。子女的评价也结合群体的评价，群体中评价最低的个体将被删除。如此循环不已，直到群体达到最优。

我们来一个看用遗传算法解决推销员旅程设计的例子：推销员要去N个城市推销，每个城市只能去一次，而且要选最短的旅程。这个问题是爱尔兰数学家威廉·密尔顿（Sir William Rowan Hamilton，1805¾1865）首先提出来的，它看上去似乎简单，但是其计算量为N！= N(N-1)(N-2) … (2)(1)。

当N等于25时，N！= 1.551121004´1025，这个数字是如此巨大，即便是超级计算机也难以解决。遗传算法却可以较快地求解出这一问题。

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

先把城市编码：1 — 北京，2 — 上海，3 —广州，4 —深圳，5 — 天津， 6 — 重庆，7 — 苏州，8 — 西安。

那么可能的旅程包括

（1—2—3—4—5—6—7—8），（1—3—2—4—5—6—7—8），（1—2—4—3—5—6—7—8），

共8！= 40320个

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

旅程1 = (3 5 7 2 1 6 4 8)旅程2 = (2 5 7 6 8 1 3 4)

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

旅程1 = (3 57 2 1 64 8)旅程2 = (2 5 7 6 8 13 4)旅程3 = (3 57 2 1 6 3 4)

注意，子女既要继承父母的基因（红字部分），又要保证每个城市只去一次的要求（蓝字部分）。

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

Tour3 = (3 572 163 4)Tour4 = (3 562 173 4)

最后我们评价修改后的旅程，即把广州— 天津 — 重庆 … — 深圳的公里数加起来，并与其父母进行比较。然后，我们把公里数最长的旅程删掉，再重复上述的过程，如此重复直至公里数不再改变为止。

上图是N = 30个城市的计算例子。其中的图（a）是30个城市的分布图；（b）是搜索了10次后的结果，看上去还是杂乱无章；（c）是搜索了100次后的结果，上面有几个大距离的跳跃显然是不合理的；（d）是搜索了1000次以后的结果，已经可以看出个大概了；（e）是搜索了10000次以后的结果，这个环绕一周的结果很接近最优了；（f）是各次搜索时的距离，从图中可见，在搜索了20000次以后，距离就基本不变了。相应的结果就是最优的旅程。

我们曾经用遗传算法求解过好几个工程设计的问题，都获得了成功。

今天，遗传算法已经成为人工智能算法中重要的一支。类似的算法也发展出了多种，包括：

群组遗传算法（Group genetic algorithm）群智能算法（Swarm intelligence）模拟退火算法（Simulated annealing）模因算法（Memetic algorithm）等

与我们前面介绍过的贝叶斯算法、逻辑决策方法与神经元网络相比，遗传算法收敛快、不容易出错。然而，对于复杂的问题则难以获得最优。遗传算法的局限性也许是进化本身所决定的。例如恐龙在地球上生活了1.65亿年，却没有进化出智能。人类获得智能只是个进化的偶然结果。这个偶然却导致了世界的改变。未来人类还会不断进化、不断地拓展自己的智能。

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

撰稿：杜如虚排版：廖勉钰

往期精彩回顾：

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

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

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

互联网小常识：IEEE802.11定义了两种类型的设备，无线结点和无线接入点，工作在2.4GHZ的ISM波段内。速度为1Mbps，2Mbps。

免责声明：本站所有信息均搜集自互联网，并不代表本站观点，本站不对其真实合法性负责。如有信息侵犯了您的权益，请告知，本站将立刻处理。联系QQ：1640731186