2022年遗传算法入门 .pdf

《2022年遗传算法入门 .pdf》由会员分享，可在线阅读，更多相关《2022年遗传算法入门 .pdf（42页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

2、会和我一样，深深叹服于自然母亲的令人着迷！。从本质上说，任何生物机体不过就是一大堆细胞的集合。每个细胞都包含若干组相同的DNA 链，人们一般称之为染色体（chromosome ）。染色体中包含的DNA 分为两股，这两股 DNA链以螺旋状绞合在一起， 如下面图 3.1 所示那样，这就是我们所熟悉的DNA 双螺旋结构模型。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 42 页 - - - - - - - - - 图 3.1 . DNA 双螺旋结构。 单个染色体是由称作基因（

3、gene）的更小结构模块组成，而基因则又由称作核苷酸（nucleotide）的物质组成。核苷酸一共只有四种类型，即：腺嘌呤(thymine) 、鸟嘌呤 (adenine) 、胞嘧啶 (cytocine) 、 胸腺嘧啶 (guanine) 。 它们常简写为 T、A、C、 G（我不知道为什么？ .）。这些核苷酸相互连接起来， 形成若干很长的基因链， 而每个基因编码了生物机体的某种特征，如头发的颜色， 耳朵的样子， 等。一个基因可能具有的不同设置（如头发的黑色、 棕色或金黄色） ，称为等位基因（ allele），它们沿染色体纵向所处的物理部位称为基因的座位（locus）。 一个细胞中的染色体组（co

4、llection ）包含了复制该机体所需的全部信息。这就是克隆怎样实行的秘密。你可以从被克隆施主（donor ）身上，哪怕是一个血细胞中包含的信息，复制出整个生物机体， 例如一头羊。 新的羊将会在每一个方面和施主羊完全相同。染色体的这一集合就称为生物机体的基因组（ genome ）。在一特殊基因组中等位基因的一种状态称为该机体的遗传类型（ genotype ）。这些就是用来生成实际的生物机体 所谓表现型（ phenotype ） 本身的硬编码指令。你和我都是表现型。我们的DNA 携带了我们的遗传类型。如将这些术语用到其他领域中， 则，设计汽车用的成套蓝图就是一个遗传类型；在生产线上隆隆作响的成

5、品汽车就是一个表现型；只有设计被定型之前的，那些完全阵旧的设计，才勉强称得上是一个基因组。行了，行话说到此已经足够了。现在让我们讨论，怎样把所有这些应用到进化中去。如果你属于偶尔有机会离开计算机屏幕的那种人（因为我的朋友告诉我，我才知道外边还有一个世界呢！），你可能已经注意到，对于于千万万的动物和植物 小到只有在显微镜下才能看到的单细胞生物，大到从空间卫星上也能见到的巨大珊瑚礁 地球是它们共同的家， 不管它们的大小怎样、形状或颜色又怎样。 一个生物机体被认为取得了成功，如果它得到了配偶并生下了一个子名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -

6、 - - - - 名师精心整理 - - - - - - - 第 2 页，共 42 页 - - - - - - - - - 机体，而后者完全有希望来继续进一步复制自己。为了做到这一点，生物机体必须善长许多工作。例如，能寻找食物和水、能面对掠食者来保卫自己、能使自己吸引潜在的配偶，等。所有这些特长在某种程度上都和生物机体的遗传类型 生命的蓝图有关。生物机体的某些基因将会产生有助于它走向成功的属性，而另一些基因则可能要妨碍它取得成功。 一个生物的成功的量度就是它的适应性。生物机体愈能适应， 它的子孙后代也就愈多。下面转来讨论我们的关键部分. 。当两个生物机体配对和复制时，它们的染色体相互混合，产生一

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

