遗传算法入门

《遗传算法入门》由会员分享，可在线阅读，更多相关《遗传算法入门（39页珍藏版）》请在装配图网上搜索。

1、生物只有经过许多世代的不断演化(evolution),才能更好地完成生存与繁衍的 任务。遗传算法也遵循同样的方式，需要随着时间的推移不断成长、演化，最后 才能收敛，得到针对某类特定问题的一个或多个解。因此，了解一些有关有生命 的机体如何演化的知识，对理解遗传算法的演化机制是是有帮助的。本章的开始 几页将扼要阐述自然演化的机制(通常称为“湿”演化算法)，以及与之相关的术 语。即使你当年在中学里对生物并不擅长，也无须担心。本章不会涉及到过深的 细节，但对于理解自然演化的基本机制已经足够。抛开以上不论，当你读完本章 或下一章后，我想，你也会和我一样，深深叹服自然母亲的令人着迷！。从本质上说，任何生物

2、机体不过就是一大堆细胞的集合。每个细胞都包含若 十组相同的DNA链，人们一般称之为染色体(chromosome)o染色体中包含 的DNA分为两股，这两股DNA链以螺旋状绞合在一起，如下面图3.1所示那 样，这就是我们所熟悉的DNA双螺旋结构模型。图3.1. DNA双螺旋结构。单个的染色体是由称作基因(gene)的更小的结构模块组成，而基因则又 由称作核苷酸(nucleotide)的物质组成。核苷酸一共只有四种类型，即：腺嘌 吟(thymine)、鸟嘌吟(adenine)、胞嘧啶(cytocine)、胸腺嘧啶(guanine)。它们常 简写为T、A、C、G (我不知道为什么？.一笑)。这些核苷酸

3、相互连接起来， 形成若干很长的基因链，而每个基因编码了生物机体的某种特征，如头发的颜色， 耳朵的样子，等。一个基因可能具有的不同设置(如头发的黑色、棕色或金黄色)， 称为等位基因(allele)，它们沿染色体纵向所处的物理部位称为基因的座位(locus)。一个细胞中的染色体组(collection)包含了复制该机体所需的全部信息。 这就是克隆怎样实行的秘密。你可以从被克隆施主(donor)身上，哪怕是一个 血细胞中包含的信息，复制出整个生物机体，例如一头羊。新的羊将会在每一个 方面和施主羊完全相同。染色体的这一集合就称为生物机体的基因组(genome)。在一特殊基因组中等位基因的一种状态称为该

4、机体的遗传类型 (genotype)。这些就是用来生成实际的生物机体 一所谓表现型(phenotype)-本身的硬编码指令。你和我都是表现型。我们的DNA携带了我们的遗传类 型。如将这些术语用到其他领域中，贝U，设计汽车用的成套蓝图就是一个遗传类 型；在生产线上隆隆作响的成品汽车就是一个表现型；只有设计被定型之前的， 那些完全阵旧的设计，才勉强称得上是一个基因组。行了，行话说到此已经足够了。现在让我们讨论，怎样把所有这些应用到进 化中去。如果你属于偶尔有机会离开计算机屏幕的那种人(因为我的朋友告诉我， 我才知道外边还有一个世界呢！)，你可能已经注意到，对于千千万万的动物和 植物一小到只有在显微

5、镜下才能看到的单细胞生物，大到从空间卫星上也能见 到的巨大珊瑚礁一地球是它们共同的家，不管它们的大小怎样、形状或颜色又 怎样。一个生物机体被认为取得了成功，如果它得到了配偶并生下了一个子机体， 而后者完全有希望来继续进一步复制自己。为了做到这一点，生物机体必须善长许多工作。例如，能寻找食物和水、能 面对掠食者来保卫自己、能使自己吸引潜在的配偶，等。所有这些特长在某种程 度上都和生物机体的遗传类型一生命的蓝图有关。生物机体的某些基因将会产 生有助于它走向成功的属性，而另一些基因则可能要妨碍它取得成功。一个生物 的成功的量度就是它的适应性。生物机体愈能适应，它的子孙后代也就愈多。下 面转来讨论我们

6、的关键部分.。当两个生物机体配对和复制时，它们的染色体相互混合，产生一个由双方基 因组成的全新的染色体组。这一过程就叫重组(recombination)或交叠(crossover，又译杂交,交叉,交换)。这样就意味，后代继承的可能大部分是上 一代的优良基因，也可能继承了它们不少的不良基因。如果是前一种情况，后代 就可能变得比它的父母更能成功（例如，它对掠食者有更强的自卫机制）；如为 后一种情况，后代甚至就有可能不能再复制自己。这里要着重注意的是，愈能适 应的子孙后代就愈有可能继续复制并将其基因传给下一个子孙后代。由此就会显 示一种趋向，每一代总是比其父母一代生存和匹配得更完美。作为它的一个很简

7、捷的例子，我们设想，雌性动物仅仅吸引大眼睛的雄性。 这样，在追求雌性配偶的雄性中，眼睛的尺寸愈大，其获得成功的可能性也愈大。 你可以说，动物的适应性正比于它的眼睛的直径。因此，你就可以看到，从一个 具有不同大小眼睛的雄性群体出发，当动物进化时，在同位基因中，能产生大眼 睛雄性动物的基因，相对于产生小眼睛雄性动物的基因，就更有可能被复制到下 一代。由此可以推出，当进化几代之后，大眼睛将会在雄性群体占据统治地位。 过些时候，你就可以说，生物正在向一种特殊的遗传基因收敛。不过，有些读者可能已经会想到，如果这是繁殖期生物机体内唯一发生的事情， 那幺即使经历成千上万代后，适应能力最强的成员的眼睛也只能象

