遗传算法入门

1、生物只有经过许多世代的不断演化(evolution),才能更好地完成生存与繁衍的 任务。遗传算法也遵循同样的方式，需要随着时间的推移不断成长、演化，最后 才能收敛，得到针对某类特定问题的一个或多个解。因此，了解一些有关有生命 的机体如何演化的知识，对理解遗传算法的演化机制是是有帮助的。本章的开始 几页将扼要阐述自然演化的机制(通常称为“湿”演化算法)，以及与之相关的术 语。即使你当年在中学里对生物并不擅长，也无须担心。本章不会涉及到过深的 细节，但对于理解自然演化的基本机制已经足够。抛开以上不论，当你读完本章 或下一章后，我想，你也会和我一样，深深叹服自然母亲的令人着迷！。从本质上说，任何生物机体不过就是一大堆细胞的集合。每个细胞都包含若 十组相同的DNA链，人们一般称之为染色体(chromosome)o染色体中包含 的DNA分为两股，这两股DNA链以螺旋状绞合在一起，如下面图3.1所示那 样，这就是我们所熟悉的DNA双螺旋结构模型。图3.1. DNA双螺旋结构。单个的染色体是由称作基因(gene)的更小的结构模块组成，而基因则又 由称作核苷酸(nucleotide)的物质组成。核苷酸

2、一共只有四种类型，即：腺嘌 吟(thymine)、鸟嘌吟(adenine)、胞嘧啶(cytocine)、胸腺嘧啶(guanine)。它们常 简写为T、A、C、G (我不知道为什么？.一笑)。这些核苷酸相互连接起来， 形成若干很长的基因链，而每个基因编码了生物机体的某种特征，如头发的颜色， 耳朵的样子，等。一个基因可能具有的不同设置(如头发的黑色、棕色或金黄色)， 称为等位基因(allele)，它们沿染色体纵向所处的物理部位称为基因的座位(locus)。一个细胞中的染色体组(collection)包含了复制该机体所需的全部信息。 这就是克隆怎样实行的秘密。你可以从被克隆施主(donor)身上，哪怕是一个 血细胞中包含的信息，复制出整个生物机体，例如一头羊。新的羊将会在每一个 方面和施主羊完全相同。染色体的这一集合就称为生物机体的基因组(genome)。在一特殊基因组中等位基因的一种状态称为该机体的遗传类型 (genotype)。这些就是用来生成实际的生物机体 一所谓表现型(phenotype)-本身的硬编码指令。你和我都是表现型。我们的DNA携带了我们的遗传类 型。如将这些术语用到其他领

3、域中，贝U，设计汽车用的成套蓝图就是一个遗传类 型；在生产线上隆隆作响的成品汽车就是一个表现型；只有设计被定型之前的， 那些完全阵旧的设计，才勉强称得上是一个基因组。行了，行话说到此已经足够了。现在让我们讨论，怎样把所有这些应用到进 化中去。如果你属于偶尔有机会离开计算机屏幕的那种人(因为我的朋友告诉我， 我才知道外边还有一个世界呢！)，你可能已经注意到，对于千千万万的动物和 植物一小到只有在显微镜下才能看到的单细胞生物，大到从空间卫星上也能见 到的巨大珊瑚礁一地球是它们共同的家，不管它们的大小怎样、形状或颜色又 怎样。一个生物机体被认为取得了成功，如果它得到了配偶并生下了一个子机体， 而后者完全有希望来继续进一步复制自己。为了做到这一点，生物机体必须善长许多工作。例如，能寻找食物和水、能 面对掠食者来保卫自己、能使自己吸引潜在的配偶，等。所有这些特长在某种程 度上都和生物机体的遗传类型一生命的蓝图有关。生物机体的某些基因将会产 生有助于它走向成功的属性，而另一些基因则可能要妨碍它取得成功。一个生物 的成功的量度就是它的适应性。生物机体愈能适应，它的子孙后代也就愈多。下 面转来讨论我们