8、性配偶的雄性中，眼睛的尺寸愈大，其获得成功的可能性也愈大。你可以说，动物的适应性正比于它的眼睛的直径。因此， 你就可以看到，从一个具有不同大小眼睛的雄性群体出发，当动物进化时，在同位基因中，能产生大眼睛雄性动物的基因，相对于产生小眼睛雄性动物的基因，就更有可能被复制到下一代。 由此可以推出，当进化几代之后， 大眼睛将会在雄性群体占据统治地位。过些时候，你就可以说，生物正在向一种特殊的遗传基因收敛。. ( 连载之二 ) . 扎自 第三章清华大学出版社(本章由 zzwu 译). 不过，有些读者可能已经会想到， 如果这是繁殖期生物机体内唯一发生的事情，那幺即使经历成千上万代后， 适应能力最强的成员的

9、眼睛也只能象初始群体中最大的眼睛一样大。而根据我们对自然界的观察中发现， 人类或动物的眼睛尺寸实际存在一代大于一代的趋势。之所以会发生这种情况， 是因为当基因传递给子孙后代的过程中，会有很小的概率发生差错， 从而使基因得到微小的改变。 这多少有点象中国古老的耳语传话游戏：在一队人中， 把一条消息一个接一名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 42 页 - - - - - - - - - 个地传递下去； 第一个人对着第二个人的耳朵轻声地讲述一个故事，第二个人再轻声地

10、把此故事传向第三个人，等，直到最后那个人再把听到的故事讲出来。通常这都会诺出很多笑话：最后一个人讲出来故事与第一个所讲的已是面目全非。其实，这种类型的差错在把信息从一个系统传递给另一系统时实际都会发生的。 图 3.2 显示的一列图画就是一个令人惊讶的例子。这是一次测试的结果：第一个人画出了一只鸟类的图(见左上角 ) 交给第二人，第二人看了以后自己重画一个给他的下一个人，这样重复下去，直到最后那个人画出来的图形就会被显著 异化。如果你有机会和十几个朋友聚集在一起， 我推荐你做一下这个小试验， 因为原始图画能有如此多变化似乎难以置信。有趣的事实.古代的硬币容易产生这种类型的信息丢失差错。早期厄尔利

11、凯尔特人和条顿人所使用的硬币大量地被假冒着；在早先的原始硬币上能找到一位皇帝的头像（那时已经在许多城市和乡镇用于支付）到后来则变成一匹马或一碗果子的形状了。你一眼就能看出当时使用的假冒货币，无需使用任何高科技的紫外线设备来探测！名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 42 页 - - - - - - - - - 图 3.2 信息移转的一个试验。 ( Thames 和 Hudson 提供的幻想图形 ) .你可以说，图形或故事的情节在从一个人到另一个人的传递过程中，已

12、经发生了变异（或突变， mutation ） ，同样的变异在生物繁衍过程中会在它们的基因中出现。发生变异的概率通常都很小，但经历大量世代之后变异就会显得很可观。一些变异对生物将是不利的（这有最大的可能） ，另一些则对生物的适应性可能没有任何影响，但也有一些则可能会给生物带来一些明显的利益， 使它能超过与其同类的生物。 在前面我们所讲的例子中， 你看到的能使动物引起眼睛直径变大的基因突变就是一种有利的突变，它将使该动物与群体其余动物相比，就好像一个超级的时髦模特儿那样显得突出。 这种使眼睛变得越来越大的趋势需要基因参与才能实现。当进化过程经历成千上万代之后，就会使动物长出一对如同盛菜的盘子那样大

13、的眼睛！见图3.3。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 42 页 - - - - - - - - - 图 3.3 一个 Adonis 的进化.进化机制除了能改进已具备的特征之外，也能产生各种各样全新特征。让我们再以眼睛的进化作为一个例子来说明吧。.可以设想，曾有一个时期动物就根本没有眼睛。那时，动物在它们的环境中航行完全是靠嗅觉和触觉来躲避掠食它们的动物。他们也 相当 擅长于这样做， 因为他们靠这样已经历了成千上万个世代。 在那个时候，鼻子大和手脚长的男性是受

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