8、初始群体中最 大的眼睛一样大。而根据我们对自然界的观察中发现，人类或动物的眼睛尺寸 实际存在一代大于一代的趋势。之所以会发生这种情况，是因为当基因传递给子 孙后代的过程中，会有很小的概率发生差错，从而使基因得到微小的改变。这多 少有点象中国古老的耳语传话游戏：在一队人中，把一条消息一个接一个地传递 下去；第一个人对着第二个人的耳朵轻声地讲述一个故事，第二个人再轻声地把 此故事传向第三个人，等，直到最后那个人再把听到的故事讲出来。通常这都会 诺出很多笑话：最后一个人讲出来故事与第一个所讲的已是面目全非。其实，这 种类型的差错在把信息从一个系统传递给另一系统时实际都会发生的。图3.2显 示的一列图

9、画就是一个令人惊讶的例子。这是一次测试的结果：第一个人画出了 一只鸟类的图（见左上角）交给第二人，第二人看了以后自己重画一个给他的下 一个人，这样重复下去，直到最后那个人画出来的图形就会被显著异化。如果 你有机会和十几个朋友聚集在一起，我推荐你做一下这个小试验，因为原始图画 能有如此多变化似乎难以置信。有趣的事实.古代的硬币容易产生这种类型的信息丢失差错。早期厄尔利凯尔特人和 条顿人所使用的硬币大量地被假冒着；在早先的原始硬币上能找到一位皇帝 的头像（那时已经在许多城市和乡镇用于支付）到后来则变成一匹马或一碗 果子的形状了。你一眼就能看出当时使用的假冒货币，无需使用任何高科技 的紫外线设备来探

10、测！图3.2信息移转的一个试验。（Thames和Hudson提供的幻想图形）你可以说，图形或故事的情节在从一个人到另一个人的传递过程中，已经发生了 变异（或突变，mutation），同样的变异在生物繁衍过程中会在它们的基因中 出现。发生变异的概率通常都很小，但经历大量世代之后变异就会显得很可观。 一些变异对生物将是不利的（这有最大的可能），另一些则对生物的适应性可 能没有任何影响，但也有一些则可能会给生物带来一些明显的利益，使它能超过与其同类的生物。在前面我们所讲的例子中，你看到的能使动物引起眼睛直径变 大的基因突变就是一种有利的突变，它将使该动物与群体其余动物相比，就好像 一个超级的时髦模特

11、儿那样显得突出。这种使眼睛变得越来越大的趋势需要基因 参与才能实现。当进化过程经历成千上万代之后，就会使动物长出一对如同盛菜 的盘子那样大的眼睛！见图3.3。图3.3 一个Adonis的进化进化机制除了能改进已具备的特征之外，也能产生各种各样全新特征。让我们再 以眼睛的进化作为一个例子来说明吧。可以设想，曾有一个时期动物就根本没有眼睛。那时，动物在它们的环境中航行 完全是靠嗅觉和触觉来躲避掠食它们的动物。他们也相当擅长于这样做，因为 他们靠这样已经历了成千上万个世代。在那个时候，鼻子大和手脚长的男性是受 女孩子们欢迎的。然而，突然有一天，当两个动物配对时，一个基因突变发生在 为皮肤细胞提供的蓝

12、图上。这一突变使其后代在他们的头上发育出了一个具有相 当光敏效应的细胞，使其后代能足够识别周围环境是亮的还是暗的。这样就给他 带来了一个微小的优点，因为，如果一种食肉动物，比如一只鹰，来到了某个范 围以内，则它将阻挡了光线，这时，该动物就会感觉得到，就可迅速跑到隐蔽的 地方去躲藏起来。另外，这种皮肤细胞还能指示现在是晚上或白天，或告诉他现 在是在地面之上或地面之下，这些信息在捕食和吸取营养时都能为它提供方便。 你能看到这一新型皮肤细胞将使这一动物与群体中其余的动物相比，具备了稍多 的优点，并因此也就有更多的生存和繁殖的机会。过了一段时间，由于进化机制 的作用，许多动物的染色体中都会出现具有光敏

13、皮肤细胞的基因。现在，如果你再作一些外推，想象这一光敏细胞基因得到了进一步的有利突变， 则你能看到，经过许多许多世代后，光敏细胞经过分化形成为一个区域；这个区 域不断变大，产生出一些更为确定的特征，例如形成一个品体，或产生能区别颜 色的视觉细胞；还可以想象，一个突变使某个动物由一个光敏区域改变为两个光 敏区域，由此就使那个动物有了立体视觉。立体视觉对一个生物体来说是一个巨 大的进步，因为这能精确告诉他目标离开他有多远。当然，你也可以把会对眼睛 产生不利影响的突变装入同样那些基因。但这里重要的一点是，这样生长出来的 后代将不会和已具备改进型眼睛的堂表亲戚们那样取得成功，它们最终将会灭 绝。只有成