4、的关键部分.。当两个生物机体配对和复制时，它们的染色体相互混合，产生一个由双方基 因组成的全新的染色体组。这一过程就叫重组(recombination)或交叠(crossover，又译杂交,交叉,交换)。这样就意味，后代继承的可能大部分是上 一代的优良基因，也可能继承了它们不少的不良基因。如果是前一种情况，后代 就可能变得比它的父母更能成功（例如，它对掠食者有更强的自卫机制）；如为 后一种情况，后代甚至就有可能不能再复制自己。这里要着重注意的是，愈能适 应的子孙后代就愈有可能继续复制并将其基因传给下一个子孙后代。由此就会显 示一种趋向，每一代总是比其父母一代生存和匹配得更完美。作为它的一个很简捷的例子，我们设想，雌性动物仅仅吸引大眼睛的雄性。 这样，在追求雌性配偶的雄性中，眼睛的尺寸愈大，其获得成功的可能性也愈大。 你可以说，动物的适应性正比于它的眼睛的直径。因此，你就可以看到，从一个 具有不同大小眼睛的雄性群体出发，当动物进化时，在同位基因中，能产生大眼 睛雄性动物的基因，相对于产生小眼睛雄性动物的基因，就更有可能被复制到下 一代。由此可以推出，当进化几代之后，大眼睛将会在雄性群体占

5、据统治地位。 过些时候，你就可以说，生物正在向一种特殊的遗传基因收敛。不过，有些读者可能已经会想到，如果这是繁殖期生物机体内唯一发生的事情， 那幺即使经历成千上万代后，适应能力最强的成员的眼睛也只能象初始群体中最 大的眼睛一样大。而根据我们对自然界的观察中发现，人类或动物的眼睛尺寸 实际存在一代大于一代的趋势。之所以会发生这种情况，是因为当基因传递给子 孙后代的过程中，会有很小的概率发生差错，从而使基因得到微小的改变。这多 少有点象中国古老的耳语传话游戏：在一队人中，把一条消息一个接一个地传递 下去；第一个人对着第二个人的耳朵轻声地讲述一个故事，第二个人再轻声地把 此故事传向第三个人，等，直到最后那个人再把听到的故事讲出来。通常这都会 诺出很多笑话：最后一个人讲出来故事与第一个所讲的已是面目全非。其实，这 种类型的差错在把信息从一个系统传递给另一系统时实际都会发生的。图3.2显 示的一列图画就是一个令人惊讶的例子。这是一次测试的结果：第一个人画出了 一只鸟类的图（见左上角）交给第二人，第二人看了以后自己重画一个给他的下 一个人，这样重复下去，直到最后那个人画出来的图形就会被显著异化。如

6、果 你有机会和十几个朋友聚集在一起，我推荐你做一下这个小试验，因为原始图画 能有如此多变化似乎难以置信。有趣的事实.古代的硬币容易产生这种类型的信息丢失差错。早期厄尔利凯尔特人和 条顿人所使用的硬币大量地被假冒着；在早先的原始硬币上能找到一位皇帝 的头像（那时已经在许多城市和乡镇用于支付）到后来则变成一匹马或一碗 果子的形状了。你一眼就能看出当时使用的假冒货币，无需使用任何高科技 的紫外线设备来探测！图3.2信息移转的一个试验。（Thames和Hudson提供的幻想图形）你可以说，图形或故事的情节在从一个人到另一个人的传递过程中，已经发生了 变异（或突变，mutation），同样的变异在生物繁衍过程中会在它们的基因中 出现。发生变异的概率通常都很小，但经历大量世代之后变异就会显得很可观。 一些变异对生物将是不利的（这有最大的可能），另一些则对生物的适应性可 能没有任何影响，但也有一些则可能会给生物带来一些明显的利益，使它能超过与其同类的生物。在前面我们所讲的例子中，你看到的能使动物引起眼睛直径变 大的基因突变就是一种有利的突变，它将使该动物与群体其余动物相比，就好像 一个超级的时髦模特

7、儿那样显得突出。这种使眼睛变得越来越大的趋势需要基因 参与才能实现。当进化过程经历成千上万代之后，就会使动物长出一对如同盛菜 的盘子那样大的眼睛！见图3.3。图3.3 一个Adonis的进化进化机制除了能改进已具备的特征之外，也能产生各种各样全新特征。让我们再 以眼睛的进化作为一个例子来说明吧。可以设想，曾有一个时期动物就根本没有眼睛。那时，动物在它们的环境中航行 完全是靠嗅觉和触觉来躲避掠食它们的动物。他们也相当擅长于这样做，因为 他们靠这样已经历了成千上万个世代。在那个时候，鼻子大和手脚长的男性是受 女孩子们欢迎的。然而，突然有一天，当两个动物配对时，一个基因突变发生在 为皮肤细胞提供的蓝图上。这一突变使其后代在他们的头上发育出了一个具有相 当光敏效应的细胞，使其后代能足够识别周围环境是亮的还是暗的。这样就给他 带来了一个微小的优点，因为，如果一种食肉动物，比如一只鹰，来到了某个范 围以内，则它将阻挡了光线，这时，该动物就会感觉得到，就可迅速跑到隐蔽的 地方去躲藏起来。另外，这种皮肤细胞还能指示现在是晚上或白天，或告诉他现 在是在地面之上或地面之下，这些信息在捕食和吸取营养时都能为