15、和繁殖的机会。过了一段时间，由于进化机制的作用，许多动物的染色体中都会出现具有光敏皮肤细胞的基因。.现在，如果你再作一些外推，想象这一光敏细胞基因得到了进一步的有利突变，则你能看到，经过许多许多世代后，光敏细胞经过分化形成为一个区域；这个区域不断变大，产生出一些更为确定的特征，例如形成一个晶体，或产生能区别颜色的视觉细胞；还可以想象，一个突变使某个动物由一个光敏区域改变为两个光敏区域，由此就使那个动物有了立体视觉。立体视觉对一个生物体来说是一个巨大的进步，因为这能精确告诉他目标离开他有多远。当然，你也可以把会对眼睛产生不利影响的突变装入同样那些基因。但这里重要的一点是， 这样生长出来的后代将不

16、会和已具备改进型眼睛的堂表亲戚们那样取得成功，它们最终将会灭绝。 只有成功的基因才会得到继承。 你观察自然界中存在的任何特征就能发现，它们的进化都是利用无数微小的突变发展而来的，且它们都是对拥有者有利。难以置信吧？.这些重组和变异机制说明了进化怎么完成。我希望现在你已经理解， 有机体是怎么逐步形成各种不同类型的特征，以帮助它们在其生存环境中取得更大的成功。. . 遗传算法入门 . 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 42 页 - - - - - - - - -

17、 (连载之三) . 扎自第三章 清华大学出版社 ( 本章由 zzwu 译)3.2 二进制数速成 （A Quick Lesson in Binary Numbers）当进入更深层的学习之前，我必需确保你对二进制记数系统的理解。如果你已经知道二进制记数的工作原理，可以跳过这一小节。如果你还不了解，就让我来启发你 . 我认为了解二进制数（基为2 的数）的最容易的方法，就是首先查看一下十进制数：你为什么使用十进制数字（基为10 的数）和怎样使用十进制计数？人们通常相信，人类之所以采用基数为十的记数法来计数，是因为我们的双手共有十个手指的缘故。设想我们的一个祖先，不妨称他为Ug ，几十万年前在计算一个猛

18、犸群中猛犸的数字。 Ug 利用 2 个拳头来开始计算，当他每看到一个猛犸，就伸出一个手指；这样继续下去，直到他所有的手指都被用上为止；这样他就知道他已经算到10 个猛犸。但因猛犸群中包含的猛犸远远超过10 个， Ug 不得不再想一种方法来计算更大的数目。他狠抓了一下他的脑袋， 就产生了一个想法：叫他的一个朋友Frak 来帮忙。 Ug 想到用 Frak 的一个手指来代表他计算到的那10 个猛犸，然后他自己的手指就得到解脱，可重新开始用来计算第 11 、12 、13 个猛犸，等等，直到20 ，这时就需要使用Frak的另一个手指。你能看出，采用这样的过程， Ug 和 Frak 最多可以计算到110

19、个猛犸（那真是一桩了不起的奇观，不是吗？），但为了统计出更多的猛犸数目，他们就不得不去招募另一位朋友了。当人们最终学会了怎么写出数字时，就是使用类似方法来完成的。为了表示基数为 10 的数字，你创建一系列的列（columns），每一列代表人的一双手，例如: 1000位 100位10 位个位. 因此，要计数到15 ，你先在个位（列）由0 开始不断递增，直到9，然后，因个位已不能再增， 你就在 10 位记 1，并从新在个位由0 开始不断增加， 直到如下结束：1000位100 位10 位个位1 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -

20、- - - 名师精心整理 - - - - - - - 第 7 页，共 42 页 - - - - - - - - - 数字 15 由一个十位和5 个个位组成。（我知道，你听到这些会感到非常显然，但是这种详细的分析是必要的。）你能看到，二进制数系（或不管哪一种进制数系）都用同样的方式工作。但二进制计数时不用10 个数字，而只用2 个 译注：原文误为个，其中一个是 0，另一个是1。这样，当你在写2 进制数时，表示数的列（在2 进制数人们称作 bit ）的形式应为：16 8 4 2 个位现在你就可以来计算15。首先，你在个位（列）加1，得： 16 8 4 2 个位1 这时，因为你已经没有更大的数字可以

21、用了（请记住，2 进制数中最大的数是1），你必须增加个位左边的那个列，并将个位数从新变为0，因此数字2 的形式如下：16 8 4 2 个位1 0 数字 3 的形式为： 16 8 4 2 个位1 1 数字 4 的形式为： 16 8 4 2 个位1 0 0 等等，直到数字15 ：16 8 4 2 个位1 1 1 1 . . 这就是计算15 所要做的全部过程了。至此，你应该能够转换十进制数为二进制，或反过来， 把二进制转换为十进制了。我同时必须指出，二进制数字也常常写成一组有固定长度的位，特别当它与计算机联系起来讨论时如此。这就是为什么处理器常被说成是8 位、I6 位、 32 位、或 64 位的原因

22、。这意味，如果你要把15 写成 8 位的二进制，则你就要写成下面这样的形式，其中高位都是，但也要在前面写出来，以使整个长度达到：00001111名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 42 页 - - - - - - - - - 为了确保你理解这一概念，作为一个练习，在你继续进入下一节以前，试回答下列问题（答案附在本章最后）：1把十进制27 转换为二进制。2把二进制数10101转换为十进制。3把十进制数135 表示成为一个8 位的二进制数。一点不难吧？既然你对二进

23、制数有了一个初步概念，下面就让我们来讨论令人更加激动的内容吧. ( 连载之四 ) . 扎自 第三章清华大学出版社( 本章由 zzwu译)3.3 计算机内的进化（ Evolution Inside Your Computer ）. 。 遗传算法的工作过程本质上就是模拟生物的进化过程。首先，要规定一种编码方法，使得你的问题的任何一个潜在可行解都能表示成为一个“ 数字 ” 染色体。 然后，创建一个由随机的染色体组成的初始群体（每个染色体代表了一个不同的候选解），并在一段时期中，以培育适应性最强的个体的办法，让它们进化， 在此期间， 染色体的某些位置上要加入少量的变异。经过许多世代后，运气好一点，遗传

24、算法将会收敛到一个解。遗传算法不保证一定能得到解， 如果有解也不保证找到的是最优解，但只要采用的方法正确，你通常都能为遗传算法编出一个能够很好运行的程序。遗传算法的最大优点就是，你不需要知道怎么去解决一个问题 ; 你需要知道的仅仅是，用怎么的方式对可行解进行编码，使得它能能被遗传算法机制所利用。. 。通常，代表可行解的染色体采用一系列的二进制位作为编码。在运行开始时，你创建一个染色体的群体，每个染色体都是一组随机的进制位。进制位（即染色体）的长度在整个群体中都是一样的。作为一个例子，长度为 20的染色体的形状如下: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -

25、- - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 42 页 - - - - - - - - - .01010010100101001111 . 重要的事情就在于，每个染色体都用这样的方式编码成为由0 和 1 组成的字符串，而它们通过译码就能用来表示你手头问题的一个解。这可能是一个很差的解，也可能是一个十分完美的解， 但每一个单个的染色体都代表了一个可行解（下面就将讨论有关编码的更多的细节）。初始群体通常都是很糟的，有点象英国板球队或美国足球队（抱歉了！）。但不管怎样，正如我前面说过的那样，一个初始的群体已经创建完成（对这一例子，不妨设共有 100 个