14、功的基因才会得到继承。你观察自然界中存在的任何特征就能发现， 它们的进化都是利用无数微小的突变发展而来的，且它们都是对拥有者有利。难 以置信吧？这些重组和变异机制说明了进化怎么完成。我希望现在你已经理解，有机体是怎 么逐步形成各种不同类型的特征，以帮助它们在其生存环境中取得更大的成功。3.2 二进制数速成（A Quick Lesson in Binary Numbers ）当进入更深层的学习之前，我必需确保你对二进制记数系统的理解。如果你已经 知道二进制记数的工作原理，可以跳过这一小节。如果你还不了解，就让我来启 发你.我认为了解二进制数（基为2的数）的最容易的方法，就是首先查看一下十进制数：

15、你为 什么使用十进制数字（基为10的数）和怎样使用十进制计数？人们通常相信，人类之所以采用基数为十的记数法来计数，是因为我们的双手共有十个手指 的缘故。设想我们的一个祖先，不妨称他为Ug，几十万年前在计算一个猛犸群中猛犸的数 目。Ug利用2个拳头来开始计算，当他每看到一个猛犸，就伸出一个手指；这样继续下去， 直到他所有的手指都被用上为止；这样他就知道他已经算到10个猛犸。但因猛犸群中包含 的猛犸远远超过10个，Ug不得不再想一种方法来计算更大的数目。他狠抓了一下他的脑 袋，就产生了一个想法：叫他的一个朋友Frak来帮忙。Ug想到用Frak的一个手指来代表 他计算到的那10个猛犸，然后他自己的手

16、指就得到解脱，可重新开始用来计算第11、12、 13个猛犸，等等，直到20，这时就需要使用Frak的另一个手指。你能看出，采用这样的 过程，Ug和Frak最多可以计算到110个猛犸（那真是一桩了不起的奇观，不是吗？）， 但为了统计出更多的猛犸数目，他们就不得不去招募另一位朋友了。当人们最终学会了怎么写出数字时，就是使用类似方法来完成的。为了表示基数为10的数 字，你创建一系列的列（columns），每一列代表人的一双手，例如：1000 位100位10位个位因此，要计数到15,你先在个位（列）由0开始不断递增，直到9,然后，因个位已不能 再增，你就在10位记1,并从新在个位由0开始不断增加，直到

17、如下结束：1000 位100位10位个位15数字15由一个十位和5个个位组成。（我知道，你听到这些会感到非常显然，但是这种详 细的分析是必要的。）你能看到，二进制数系（或不管哪一种进制数系）都用同样的方式工 作。但二进制计数时不用10个数字，而只用2个译注：原文误为1个，其中一个是0， 另一个是1。这样，当你在写2进制数时，表示数的列（在2进制数人们称作bit的形式 应为:16842个位现在你就可以来计算15。首先，你在个位（列）加1，得:16842个位1并将个位数从新变为0，因此数字2的形式如下:这时，因为你已经没有更大的数字可以用了（请记住，2进制数中最大的数是1），你必须 增加个位左边的

18、那个列16842个位10数字3的形式为:16842个位11数字4的形式为:16842个位100等等，直到数字15：16842个位1111这就是计算15所要做的全部过程了。至此，你应该能够转换十进制数为二进制，或反过来， 把二进制转换为十进制了。我同时必须指出，二进制数字也常常写成一组有固定长度的位， 特别当它与计算机联系起来讨论时如此。这就是为什么处理器常被说成是8位、I6位、32 位、或64位的原因。这意味，如果你要把15写成8位的二进制，则你就要写成下面这样 的形式，其中高位都是0,但也要在前面写出来，以使整个长度达到8：00001111为了确保你理解这一概念，作为一个练习，在你继续进入下

19、一节以前，试回答下列问题（答 案附在本章最后）：1. 把十进制27转换为二进制。2. 把二进制数10101转换为十进制。3. 把十进制数135表示成为一个8位的二进制数。不难吧？既然你对二进制数有了一个初步概念，下面就让我们来讨论令人更加激动的内容 吧！3.3 计算机内的进化（Evolution Inside Your Computer ）遗传算法的工作过程本质上就是模拟生物的进化过程。首先，要规定一种编码方法，使得你 的问题的任何一个潜在可行解都能表示成为一个数字”染色体。然后，创建一个由随机的染 色体组成的初始群体（每个染色体代表了一个不同的候选解），并在一段时期中，以培育适 应性最强的个

20、体的办法，让它们进化，在此期间，染色体的某些位置上要加入少量的变异。 经过许多世代后，运气好一点，遗传算法将会收敛到一个解。遗传算法不保证一定能得到解， 如果有解也不保证找到的是最优解，但只要采用的方法正确，你通常都能为遗传算法编出一 个能够很好运行的程序。遗传算法的最大优点就是，你不需要知道怎么去解决一个问题；你 需要知道的仅仅是，用怎么的方式对可行解进行编码，使得它能能被遗传算法机制所利用。通常，代表可行解的染色体采用一系列的二进制位作为编码。在运行开始时，你创建一个染 色体的群体，每个染色体都是一组随机的2进制位。2进制位（即染色体）的长度在整个群 体中都是一样的。作为一个例子，长度为2

