简单遗传算法入门

遗传算法入门 (连载之一) . 扎自<游戏编程中的人工智能技术>第三章 ． 清华大学出版社出版 生物只有经过许多世代的不断进化（evolution,演化），才能更好地完成生存与繁衍的任务。 遗传算法也遵循同样的方式，需要随着时间的推移不断成长、演化，最后才能收敛，得到针对某 类特定问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的一个或多个解。因此，了解一些有关有生命的机体如何演化的知识，对理解遗传算 法的演化机制是是有帮助的。本章的开始几页将扼要阐述自然演化的机制（通常称为“湿”演化算 法），以及与之相关的术语。即使你当年在中学里对生物并不擅长，也无须担心。本章不会涉及 到过深的细节，但对于理解自然演化的基本机制已经足够。抛开以上不论，当你读完本章或下一 章后，我想，你也会和我一样，深深叹服于自然母亲的令人着迷！ 。。从本质上说，任何生物机体不过就是一大堆细胞的集合。每个细胞都包含若干组相同的 DN A 链，人们一般称之为染色体（chromosome）。染色体中包含的 DNA 分为两股，这两股 DNA 链以螺旋状绞合在一起，如下面图 3.1 所示那样，这就是我们所熟悉的 DNA 双螺旋结构模型。 图 3.1.. DNA 双螺旋结构 。。单个染色体是由称作基因（gene）的更小结构模块组成，而基因则又由称作核苷酸（nucl eotide）的物质组成。核苷酸一共只有四种类型，即：腺嘌呤(thymine)、鸟嘌呤(adenine)、胞 嘧啶(cytocine)、胸腺嘧啶(guanine)。它们常简写为 T、A、C、G（我不知道为什么？...<一笑>）。 这些核苷酸相互连接起来，形成若干很长的基因链，而每个基因编码了生物机体的某种特征，如 头发的颜色，耳朵的样子，等。一个基因可能具有的不同设置（如头发的黑色、棕色或金黄色）， 称为等位基因（allele），它们沿染色体纵向所处的物理部位称为基因的座位（locus）。 。。一个细胞中的染色体组（collection）包含了复制该机体所需的全部信息。这就是克隆怎样 实行的秘密。你可以从被克隆施主（donor）身上，哪怕是一个血细胞中包含的信息，复制出整 个生物机体，例如一头羊。新的羊将会在每一个方面和施主羊完全相同。染色体的这一集合就称 为生物机体的基因组（genome）。在一特殊基因组中等位基因的一种状态称为该机体的遗传类 型（genotype）。这些就是用来生成实际的生物机体 － 所谓表现型（phenotype） － 本身 的硬编码指令。你和我都是表现型。我们的 DNA 携带了我们的遗传类型。如将这些术语用到其 他领域中，则，设计汽车用的成套蓝图就是一个遗传类型；在生产线上隆隆作响的成品汽车就是 一个表现型；只有设计被定型之前的，那些完全阵旧的设计，才勉强称得上是一个基因组。 。。行了，行话说到此已经足够了。现在让我们讨论，怎样把所有这些应用到进化中去。如果你 属于偶尔有机会离开计算机屏幕的那种人（因为我的朋友告诉我，我才知道外边还有一个世界 呢！），你可能已经注意到，对于于千万万的动物和植物 － 小到只有在显微镜下才能看到的单 细胞生物，大到从空间卫星上也能见到的巨大珊瑚礁 － 地球是它们共同的家，不管它们的大小 怎样、形状或颜色又怎样。一个生物机体被认为取得了成功，如果它得到了配偶并生下了一个子 机体，而后者完全有希望来继续进一步复制自己。 。。为了做到这一点，生物机体必须善长许多工作。例如，能寻找食物和水、能面对掠食者来保 卫自己、能使自己吸引潜在的配偶，等。所有这些特长在某种程度上都和生物机体的遗传类型 － 生命的蓝图有关。生物机体的某些基因将会产生有助于它走向成功的属性，而另一些基因则 可能要妨碍它取得成功。一个生物的成功的量度就是它的适应性。生物机体愈能适应，它的子孙 后代也就愈多。下面转来讨论我们的关键部分... 。。当两个生物机体配对和复制时，它们的染色体相互混合，产生一个由双方基因组成的全新的 染色体组。这一过程就叫重组（recombination）或交叠（crossover,又译杂交,交叉,交换）。这 样就意味，后代继承的可能大部分是上一代的优良基因，也可能继承了它们不少的不良基因。如 果是前一种情况，后代就可能变得比它的父母更能成功（例如，它对掠食者有更强的自卫机制）； 如为后一种情况，后代甚至就有可能不能再复制自己。这里要着重注意的是，愈能适应的子孙后 代就愈有可能继续复制并将其基因传给下一个子孙后代。由此就会显示一种趋向，每一代总是比 其父母一代生存和匹配得更完美。 。。作为它的一个很简捷的例子，我们设想，雌性动物仅仅吸引大眼睛的雄性。这样，在追求雌 性配偶的雄性中，眼睛的尺寸愈大，其获得成功的可能性也愈大。你可以说，动物的适应性正比 于它的眼睛的直径。因此，你就可以看到，从一个具有不同大小眼睛的雄性群体出发，当动物进 化时，在同位基因中，能产生大眼睛雄性动物的基因，相对于产生小眼睛雄性动物的基因，就更 有可能被复制到下一代。由此可以推出，当进化几代之后，大眼睛将会在雄性群体占据统治地位。 过些时候，你就可以说，生物正在向一种特殊的遗传基因收敛。 <遗传算法入门> . (连载之二) . 扎自<游戏编程中的人工智能技术>第三章 清华大学出版社 (本章由 zzwu 译) .......不过，有些读者可能已经会想到，如果这是繁殖期生物机体内唯一发生的事情，那幺 即使经历成千上万代后，适应能力最强的成员的眼睛也只能象初始群体中最大的眼睛一样大。而 根据我们对自然界的观察中发现，人类或动物的眼睛尺寸实际存在一代大于一代的趋势。之所以 会发生这种情况，是因为当基因传递给子孙后代的过程中，会有很小的概率发生差错，从而使基 因得到微小的改变。这多少有点象中国古老的耳语传话游戏：在一队人中，把一条消息一个接一 个地传递下去；第一个人对着第二个人的耳朵轻声地讲述一个故事，第二个人再轻声地把此故事 传向第三个人，等，直到最后那个人再把听到的故事讲出来。通常这都会诺出很多笑话：最后一 个人讲出来故事与第一个所讲的已是面目全非。其实，这种类型的差错在把信息从一个系统传递 给另一系统时实际都会发生的。图 3.2 显示的一列图画就是一个令人惊讶的例子。这是一次测试 的结果：第一个人画出了一只鸟类的图(见左上角) 交给第二人，第二人看了以后自己重画一个 给他的下一个人，这样重复下去，直到最后那个人画出来的图形就会被显著‘异化'。如果你有机 会和十几个朋友聚集在一起，我推荐你做一下这个小试验，因为原始图画能有如此多变化似乎难 以置信。 有趣的事实 .......古代的硬币容易产生这种类型的信息丢失差错。早期厄尔利凯尔特人和条顿人所使用的硬币 大量地被假冒着；在早先的原始硬币上能找到一位皇帝的头像（那时已经在许多城市和乡镇用 于支付）到后来则变成一匹马或一碗果子的形状了。你一眼就能看出当时使用的假冒货币，无 需使用任何高科技的紫外线设备来探测！ 图 3.2 信息移转的一个试验。 ( Thames 和 Hudson 提供的幻想图形 ) .......你可以说，图形或故事的情节在从一个人到另一个人的传递过程中，已经发生了变异 （或突变，mutation） ，同样的变异在生物繁衍过程中会在它们的基因中出现。发生变异的概 率通常都很小，但经历大量世代之后变异就会显得很可观。一些变异对生物将是不利的 （这有 最大的可能），另一些则对生物的适应性可能没有任何影响，但也有一些则可能会给生物带来一 些明显的利益，使它能超过与其同类的生物。在前面我们所讲的例子中，你看到的能使动物引起 眼睛直径变大的基因突变就是一种有利的突变，它将使该动物与群体其余动物相比，就好像一个 超级的时髦模特儿那样显得突出。这种使眼睛变得越来越大的趋势需要基因参与才能实现。当进 化过程经历成千上万代之后，就会使动物长出一对如同盛菜的盘子那样大的眼睛！见图 3.3。 图 3.3 一个 Adonis 的进化 .......进化机制除了能改进已具备的特征之外，也能产生各种各样全新特征。让我们再以眼 睛的进化作为一个例子来说明吧。 .......可以设想，曾有一个时期动物就根本没有眼睛。那时，动物在它们的环境中航行完全 是靠嗅觉和触觉来躲避掠食它们的动物。他们也 相当 擅长于这样做，因为他们靠这样已经历了 成千上万个世代。在那个时候，鼻子大和手脚长的男性是受女孩子们欢迎的。然而，突然有一天， 当两个动物配对时，一个基因突变发生在为皮肤细胞提供的蓝图上。这一突变使其后代在他们的 头上发育出了一个具有相当光敏效应的细胞，使其后代能足够识别周围环境是亮的还是暗的。这 样就给他带来了一个微小的优点，因为，如果一种食肉动物，比如一只鹰，来到了某个范围以内， 则它将阻挡了光线，这时，该动物就会感觉得到，就可迅速跑到隐蔽的地方去躲藏起来。另外， 这种皮肤细胞还能指示现在是晚上或白天，或告诉他现在是在地面之上或地面之下，这些信息在 捕食和吸取营养时都能为它提供方便。你能看到这一新型皮肤细胞将使这一动物与群体中其余的 动物相比，具备了稍多的优点，并因此也就有更多的生存和繁殖的机会。过了一段时间，由于进 化机制的作用，许多动物的染色体中都会出现具有光敏皮肤细胞的基因。 .......现在，如果你再作一些外推，想象这一光敏细胞基因得到了进一步的有利突变，则你 能看到，经过许多许多世代后，光敏细胞经过分化形成为一个区域；这个区域不断变大，产生出 一些更为确定的特征，例如形成一个晶体，或产生能区别颜色的视觉细胞；还可以想象，一个突 变使某个动物由一个光敏区域改变为两个光敏区域，由此就使那个动物有了立体视觉。立体视觉 对一个生物体来说是一个巨大的进步，因为这能精确告诉他目标离开他有多远。当然，你也可以 把会对眼睛产生不利影响的突变装入同样那些基因。但这里重要的一点是，这样生长出来的后代 将不会和已具备改进型眼睛的堂表亲戚们那样取得成功，它们最终将会灭绝。只有成功的基因才 会得到继承。你观察自然界中存在的任何特征就能发现，它们的进化都是利用无数微小的突变发 展而来的，且它们都是对拥有者有利。难以置信吧？ .......这些重组和变异机制说明了进化怎么完成。我希望现在你已经理解，有机体是怎么逐步形成 各种不同类型的特征，以帮助它们在其生存环境中取得更大的成功。 . ..遗传算法入门.. . (连载之三) . 扎自<游戏编程中的人工智能技术>第三章 清华大学出版社 (本章由 zzwu 译) 3.2 二进制数速成 （A Quick Lesson in Binary Numbers） 当进入更深层的学习之前，我必需确保你对二进制记数系统的理解。如果你已经 知道二进制记数的工作原理，可以跳过这一小节。如果你还不了解，就让我来启发你... 我认为了解二进制数（基为 2 的数）的最容易的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ，就是首先查看一下十进制 数：你为什么使用十进制数字（基为 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 位 个位 1 5 数字 15 由一个十位和 5 个个位组成。（我知道，你听到这些会感到非常显然， 但是这种详细的 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 是必要的。）你能看到，二进制数系（或不管哪一种进制数系）都用同 样的方式工作。但二进制计数时不用 10 个数字，而只用 2 个［译注：原文误为１个］，其 中一个是 0，另一个是 1。这样，当你在写 2 进制数时，表示数的列（在 2 进制数人们称作 ‘bit'）的形式应为： 16 8 4 2 个位 现在你就可以来计算 15。首先，你在个位（列）加 1，得： 16 8 4 2 个位 1 这时，因为你已经没有更大的数字可以用了（请记住，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 位的原因。这意味，如果你要把 15 写成 8 位的二进制，则你就要写 成下面这样的形式，其中高位都是０，但也要在前面写出来，以使整个长度达到８： 00001111 为了确保你理解这一概念，作为一个练习，在你继续进入下一节以前，试回答下列问 题（答案附在本章最后）： 1．把十进制 27 转换为二进制。 2．把二进制数 10101 转换为十进制。 3．把十进制数 135 表示成为一个 8 位的二进制数。 一点不难吧？既然你对二进制数有了一个初步概念，下面就让我们来讨论令人更加激 动的内容吧 <遗传算法入门> . (连载之四) . 扎自<游戏编程中的人工智能技术>第三章 清华大学出版社 (本章由 zzwu 译) 3.3 计算机内的进化 （ Evolution Inside Your Computer ） ..。遗传算法的工作过程本质上就是模拟生物的进化过程。首先，要规定一种编码方法， 使得你的问题的任何一个潜在可行解都能表示成为一个“数字”染色体。然后，创建一个由随 机的染色体组成的初始群体（每个染色体代表了一个不同的候选解），并在一段时期中，以 培育适应性最强的个体的办法，让它们进化，在此期间，染色体的某些位置上要加入少量的 变异。经过许多世代后，运气好一点，遗传算法将会收敛到一个解。遗传算法不保证一定能 得到解，如果有解也不保证找到的是最优解，但只要采用的方法正确，你通常都能为遗传算 法编出一个能够很好运行的程序。遗传算法的最大优点就是， 你不需要知道怎么去解决一 个问题; 你需要知道的仅仅是，用怎么的方式对可行解进行编码，使得它能能被遗传算法机 制所利用。 ..。通常，代表可行解的染色体采用一系列的二进制位作为编码。在运行开始时，你创 建一个染色体的群体，每个染色体都是一组随机的２进制位。２进制位（即染色体）的长度 在整个群体中都是一样的。作为一个例子，长度为 20 的染色体的形状如下: .........................01010010100101001111 ....重要的事情就在于，每个染色体都用这样的方式编码成为由 0 和 1 组成的字符串， 而它们通过 译码 就能用来表示你手头问题的一个解。这可能是一个很差的解，也可能是一 个十分完美的解，但每一个单个的染色体都代表了一个可行解（下面就将讨论有关编码的更 多的细节）。初始群体通常都是 很糟的 ，有点象英国板球队或美国足球队（抱歉了！）。 但不管怎样，正如我前面说过的那样，一个初始的群体已经创建完成（对这一例子，不妨设 共有 100 个成员），这样，你就可以开始做下面列出的一系列工作（你不用担心用粗体显 示的那些词句，我后面马上就会来解释一切）： 不断进行下列循环，直到寻找出一个解 : 1.检查每个染色体，看它解决问题的性能怎样，并相应地为它分配一个适应性分数。 2. 从当前群体中选出 2 个成员。被选出的概率正比于染色体的适应性，适应性分数愈 高，被选中的可能性也就愈大。常用的方法就是采用所谓的 轮盘赌选择法 (Roulette wh eel selection )。 3. .按照预先设定的 杂交率（Crossover Rate ），从每个选中染色体的一个随机的点上 进行杂交（crossover ）。 4. 按照预定的 变异率（ mutation rate ），通过对被选染色体的位的循环，把相应的位 实行翻转（ flip ）。 5. 重复步骤 2，3，4，直到 100 个成员的新群体被创建出来。 结束循环 ....。以上算法中步骤 1 到步骤 5 的一次循环称为一个代（或世代，generation）。而我 把这整个的循环称作一个时代（epoch），在我的正文和代码中将始终都用这样方式来称 呼。 3.3.1 什么是轮盘赌选择？ ( What's the Roulette Wheel Selection ) 。。轮盘赌选择是从染色体群体中选择一些成员的方法，被选中的机率和它们的适应 性分数成比例，染色体的适应性分数愈高，被选中的概率也愈多。这不保证适应性分数最高 的成员一定能选入下一代，仅仅说明它有最大的概率被选中。其工作过程是这样的： 。。设想群体全体成员的适当性分数由一张饼图来代表 (见图 3.4)，这一饼图就和用 于赌博的转轮形状一样。我们要为群体中每一染色体指定饼图中一个小块。块的大小与染色 体的适应性分数成比例，适应性分数愈高，它在饼图中对应的小块所占面积也愈大。为了选 取一个染色体，你要做的，就是旋转这个轮子，并把一个小球抛入其中，让它翻来翻去地跳 yang.j 铅笔 yang.j 铅笔 yang.j 铅笔 yang.j 铅笔 yang.j 铅笔 yang.j 铅笔 动，直到轮盘停止时，看小球停止在哪一块上，就选中与它对应的那个染色体。本章后面我 就会告诉你怎样来编写这种程序的准确算法。 图 3.4 染色体的轮盘赌式选择 3.3.2 什么是杂交率？( What's the Crossover Rate ) 。。杂交率就是用来确定 2 个染色体进行局部的位（bit）的互换以产生 2 个新的子 代的概率。 实验表明这一数值通常取为 0.7 左右是理想的，尽管某些问题领域可能需要更 高一些或较低一些的值。 。。每一次，我们从群体中选择 2 个染色体，同时生成其值在 0 到 1 之间一个随机数， 然后根据此数据的值来确定两个染色体是否要进行杂交。如果数值低于杂交率(O.7)就进行 杂交，然后你就沿着染色体的长度随机选择一个位置，并把此位置后面所有的位进行互换。 例如，设给定的 2 个染色体为: .........................10001001110010010 .........................01010001001000011 。。沿着它们的长度你随机选择一个位置，比如说 10，然后互换第 10 位之后所有位。 这样两个染色体就变成了（我已在开始互换的位置加了一个空格）： .........................100010011 01000011 .........................010100010 10010010 3.3.3 什么是变异率？( What's the Mutation Rate? ) 。。变异率（突变率）就是在一个染色体中将位实行翻转（flip，即 0 变 1，1 变 0） 的几率。这对于二进制编码的基因来说通常都是很低的值，比如 0.001 。 yang.j 高亮 。。因此，无论你从群体中怎样选择染色体，你首先是检查是否要杂交，然后再从头 到尾检查子代染色体的各个位，并按所规定的几率对其中的某些位实行突变（翻转）。 3.3.4 咂！( Phew! ) 。。如果你对上面讲东西感到有些茫然，那也不必担心！从现在开始直到本章结束， 所有阅读 材料 关于××同志的政审材料调查表环保先进个人材料国家普通话测试材料农民专业合作社注销四查四问剖析材料 大多数都被设计用来重读两遍。这里有很多需要你理解的新概念，且它们都是 相互混杂在一起。我相信对于你这是最好的学习方法。当你通读第一遍时，你有望对一些基 本概念得到一些孤立的感性认识，而在阅读第二遍时（如果做我的工作是正确的话），你就 能看到各种不同的概念怎样相互联系起来。而当你最后结合源程序来开始编程玩弄时，每一 件事物都只是考虑怎样周密地进行安排的问题，到那时你的工作仅仅是一种如何来提炼你的 知识和技能的事了（那是比较容易的一部分）。 注意 。。在本 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 所附的光盘的 Chaper3/Pathfinder 文件夹中，你能找到 Pathfinder 工程的全部源码。 。。如果你想在进一步阅读课文之前窥视一下工程的全貌，在 Chaper3/Executable 文件中有一个预先制作好的执行程序， Pathfinder.exe。 <遗传算法入门> . (连载之五) . 扎自<游戏编程中的人工智能技术>第三章 清华大学出版社 (本章由 zzwu 译) 3.4 帮助 Bob 回家（ Helping Bob Home ） ....由于寻找路径问题被看成是游戏人工智能的一块神圣基石，我们下面就来创建一个遗传 算法，用在一个非常简单的场景中解决寻找路径问题。为此，我们将创建一个迷宫，它的左边有 一入口，右边有一出口，并有一些障碍物散布在其中。然后在出发点放置一个虚拟的人，我们叫 他鲍勃（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, ..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 的迷宫，用红色标出了入口和出口 作者已把这种地图设计方法封装在一个被称作 CBobsMap 的类中，它定义为: class CBobsMap { private: //保存地图用的存储器 (一个 2维整型数组) static const int map[MAP_HEIGHT][MAP_WIDTH]; static const int m_iMapWidth; //地图的宽度 static const int m_iMapHeight; //地图的高度 //起始点在数组中的下标 static const int m_iStartX; static const int m_iStartY; //终点的数组下标 static const int m_iEndX; static const int m_iEndY; public: //你可以利用这一数组作为 Bob 存储器，如果需要的话 int memory[MAP_HEIGHT][MAP_WIDTH]; CBobsMap() { ResetMemory(); } //利用一个字符串来记录 Bob行进的方向，其中每一个字符代表 //Bob所走的一步；检查 Bob离开出口还有多远； //返回一个与到达出口距离成正比的适应性分数 double 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(); }; ...。 .由上可以看出，我们只需要以常量的形式来保存地图数组以及起点和终点的坐标就行了。这些 数据是在文件 CBobsMap.cpp 中定义的，在光盘上你能找到它的相关的文件夹。除了存储迷宫 的数据外，这个 Map 类也用来记录 Bob 在迷宫中所走过的路程： memory[][] 。这对遗传算 法本身而言不是本质的，但为了显示目的，使你能看到 Bob 怎样在迷宫中漫游，设置一个记录 是必需的。这里重要的是成员函数 TestRoute()，它需要利用一系列的行进方向来检测 Bob 走了多远。这里我不准备花费时间来列出 TestRoute 函数的清单，因为这是十分简单的那种函 数，但要列出来却可能需要长长的 2 页。我们只需要说明一下就行了。给出一个方向向量，它 的每个分量能代表向北（North）、向南（South）、向东（East）、向西（West）四个方向之 一，让 Bob 按照它在地图中行走， TestRoute 计算 Bob 能到达的最远点的位置，然后返回 一个适应性分数，它正比于 Bob 最终位置离出口的距离。他所到达的位置离开出口愈近，奖励 给他的适应性分数也愈高。如果他实际已到达了出口，则我们就要向他表示祝贺了，他将得到满 分 1。这时循环就会自动结束，因为你已经找到一个解了，可以喊乌拉了！ ....再有，不要因为理解不了这个类的任何一点而操心。我们下面马上就会开始讨论有关的每一 件事情的。 <遗传算法入门> . (连载之六) . 扎自<游戏编程中的人工智能技术>第三章 清华大学出版社 (本章由 zzwu 译) 3.4.1 为染色体编码 （Ecoding the Chromosome） 每个染色体必须把小人 Bob 的每一个行动编入代码中。Bob 的行动仅限为 4 个方向： 向东(East)，向南(South)，向西(West)，向北(North) 故编码后的染色体应该就是代表这 4 个方向信息的一个字符串。传统的编码方法就是把方 向变换成二进制的代码。四个方向只要 2 位就够了，例如下表所示的那样： 二进制代码 十进制译码 代表的方向 00 0 向北 01 1 向南 10 2 向东 11 3 向西 这样，如果你得到了一个随机的二进制字符串，你就能将它译码出 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 再把这些放进一个表格中，就可以使你相信这是一样的一些概念: 二进制代码 十进制译码 代表的方向 11 3 West 11 3 West 10 2 East 01 1 South 10 2 East 11 3 West 10 2 East 11 3 West 10 2 East 01 1 South 01 1 South 01 1 South 到此，你要做的全部就是将 Bob 置于迷宫的起点，然后告诉他根据这张表所列的方向 一步步地走。如果按某一个方向前进将使 Bob 碰到墙壁或障碍物，则只需忽略该方向并继 续按下一个方向去走就行了。这样不断下去，直到所有方向用光或 Bob 到达出口时为止。 如果你想象有几百个这样的随机的染色体，你就能看到它们中的某些可能为 Bob 译码 出到达出口的一套方向（问题的一个解），但它们中的大多数将是失败的。 遗传算法以随机的 2 进制串（染色体）作为初始群体，测试它们每一个能让 Bob 走到 离开出口有多么接近，然后让其中最好的那些来孵化后代，期望它们的子孙中能有比 Bob 走得离出口更近一点。这样继续下去，直到找出一个解，或直到 Bob 绝望地在一个角落里 被粘住不动为止（你将看到，这种情况是可能发生的）。 因此，我们应定义一种结构，其中包含一个２进制位串（染色体），以及一个与该 染色体相联系的适应性分数。我把这个结构称为 SGenome 结构，它的定义如下: struct SGenome { vector vecBits; double dFitness; SGenome():dFitness(0){} SGenome(const int num_bits):dFitness(0) { //创造随机二进制位串 for (int i=0; i for (int i=0; i<10; i++) { MyFirstVector.push_back(i); cout << endl << MyFirstVector[i]; } 要清空一个向量，使用 clear()方法： MyFirstVector.clear(); 你可利用 size()方法来得到向量中元素的数目： NyFirstVector.size() 就是这样。 不需要你去考虑内存管理问题－std::vector 能够为你来做所有这些！当需要 时，我会在整个程序中使用它。 SGenome 结构中不具备怎样为染色体（vecBits）进行译码的知识; 这是需要 由遗传算法类自己来完成的一项任务。现在让我们来快速窥视一下这个类的定义。 我已把它称作 CgaBob 类（有时我对我的原始创见自己也很吃惊，但我确实是这样 做的）。 class CgaBob { 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; //为 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& RouletteWheel 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_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, int 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 （时代） 遗传算法类中最烩灵人口的内容就是 Epoch()方法。这就是我们前面 3.3 节讲 过的遗传算法的那个循环。它是这个类的工作部门（workhorse）。这一方法与所 有工作或多或少都有连系。下面就让我们来更近距离地考察它 ... void CgaBob::epoch() { UpdateFitnessScores(); 在每一个 epoch 循环内所要做的第一件事情，就是测试染色体群中每一个成 员的适应性分数。 UpdateFitnessScores() 是用来对每个基因组的二进制染色体 编码进行译码的函数，而由它再把译码所得到的一系列结果，也就是由代表东、 南、西、北四个方向的整数，发送给 CBobsMap::TestRoute 。后者检查 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 的适应性分数。它把 DiffX 与 DiffY 两个数字加 起来然后求倒数。 DiffX 与 DiffY 的和数中还加了一个１，这是为了确保除法不会出现一个分母为零的错误， 如果 Bob 到达出口，Diffx + DiffY = 0。 UpdateFitnessScores 也保持对每一代里适应分最高的基因组、以及与所有基 因组相关的适应 性分数的跟踪。这些数值在执行轮盘赌选择时需要使用。到此，你已经知道了函数 UpdateFitnessScores() 所做的全部工作，让我们回到 Epoch 函数的讨论 ... 由于在每一个 Epoch 中都需要创建一个新的基因组群，因此，当它们在创建出来 时(每次２个基 因组)，我们需要寻找一些地方来保存它们。 //现在创建一个新的群体 int NewBabies = 0; //为婴儿基因组创建存储器 vector vecBabyGenomes; 现在继续讨论遗传算法循环中所处理的各种事务。 while (NewBabies < m_iPopSize) { //用轮盘赌法选择 2 个上辈（parents） SGenome mum = RouletteWheelSelection(); SGenome dad = RouletteWheelSelection(); 在每次迭代过程中，我们需要选择 2 个基因组来作为 2 个新生婴儿的染色体 的上辈。我今 后常喜欢把这２个上辈分别称为 dad （父亲）和 mum （母亲）因为他们将来就是要生 孩子的）。 你应该回忆得起来，一个基因组的适应性愈强，则由轮盘赌方法选择作为父母的几率也愈大。 //杂交操作 SGenome baby1, baby2; Crossover(mum.vecBits ,dad.vecBits, baby1.vecBits, baby2.vecBits); 以上２行的工作是：创建 2 个空白基因组，这就是２个婴儿；它们与所选的上 辈一起传递给杂 交函数 Crossover() 。这一函数执行了杂交（需要依赖于所设杂交率 m_dCrossoverRa te 来进行）， 并把新的染色体的２进制位串存放到２个新生婴儿 baby1 和 baby2 之中。 // 变异操作 Mutate(baby1.vecBits); Mutate(baby2.vecBits); 以上这 2 步是对婴儿实行突变！这听起来可怕，但这对他们是有利的。一个婴 儿的位的突变概率 依赖于所选的参数 m_dMutationRate（突变率）。 // 把２个新生因个婴儿加入新群体 vecBabyGenomes.push_back(baby1); vecBabyGenomes.push_back(baby2); NewBabies += 2; } 这 2 个新生后代最终要加入到新的群体中，这样就完成了一次 Loop 的迭代过 程。这一过程需要不 断重复，直到创建出来的后代总量和初始群体的大小相同。 // 把所有婴儿复制到初始群体 m_vecGenomes = vecBabyGenomes; // 代的计数加１ ++m_iGeneration; } 这里，原有的那个群体由新生一代所组成的群体来代替，并把代的计数器加１， 以跟踪当前的代。 就是这么一些了！呵呵，不难吧？ 这一 Epoch 函数将无止境地重复，直到染色体收敛到了一个解，或到用户要求停止 时为止。下面我 将会向你显示上述各种操作（算子）的代码，但在此首先让我们来聊聊，应该如何确定使用 的参数值。 <遗传算法入门> . (连载之八) . 扎自<游戏编程中的人工智能技术>第三章 清华大学出版社 我已把程序用到的所有参数存放在文件 defines.h 中了。这些参数中大多数将是 一目了然的，但有其中几个我想说明一下，即 #define CROSSOVER_RATE 0.7 #define MUTATION_RATE 0.001 #define POP_SIZE 140 #define CHROMO_LENGTH 70 你可能想了解我是如何知道需要采用这些变量初值？这可是价值百万美元的问题， 因至今尚未有快速有效的规则能确定这些值，有的只是一些原则性的指导。而且，选 择这些值最终还得归结为每个人对遗传算法所得到的“感觉”，你只能通过自己的编 程实践、用各种不同的参数值进行调试、看结果会发生什么，并从中选取适合的值。 不同的问题需要不同的值，但是通常来说，如果你在使用二进制编码的染色体，则把 杂交率设定为 O.7，变异率设为 0.001，将是很好的初始缺省值。而确定群体大小的一 条有用规则是将基因组的数目取为染色体长度的２倍。 因 70 表示 Bob 的 3