26、成员），这样，你就可以开始做下面列出的一系列工作（你不用担心用粗体显示的那些词句，我后面马上就会来解释一切）：不断进行下列循环，直到寻找出一个解 : 1. 检查每个染色体，看它解决问题的性能怎样，并相应地为它分配一个适应性分数。2. 从当前群体中选出2 个成员。 被选出的概率正比于染色体的适应性，适应性分数愈高，被选中的可能性也就愈大。常用的方法就是采用所谓的轮盘赌选择法 (Roulette wheel selection )。3. . 按照预先设定的杂交率 （ Crossover Rate ），从每个选中染色体的一个随机的点上进行杂交（ crossover ）。4. 按照预定的变异率 （ m

27、utation rate ），通过对被选染色体的位的循环，把相应的位实行翻转（ flip ）。5. 重复步骤2，3，4，直到 100 个成员的新群体被创建出来。结束循环. 。以上算法中步骤1 到步骤 5 的一次循环称为一个代（或世代，generation）。而我把这整个的循环称作一个时代（epoch），在我的正文和代码中将始终都用这样方式来称呼。3.3.1 什么是轮盘赌选择？( Whats the Roulette Wheel Selection ) 。 轮盘赌选择是从染色体群体中选择一些成员的方法，被选中的机率和它们的适应性分数成比例， 染色体的适应性分数愈高，被选中的概率也愈多。这不保证适

28、应性分数最高的成员一定能选入下一代，仅仅说明它有最大的概率被选中。其工作过程是这样的：。 设想群体全体成员的适当性分数由一张饼图来代表(见图 3.4) ，这一饼图就和用于赌博的转轮形状一样。我们要为群体中每一染色体指定饼图中一个小块。块的大小与染色体的适应性分数成比例，适应性分数愈高，它在饼图中对应的小块所占面积也愈大。为了选取一个染色体，你要做的，就是旋转这个轮子，并把一个小球抛入其中，让它翻来翻去地跳名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 42 页 - -

29、- - - - - - - 动，直到轮盘停止时，看小球停止在哪一块上，就选中与它对应的那个染色体。本章后面我就会告诉你怎样来编写这种程序的准确算法。图 3.4染色体的轮盘赌式选择3.3.2 什么是杂交率？( Whats the Crossover Rate ) 。 杂交率就是用来确定2 个染色体进行局部的位（bit ）的互换以产生2 个新的子代的概率。实验表明这一数值通常取为0.7 左右是理想的，尽管某些问题领域可能需要更高一些或较低一些的值。每一次， 我们从群体中选择2 个染色体， 同时生成其值在0 到 1 之间一个随机数，然后根据此数据的值来确定两个染色体是否要进行杂交。如果数值低于杂交率

30、(O.7) 就进行杂交，然后你就沿着染色体的长度随机选择一个位置，并把此位置后面所有的位进行互换。例如，设给定的2 个染色体为 : .10001001110010010 .01010001001000011 。沿着它们的长度你随机选择一个位置，比如说 10 ， 然后互换第10 位之后所有位。这样两个染色体就变成了（我已在开始互换的位置加了一个空格）：.100010011 01000011 .010100010 10010010 3.3.3 什么是变异率？( Whats the Mutation Rate? ) 。 变异率（突变率）就是在一个染色体中将位实行翻转（flip ，即 0 变 1，1

31、变 0）的几率。这对于二进制编码的基因来说通常都是很低的值，比如 0.001 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 42 页 - - - - - - - - - 。 因此，无论你从群体中怎样选择染色体，你首先是检查是否要杂交，然后再从头到尾检查子代染色体的各个位，并按所规定的几率对其中的某些位实行突变（翻转）。3.3.4 咂！( Phew! ) 。 如果你对上面讲东西感到有些茫然，那也不必担心！从现在开始直到本章结束，所有阅读材料大多数都被设计用来重读两遍。

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