21、0的染色体的形状如下：01010010100101001111重要的事情就在于，每个染色体都用这样的方式编码成为由0和1组成的字符串，而它们 通过译码就能用来表示你手头问题的一个解。这可能是一个很差的解，也可能是一个十分 完美的解，但每一个单个的染色体都代表了一个可行解（下面就将讨论有关编码的更多的细 节）。初始群体通常都是很糟的，有点象英国板球队或美国足球队（抱歉了！）。但不管 怎样，正如我前面说过的那样，一个初始的群体已经创建完成（对这一例子，不妨设共有 100个成员），这样，你就可以开始做下面列出的一系列工作（你不用担心用粗体显示的那 些词句，我后面马上就会来解释一切）：不断进行下列循环

22、，直到寻找出一个解:1. 检查每个染色体，看它解决问题的性能怎样，并相应地为它分配一个适应性分数。2. 从当前群体中选出2个成员。被选出的概率正比于染色体的适应性，适应性分数愈高， 被选中的可能性也就愈大。常用的方法就是采用所谓的轮盘赌选择法或赌轮选择法 （Roulette wheel selection ）。3. 按照预先设定的杂交率（Crossover Rate ），从每个选中染色体的一个随机的点上进 彳亍杂交（crossover ）。4. 按照预定的变异率（mutation rate ），通过对被选染色体的位的循环，把相应的位实 行翻转（flip ）。5. 重复步骤2, 3, 4,直到1

23、00个成员的新群体被创建出来。结束循环 以上算法中步骤1到步骤5的一次循环称为一个代(或世代，generation)0而我把这整 个的循环称作一个时代(epoch)，在我的正文和代码中将始终都用这样方式来称呼。3.3.1 什么是轮盘赌选择？ ( Whats the Roulette Wheel Selection )轮盘赌选择是从染色体群体中选择一些成员的方法，被选中的机率和它们的适应性分数成比 例，染色体的适应性分数愈高，被选中的概率也愈多。这不保证适应性分数最高的成员一定 能选入下一代，仅仅说明它有最大的概率被选中。其工作过程是这样的：设想群体全体成员的适当性分数由一张饼图来代表(见图3.

24、4)，这一饼图就和用于赌博的转 轮形状一样。我们要为群体中每一染色体指定饼图中一个小块。块的大小与染色体的适应性 分数成比例，适应性分数愈高，它在饼图中对应的小块所占面积也愈大。为了选取一个染色 体，你要做的，就是旋转这个轮子，并把一个小球抛入其中，让它翻来翻去地跳动，直到轮 盘停止时，看小球停止在哪一块上，就选中与它对应的那个染色体。本章后面我就会告诉你 怎样来编写这种程序的准确算法。图3.4染色体的轮盘赌式选择3.3.2 什么是杂交率？( Whats the Crossover Rate )杂交率就是用来确定2个染色体进行局部的位(bit)的互换以产生2个新的子代的概率。实 验表明这一数值

25、通常取为0.7左右是理想的，尽管某些问题领域可能需要更高一些或较低一 些的值。每一次，我们从群体中选择2个染色体，同时生成其值在0到1之间一个随机数，然后根 据此数据的值来确定两个染色体是否要进行杂交。如果数值低于杂交率（O.7）就进行杂交， 然后你就沿着染色体的长度随机选择一个位置，并把此位置后面所有的位进行互换。例如，设给定的2个染色体为：1000100111001001001010001001000011沿着它们的长度你随机选择一个位置，比如说10，然后互换第10位之后所有位。这样两 个染色体就变成了（我已在开始互换的位置加了一个空格）：100010011 010000110101000

26、10 100100103.3.3 什么是变异率？（ Whats the Mutation Rate?）变异率（突变率）就是在一个染色体中将位实行翻转（flip，即0变1, 1变0）的几率。 这对于二进制编码的基因来说通常都是很低的值，比如0.001。因此，无论你从群体中怎样选择染色体，你首先是检查是否要杂交，然后再从头到尾检查子 代染色体的各个位，并按所规定的几率对其中的某些位实行突变（翻转）。3.3.4 怎么搞的啦！（ Phew!）如果你对上面讲东西感到有些茫然，那也不必担心！从现在开始直到本章结束，所有阅读材 料大多数都被设计用来重读两遍。这里有很多需要你理解的新概念，且它们都是相互混杂在

27、 一起。我相信对于你这是最好的学习方法。当你通读第一遍时，你有望对一些基本概念得到 一些孤立的感性认识，而在阅读第二遍时（如果我做的工作是正确的话），你就能看到各种 不同的概念怎样相互联系起来。而当你最后结合源程序来开始编程玩弄时，每一件事物都只 是考虑怎样周密地进行安排的问题，到那时你的工作仅仅是一种如何来提炼你的知识和技能 的事了（那是比较容易的一部分）。注意：在本书所附的光盘的Chaper3/Pathfinder文件夹中，你能找到 Pathfinder工程的全部源码。如果你想在进一步阅读课文之前窥视一下工程的全貌，在Chaper3/Executable文件中有一个预先制作好的执行程序，P