8、它提供方便。 你能看到这一新型皮肤细胞将使这一动物与群体中其余的动物相比，具备了稍多 的优点，并因此也就有更多的生存和繁殖的机会。过了一段时间，由于进化机制 的作用，许多动物的染色体中都会出现具有光敏皮肤细胞的基因。现在，如果你再作一些外推，想象这一光敏细胞基因得到了进一步的有利突变， 则你能看到，经过许多许多世代后，光敏细胞经过分化形成为一个区域；这个区 域不断变大，产生出一些更为确定的特征，例如形成一个品体，或产生能区别颜 色的视觉细胞；还可以想象，一个突变使某个动物由一个光敏区域改变为两个光 敏区域，由此就使那个动物有了立体视觉。立体视觉对一个生物体来说是一个巨 大的进步，因为这能精确告诉他目标离开他有多远。当然，你也可以把会对眼睛 产生不利影响的突变装入同样那些基因。但这里重要的一点是，这样生长出来的 后代将不会和已具备改进型眼睛的堂表亲戚们那样取得成功，它们最终将会灭 绝。只有成功的基因才会得到继承。你观察自然界中存在的任何特征就能发现， 它们的进化都是利用无数微小的突变发展而来的，且它们都是对拥有者有利。难 以置信吧？这些重组和变异机制说明了进化怎么完成。我希望现在你已经理

9、解，有机体是怎 么逐步形成各种不同类型的特征，以帮助它们在其生存环境中取得更大的成功。3.2 二进制数速成（A Quick Lesson in Binary Numbers ）当进入更深层的学习之前，我必需确保你对二进制记数系统的理解。如果你已经 知道二进制记数的工作原理，可以跳过这一小节。如果你还不了解，就让我来启 发你.我认为了解二进制数（基为2的数）的最容易的方法，就是首先查看一下十进制数：你为 什么使用十进制数字（基为10的数）和怎样使用十进制计数？人们通常相信，人类之所以采用基数为十的记数法来计数，是因为我们的双手共有十个手指 的缘故。设想我们的一个祖先，不妨称他为Ug，几十万年前在计算一个猛犸群中猛犸的数 目。Ug利用2个拳头来开始计算，当他每看到一个猛犸，就伸出一个手指；这样继续下去， 直到他所有的手指都被用上为止；这样他就知道他已经算到10个猛犸。但因猛犸群中包含 的猛犸远远超过10个，Ug不得不再想一种方法来计算更大的数目。他狠抓了一下他的脑 袋，就产生了一个想法：叫他的一个朋友Frak来帮忙。Ug想到用Frak的一个手指来代表 他计算到的那10个猛犸，然后他自己的手指就得到解脱，可重新开始用来计算第11、12、 13个猛犸，等等，直到20，这时就需要使用Frak的另一个手指。你能看出，采用这样的 过程，Ug和Frak最多可以计算到110个猛犸（那真是一桩了不起的奇观，不是吗？）， 但为了统计出更多的猛犸数目，他们就不得不去招募另一位朋友了。当人们最终学会了怎么写出数字时，就是使用类似方法来完成的。为了表示基数为10的数 字，你创建一系列的列（columns），每一列代表人的一双手，例如：1000 位100位10位个位因此，要计数到15,你先在个位（列）由0开始不断递增，直到9,然后，因个位已不能 再增，你就在10位记1,并从新在个位由0开始不断增加，直到如下结束：1000 位100位10位个位15数字15由一个十位和5个个位组成。（我知道，你听到这些会感到非常显然

《遗传算法入门》由会员新**分享，可在线阅读，更多相关《遗传算法入门》请在金锄头文库上搜索。