33、xecutable 文件中有一个预先制作好的执行程序，Pathfinder.exe。. (连载之五 ) . 扎自第三章清华大学出版社(本章由 zzwu 译)3.4 帮助 Bob 回家（ Helping Bob Home ）. 由于寻找路径问题被看成是游戏人工智能的一块神圣基石，我们下面就来创建一个遗传算法，用在一个非常简单的场景中解决寻找路径问题。为此，我们将创建一个迷宫，它的左边有一入口，右边有一出口， 并有一些障碍物散布在其中。 然后在出发点放置一个虚拟的人，我们叫名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理

34、 - - - - - - - 第 12 页，共 42 页 - - - - - - - - - 他鲍勃（ Bob ），然后要为他解决如何寻找路径的问题，使他能找到出口，并避免与所有障碍物相碰撞。下面我将说明怎样来产生Bob 的染色体的编码，但首先需要解释怎样来表示迷宫. . 迷宫是一个 2D 整数型数组；用0 来表示开放的空间， 1 代表墙壁或障碍物， 5 是起始点， 8 是出口。因此，整数数组 : . 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, .

35、 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,1,1,1,1,1,1,1,1,1,1,1,1,1,1 在屏幕上看起来将会有下面图3.5 的样子 : 图 3.5 Bob的迷宫，用红色标出了入口和出口作者已把这种地图设计方法封装在一个被称作CBob