28、athfinder.exe。3.4 帮助 Bob 回家(Helping Bob Home)由于寻找路径问题被看成是游戏人工智能的一块神圣基石，我们下面就来创建一 个遗传算法，用在一个非常简单的场景中解决寻找路径问题。为此，我们将创建 一个迷宫，它的左边有一入口，右边有一出口，并有一些障碍物散布在其中。然 后在出发点放置一个虚拟的人，我们叫他鲍勃（Bob），然后要为他解决如何寻 找路径的问题，使他能找到出口，并避免与所有障碍物相碰撞。下面我将说明怎 样来产生Bob的染色体的编码，但首先需要解释怎样来表示迷宫.迷宫是一个2D整数型数组；用0来表示开放的空间，1代表墙壁或障碍物，5 是起始点，8是出

29、口。因此，整数数组：. 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,.1,0,1,0,0,0,0,0,1,1,1,0,0,0,1, .5,0,0,0,0,0,0,0,1,1,1,0,0,0,1, .1,0,0,0,1,1,1,0,0,1,0,0,0,0,1, .1,0,0,0,1,1,1,0,0,0,0,0,1,0,1, .1,1,0,0,1,1,1,0,0,0,0,0,1,0,1, .1,0,0,0,0,1,0,0,0,0,1,1,1,0,1, .1,0,1,1,0,0,0,1,0,0,0,0,0,0,8, .1,0,1,1,0,0,0,1,0,0,0,0,0,0,1,.1,

30、1,1,1,1,1,1,1,1,1,1,1,1,1,1 在屏幕上看起来将会有下面图3.5的样子:Cko.pt.cr3 - Pathfinder图3.5 Bob的迷宫，用红色标出了入口和出口它定义作者已把这种地图设计方法封装在一个被称作CBobsMap的类中，为：class CBobsMap private:/保存地图用的存储器（一个2维整型数组）static const int mapMAP_HEIGHTMAP_WIDTH;static const int m_iMapWidth; /地图的宽度static const int m_iMapHeight; /地图的高度/起始点在数组中的下标st

31、atic const int m_iStartX;static const int m_iStartY;/终点的数组下标static const int miEndX;static const int miEndY;public:/你可以利用这一数组作为Bob存储器，如果需要的话int memoryMAP_HEIGHTMAP_WIDTH;CBobsMap()ResetMemory();/利用一个字符串来记录Bob行进的方向，其中每一个字符代表/Bob所走的一步；检查Bob离开出口还有多远；/返回一个与到达出口距离成正比的适应性分数double TestRoute(const vector &v

32、ecPath,CBobsMap &memory);/Render 函数利用 WindowsGDI在一个给定的surface上显示地cxClient,cyClient,surface);void Render(const int const int HDC/画出能够存放于存储器中的不管什么样的路径void MemoryRender(const int cxClient, const int cyClient. HDCsurface);void ResetMemory();.o.由上可以看出，我们只需要以常量的形式来保存地图数组以及起点和终点的坐标就行了。这些数据是在文件CBobsMap.cpp中

33、定义的，在光盘上你能找 到它的相关的文件夹。除了存储迷宫的数据外，这个Map类也用来记录Bob在 迷宫中所走过的路程：memory。这对遗传算法本身而言不是本质的，但为了显示目的，使你能看到Bob怎样在迷宫中漫游，设置一个记录是必需的。这里重要的是成员函数TestRoute()，它需要利用一系列的行进方向来检测Bob走了多远。这里我不准备花费时间来列出TestRoute函数的清单，因为这 是十分简单的那种函数，但要列出来却可能需要长长的2页。我们只需要说明一 下就行了。给出一个方向向量，它的每个分量能代表向北(North)、向南(South)、 向东(East)、向西(West)四个方向之一，

34、让Bob按照它在地图中行走， TestRoute计算Bob能到达的最远点的位置，然后返回一个适应性分数，它正 比于Bob最终位置离出口的距离。他所到达的位置离开出口愈近，奖励给他的 适应性分数也愈高。如果他实际已到达了出口，则我们就要向他表示祝贺了，他 将得到满分1。这时循环就会自动结束，因为你已经找到一个解了，可以喊乌拉 了！.再有，不要因为理解不了这个类的任何一点而操心。我们下面马上就会开始 讨论有关的每一件事情的3.4.1为染色体编码(Ecoding the Chromosome)每个染色体必须把小人Bob的每一个行动编入代码中。Bob的行动仅限为4个方向：向东(East)，向南(Sou

35、th)，向西(West)，向北(North)故编码后的染色体应该就是代表这4个方向信息的一个字符串。传统的编码方法就是把方 向变换成二进制的代码。四个方向只要2位就够了，例如下表所示的那样：二进制代码十进制译码代表的方向000向北011向南102向东113向西这样，如果你得到了一个随机的二进制字符串，你就能将它译码出Bob行动时所遵循的 一系列方向。例如染色体：111110011011101110010101代表的基因就是：11,11,10,01,10,11,10,11,10,01,01,01当把二进制代码译成十进制时，就成为3,3,2,1,2,3,2,3,2,1,1,1再把这些放进一个表格中

36、，就可以使你相信这是一样的一些概念:二进制代码十进制译码代表的方向113West113West102East011South102East113West102East113West102East011South011South011South到此，你要做的全部就是将Bob置于迷宫的起点，然后告诉他根据这张表所列的方向 一步步地走。如果按某一个方向前进将使Bob碰到墙壁或障碍物，则只需忽略该方向并继 续按下一个方向去走就行了。这样不断下去，直到所有方向用光或Bob到达出口时为止。如果你想象有几百个这样的随机的染色体，你就能看到它们中的某些可能为Bob译码 出到达出口的一套方向（问题的一个解），但

37、它们中的大多数将是失败的。遗传算法以随机的2进制串（染色体）作为初始群体，测试它们每一个能让Bob走到 离开出口有多么接近，然后让其中最好的那些来孵化后代，期望它们的子孙中能有比Bob 走得离出口更近一点。这样继续下去，直到找出一个解，或直到Bob绝望地在一个角落里 被粘住不动为止（你将看到，这种情况是可能发生的）。因此，我们应定义一种结构，其中包含一个2进制位串(染色体)，以及一个与该 染色体相联系的适应性分数。我把这个结构称为SGenome结构，它的定义如下:struct SGenomevector vecBits;double dFitness;SGenome():dFitness(0)

38、SGenome(const int num_bits):dFitness(0)/创造随机二进制位串for (int i=0; inum_bits; +i)vecBits.push_back(RandInt(0,1);正如你能见到的那样，如果你在创建Sgenome对象时把一个整型数作为参数 传递给构造函数，则它就会自动创建一个以此整数为长度的随机2进制位串， 并将其适应性分数初始化为零，这样就把基因组什么都准备好了。程序注释std:vector 是 STL (Standard Templete Library)标准模板库的一部分， 这是一种为处理动态数组而预先建立好的类。如果要把数据加入STL中

39、，可使用 push_back()方法。下面是一个简单的例子：#include for (int i=0; i10; i+)MyFirstVector.push_back(i);cout endl MyFirstVectori;要清空一个向量，使用clear()方法：MyFirstVector.clear();你可利用size()方法来得到向量中元素的数目：NyFirstVector.size()就是这样。不需要你去考虑内存管理问题一std:vector能够为你来做所有这些！当需要 时，我会在整个程序中使用它。SGenome结构中不具备怎样为染色体（vecBits）进行译码的知识；这是需要 由遗

40、传算法类自己来完成的一项任务。现在让我们来快速窥视一下这个类的定义。 我已把它称作CgaBob类（有时我对我的原始创见自己也很吃惊，但我确实是这样 做的）。class CgaBobprivate:基因组群体vector m_vecGenomes群体的大小int m_iPopSizedouble m_dCrossoverRate;double m_dMutationRate;/每个染色体含有多少bitsint m_iChromoLength;每个基因有多少bitsint m_iGeneLength;int m_iFittestGenome;double m_dBestFitnessScore;d

41、ouble m_dTotalFitnessScore;int m_iGeneration;为map类创建一个实例CBobsMap m_BobsMap;/另一个CbobsMap对象用来保存每一代的最佳路径的一个记录，这是被访问小格的一个数组，它仅仅是为了显示目的而使用的。CBobsMap m_BobsBrain;让你知道运行是否仍在进行中bool m_bBusy;void Mutate(vector&vecBits);void Crossover(const vector&mum,const vector&dad,vector&baby1,vector&baby2);SGenome& Roule

42、tteWheel Selection();/用新的适应性分数来更新基因组原有的适应性分数，并计算群体的最高适应性分数和适应性分数最高的那个成员。void UpdateFitnessScores();把一个位向量译成为一个方向的(整数)向量vector Decode(const vector &bits);把一个位向量变换为十进制数。用于译码int BinToInt(const vector &v);创建一个随机的二进制位串的初始群体void CreateStartPopulation();public:CgaBob(double cross_rat,double mut_rat,int pop

43、_size,int num_bits,int gene_len):m_dCrossoverRate(cross_rat),m_dMutationRate(mut_rat),m_iPopSize(pop_size),m_iChromoLength(num_bits),m_dTotalFitnessScore(0.0),m_iGeneration(0),m_iGeneLength(gene_len), m_bBusy(false)CreateStartPopulation();void Run(HNND hwnd);void Epoch();void Render(int cxClient, in

44、t cyClient, HDC surface);/访问用的方法int Generation()return m_iGeneration;int GetFittest()return m_iFittestGenome;bool Started()return m_bBusy;void Stop()m_bBusy = false;由上你可看出，当这个类的一个实例被创建时，构造函数初始化所有的变量，并调用CreateStartPopulation()。这一短小函数创建了所需数量的基因组群体。每个基因组一开始包含的是一个由随机2进制位串组成的染色体，其适应性分数则 被设置为零。3.4.2 Epoch

45、(时代)遗传算法类中最烩灵人口的内容就是Epoch ()方法。这就是我们前面3.3节讲 过的遗传算法的那个循环。它是这个类的工作部门(workhorse)。这一方法与所 有工作或多或少都有连系。下面就让我们来更近距离地考察它.void CgaBob:epoch()UpdateFitnessScores();在每一个epoch循环内所要做的第一件事情，就是测试染色体群中每一个成 员的适应性分数。UpdateFitnessScores()是用来对每个基因组的二进制染色体 编码进行译码的函数，而由它再把译码所得到的一系列结果，也就是由代表东、 南、西、北四个方向的整数，发送给CBobsMap:Tes

46、tRoute。后者检查Bob在地 图中游走了多远，并根据Bob离开出口的最终距离，返回一个相应的适应性分数。 让我通过很少几行源码来告诉你怎样计算Bob的适应性分数：int DiffX = abs(posX - m_iEndX);int DiffY = abs(posY - m_iEndY);这里，DiffX和DiffY就是Bob所在格子相对于迷宫出口的水平和垂直偏离值。试考察图3.6的例子。灰色小格代表Bob通过迷宫的路程，上面写着B的小格是他 最终所到达的地方。在这一位置上，Diffx = 3，而DiffY = 0。图3.6 Bob尝试寻找迷宫出口这最后一行式子就是计算Bob的适应性分数。

47、它把DiffX与DiffY两个数字加起来 然后求倒数。DiffX与DiffY的和数中还加了一个1,这是为了确保除法不会出现一个分母 为零的错误，如果Bob到达出口，Diffx + DiffY = 0。UpdateFitnessScores也保持对每一代里适应分最高的基因组、以及与所有基因组相 关的适应性分数的跟踪。这些数值在执行轮盘赌选择时需要使用。到此，你已经知道了函数 UpdateFitnessScores。所做的全部工作，让我们回到Epoch函数的讨论.由于在每一个Epoch中都需要创建一个新的基因组群，因此，当它们在创建出来时(每 次2个基因组)，我们需要寻找一些地方来保存它们。/现在

48、创建一个新的群体int NewBabies = 0;为婴儿基因组创建存储器vector vecBabyGenomes;现在继续讨论遗传算法循环中所处理的各种事务。while (NewBabies m_iPopSize)/用轮盘赌法选择2个上辈(parents)SGenome mum = RouletteWheelSelection();SGenome dad = RouletteWheelSelection();在每次迭代过程中，我们需要选择2个基因组来作为2个新生婴儿的染色体的上辈。 我今后常喜欢把这2个上辈分别称为dad (父亲)和mum (母亲)因为他们将来就是要生 孩子的)。你应该回忆

49、得起来，一个基因组的适应性愈强，则由轮盘赌方法选择作为父母的 几率也愈大。杂交操作SGenome baby1, baby2;Crossover(mum.vecBits ,dad.vecBits, baby1.vecBits, baby2.vecBits);以上2行的工作是：创建2个空白基因组，这就是2个婴儿；它们与所选的上辈一起 传递给杂交函数Crossover()。这一函数执行了杂交(需要依赖于所设杂交率 m_dCrossoverRate来进行)，并把新的染色体的2进制位串存放到2个新生婴儿baby1和 baby2之中。/变异操作Mutate(baby1.vecBits);Mutate(ba

50、by2.vecBits);以上这2步是对婴儿实行突变！这听起来可怕，但这对他们是有利的。一个婴儿的位 的突变概率依赖于所选的参数m_dMutationRate (突变率)。/把2个新生因个婴儿加入新群体vecBabyGenomes.push_back(baby1);vecBabyGenomes.push_back(baby2);NewBabies += 2;这2个新生后代最终要加入到新的群体中，这样就完成了一次Loop的迭代过程。这 一过程需要不断重复，直到创建出来的后代总量和初始群体的大小相同。/把所有婴儿复制到初始群体m_vecGenomes = vecBabyGenomes;/代的计数加

51、1+m_iGeneration;这里，原有的那个群体由新生一代所组成的群体来代替，并把代的计数器加1,以跟踪 当前的代。就是这么一些了！呵呵，不难吧？这一 Epoch函数将无止境地重复，直到染色体收敛到了一个解，或到用户要求停止时 为止。下面我将会向你显示上述各种操作（算子）的代码，但在此首先让我们来聊聊，应该 如何确定使用的参数值我已把程序用到的所有参数存放在文件defines.h中了。这些参数中大多数将 是一目了然的，但有其中几个我想说明一下，即#define CROSSOVER_RATE 0.7#define MUTATION_RATE 0.001#define POP_SIZE 140

52、#define CHROMO_LENGTH 70。你可能想了解我是如何知道需要采用这些变量初值？这可是价值百万美元的 问题，因至今尚未有快速有效的规则能确定这些值，有的只是一些原则性的指导。而且， 选择这些值最终还得归结为每个人对遗传算法所得到的“感觉”，你只能通过自己 的编程实践、用各种不同的参数值进行调试、看结果会发生什么，并从中选取适合的 值。不同的问题需要不同的值，但是通常来说，如果你在使用二进制编码的染色体， 则把杂交率设定为O.7，变异率设为0.001,将是很好的初始缺省值。而确定群体大 小的一条有用规则是将基因组的数目取为染色体长度的2倍。因70表示Bob的35步的最大可能移动数

53、目，所以这里选择70作为染色 体的长度，它比Bob为穿越地图到达出口所需的步数还要多一些。当你学习了以后几 章的方法后可以使遗传算法变得更为有效，到时你就能将这个长度减少下来。历史的注释。遗传算法是John Holland大脑的产物，早在上个世纪60年代，他已提出 这种。想法。但不可思议的是，他没有感到需要在计算机上实际试验出结果，而宁 愿。利用笔和纸来作修修补补的工作！直到后来他的一名学生编写出程序并在 一台。个人计算机上运行后，才使人们终于看到在软件中利用他的思想能够得到什 么。3.4.4 算子函数(The Operator Functions)。我们现在从头到尾来考察一遍遗传算法的各种操

54、作(或称算子)函数一选择、 杂交、变异一的代码。尽管很简单，但与你一起通读一遍源码能给你重温一次这些函 数的机会。这可使你在了解遗传算法的知识时对它们具有更确切的认识。3.4.4.1重温轮盘赌选择(Roulette Whell Selection Revisited )让我们从轮盘赌选择算法开始。请记住，这一个函数的功能是从群体中选择 一个基因组，选中的几率正比于基因组的适应性分数。SGenome& CgaBob:RouletteWheelSelection()(double fSlice = RandFloat()*m_dTotalFitnessScore;。我们从零到整个适应分范围内随机选

55、取了一实数fSlice。我喜欢把此数看 作整个适应性分数饼图中的一块，如早先在图3.4中所示。但并不是其中一块，译 注double cfTotal = O;int SelectedGenome = 0;for (int i=O; i fSlice)(SelectedGenome = i;break;return m_vecGenomesSelectedGenome;。现在，程序通过循环来考察各基因组，把它们相应的适应性分数一个一个累 加起来，直到这一部分累加和大于fSlice值时，就返回该基因组。就是这样简单。3.4.4.2 重温杂交操作(Crossover Revisited)。这一函数要求

56、2个染色体在同一随机位置上断裂开，然后将它们在断开点以 后的部分进行互换，以形成2个新的染色体(子代)。void CgaBob:Crossover ( const vector&mum,const vector&dad,vector&baby1,vector&baby2)(这一函数共传入4个参数，参数传递均采用引用(reference )方式， 其中前2个传入父辈parent的染色体(别忘记，染色体只是一个整数型 的矢量std:vector)，后2个则是用来copy子代染色体的空矢量。if ( (RandFloat() m_dCrossoverRate) | (mum = dad)(babyl

57、 = mum;baby2 = dad;return;。这里，首先是进行检测，看mum和dad两个上辈是否需要进行杂交。杂交 发生的概率是由参数m_dCrossoverRate确定。如果不发生杂交，则2个上辈染色体 不作任何改变地就直接复制为子代，函数立即返回。int cp = RandInt(0, m_iChromoLength - 1)；。沿染色体的长度随机选择一个点来裂开染色体。for (int i=0; icp; i+)(baby1.push_back(mumi);baby2.push_back(dadi);for (i=cp; imum.size(); i+)(baby1.push_b

58、ack(dadi);baby2.push_back(mumi);。这两个小循环把2个parent染色体在杂交点(CP, crossover point ) 以后的所有位进行了互换，并把新的染色体赋给了 2个子代：babyl和baby2。3.4.4.3 重温变异操作(Mutation Revisited)。这一函数所做的工作，不过就是沿着一个染色体的长度，一 bit 一 bit地进 行考察，并按m_dMutationRate给定的几率，将其中某些bit实行翻转。void CgaBob:Mutate(vector &vecBits)(for (int curBit=0; curBitvecBits

59、.size(); curBit+)(/是否要翻转此bit?If (RandFloat() m_dMutationRate)(/是，就翻转此bitvecBitscurBit = !vecBitscurBit;/移到下一个bit。就是这些了。你的第一遗传算法程序也就这样完成了！下面让我花一些时间 来说明一下，当你在运行Pathfinder程序时，你能看到些什么3.4.5运彳亍找路径者程序(Running the PathfinderProgram).当你运行Pathfinder程序时，你将看到，程序不是每次都能找到一条通往出口的路径。Bob 有时会被粘住在一个局部地区不确定地逗来逗去，如同一个喝醉

60、了酒的人在试着寻找他的回家的 路。这主要由于群体太快地收敛到一个特殊类型的染色体。这样，由于群体中的成员变得如此相 似，crossover算子的有益效应这时实际上已经不能发挥作用，所有发生的事情都是靠总量很 少的变异操作在起作用。但因变异率设置很低，当染色体类型的差异消失后，仅仅依靠变异本 身已不足以去发现一个解。另外，由于轮盘赌选择的工作方式，使得任何一代的最合适的染色体 无法保证传到下一代。这意味着，只要在适当时候，立即杀死这个成员，遗传算法就能在群体 中找到一个几乎完全的解，但在这样做时，它将失去它所拥有的所有好的基因！在后面的章节中， 我将会谈到这些问题，并介绍一些技术来帮助维护基因组

61、的差异性且同时能保留那些较好的基 因组。但在这里，我首先需要花费一些时间来考察不同的编码方法，并考察它们怎样和你可能遇 到的问题类型关联在一起。这就是我在下一个章中将要做的事情。3.4.6二进制数转换问题的答案见第98页1. .110112. .213.5 练习题(Stuff to Try).从现在开始，在每一章的后面，我都要给你出一些点子，让你按照它来编写出相应的游戏 程序。我不强调这些程序本身有多么重要。但这是唯一能使你对那些算法产生“感性”认识的方法。 而且，当你开始去做复杂的题目时，这种“感性”认识将变得非常重要。1. 为杂交率，突变率，群体尺寸，染色体长度等参数设置各种不同的值来进行试验，观察它们 对算法的效率有什么影响？2. 试去掉杂交操作，而增加突变率，看会发生什么结果？如果单用杂交操作，而不利用突变， 又会发生什么？3. 修改适应性分数的计算函数，使多次进入同一小格的染色体得到惩罚。这应该导致更有效的 到出口的路径。4. 你能想到另外的什么办法使路径的寻找更为有效吗?这是遗传算法入门连载的最后一篇，将对连载来源进行一些说明。