36、sMap的类中，它定义为 : class CBobsMap private: /保存地图用的存储器 ( 一个 2 维整型数组 ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 42 页 - - - - - - - - - static const int mapMAP_HEIGHTMAP_WIDTH; static const int m_iMapWidth; /地图的宽度 static const int m_iMapHeight; /地图的高度 /起始点在数组中的

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

38、TestRoute(const vector &vecPath, CBobsMap &memory); /Render函数利用 Windows GDI在一个给定的 surface上显示地图 void Render(const int cxClient, const int cyClient, HDC surface); /画出能够存放于存储器中的不管什么样的路径 void MemoryRender(const int cxClient, const int cyClient. HDC surface); void ResetMemory(); ;.。.由上可以看出，我们只需要以常量的形式来保存

39、地图数组以及起点和终点的坐标就行了。这些名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 42 页 - - - - - - - - - 数据是在文件 CBobsMap.cpp 中定义的， 在光盘上你能找到它的相关的文件夹。除了存储迷宫的数据外， 这个 Map 类也用来记录 Bob 在迷宫中所走过的路程： memory。这对遗传算法本身而言不是本质的， 但为了显示目的， 使你能看到Bob怎样在迷宫中漫游， 设置一个记录是必需的。 这里重要的是成员函数TestRoute()，

40、它需要利用一系列的行进方向来检测Bob走了多远。这里我不准备花费时间来列出TestRoute 函数的清单，因为这是十分简单的那种函数，但要列出来却可能需要长长的2 页。我们只需要说明一下就行了。给出一个方向向量，它的每个分量能代表向北（ North）、向南（ South）、向东（ East）、向西（ West ）四个方向之一，让 Bob 按照它在地图中行走， TestRoute 计算 Bob 能到达的最远点的位置，然后返回一个适应性分数， 它正比于Bob最终位置离出口的距离。 他所到达的位置离开出口愈近，奖励给他的适应性分数也愈高。 如果他实际已到达了出口， 则我们就要向他表示祝贺了，他将得到

41、满分 1。这时循环就会自动结束，因为你已经找到一个解了，可以喊乌拉了！. 再有，不要因为理解不了这个类的任何一点而操心。我们下面马上就会开始讨论有关的每一件事情的。. ( 连载之六 ) . 扎自 第三章清华大学出版社( 本章由 zzwu译) 3.4.1为染色体编码（Ecoding the Chromosome）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 42 页 - - - - - - - - - 每个染色体必须把小人Bob 的每一个行动编入代码中。Bob 的行动仅

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

43、3,3,2,1,2,3,2,3,2,1,1,1 再把这些放进一个表格中，就可以使你相信这是一样的一些概念: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 42 页 - - - - - - - - - 二进制代码十进制译码代表的方向113West 113West 102East011South 102East113West 102East113West 102East011South 011South 011South 到此，你要做的全部就是将Bob 置于迷宫的起点，然

44、后告诉他根据这张表所列的方向一步步地走。如果按某一个方向前进将使Bob 碰到墙壁或障碍物，则只需忽略该方向并继续按下一个方向去走就行了。这样不断下去，直到所有方向用光或Bob 到达出口时为止。如果你想象有几百个这样的随机的染色体，你就能看到它们中的某些可能为Bob 译码出到达出口的一套方向（问题的一个解），但它们中的大多数将是失败的。遗传算法以随机的2 进制串（染色体）作为初始群体，测试它们每一个能让Bob 走到离开出口有多么接近，然后让其中最好的那些来孵化后代，期望它们的子孙中能有比Bob 走得离出口更近一点。这样继续下去，直到找出一个解，或直到Bob 绝望地在一个角落里被粘住不动为止（你将

45、看到，这种情况是可能发生的）。因此，我们应定义一种结构，其中包含一个进制位串（染色体），以及一个与该染色体相联系的适应性分数。我把这个结构称为SGenome 结构，它的定义如下 : struct SGenome 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 42 页 - - - - - - - - - vector vecBits; double dFitness; SGenome():dFitness(0) SGenome(const int num_bits):d

46、Fitness(0) /创造随机二进制位串 for (int i=0; inum_bits ; +i) vecBits.push_back(RandInt(0,1); ; 正如你能见到的那样，如果你在创建Sgenome 对象时把一个整型数作为参数传递给构造函数，则它就会自动创建一个以此整数为长度的随机进制位串，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 42 页 - - - - - - - - - 并将其适应性分数初始化为零，这样就把基因组什么都准备好了。程序注释

47、std:vector是 STL （Standard Templete Library）标准模板库的一部分 , 这是一种为处理动态数组而预先建立好的类。如果要把数据加入STL中, 可使用push_back() 方法。下面是一个简单的例子 : #include for (int i=0; i10; i+) MyFirstVector.push_back(i); cout endl MyFirstVectori; 要清空一个向量，使用clear()方法： MyFirstVector.clear();你可利用 size() 方法来得到向量中元素的数目：名师资料总结 - - -精品资料欢迎下载 - -

48、- - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 42 页 - - - - - - - - - NyFirstVector.size()就是这样。 不需要你去考虑内存管理问题std:vector能够为你来做所有这些！当需要 时，我会在整个程序中使用它。 SGenome 结构中不具备怎样为染色体（vecBits ）进行译码的知识 ; 这是需要 由遗传算法类自己来完成的一项任务。现在让我们来快速窥视一下这个类的定义。 我已把它称作 CgaBob类（有时我对我的原始创见自己也很吃惊，但我确实是这样 做的）。class CgaB

49、ob private: / 基因组群体vector m_vecGenomes / 群体的大小 int m_iPopSize double m_dCrossoverRate; double m_dMutationRate; / 每个染色体含有多少bits int m_iChromoLength; / 每个基因有多少 bits int m_iGeneLength; int m_iFittestGenome; double m_dBestFitnessScore; double m_dTotalFitnessScore; int m_iGeneration; 名师资料总结 - - -精品资料欢迎下载

50、 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 42 页 - - - - - - - - - / 为 map 类创建一个实例 CBobsMap m_BobsMap; / 另一个 CbobsMap 对象用来保存每一代的最佳路径的一个记/ 录，这是被访问小格的一个数组，它仅仅是为了显示目的而使用的。 CBobsMap m_BobsBrain; / 让你知道运行是否仍在进行中 bool m_bBusy; void Mutate(vector&vecBits); void Crossover(const vector