游戏编程中的人工智能技术弟三章.doc

游戏编程中的人工智能技术第三章 清华大学出版社 了解一些有关有生命的机体如何演化的知识，对理解遗传算法的演化机制是是有帮助的。本章的开始几页将扼要阐述自然演化的机制（通常称为“湿”演化算法），以及与之相关的术语。 生物只有经过许多世代的不断进化（evolution,演化），才能更好地完成生存与繁衍的任务。遗传算法也遵循同样的方式，需要随着时间的推移不断成长、演化，最后才能收敛，得到针对某类特定问题的一个或多个解。因此，了解一些有关有生命的机体如何演化的知识，对理解遗传算法的演化机制是是有帮助的。本章的开始几页将扼要阐述自然演化的机制（通常称为“湿”演化算法），以及与之相关的术语。即使你当年在中学里对生物并不擅长，也无须担心。本章不会涉及到过深的细节，但对于理解自然演化的基本机制已经足够。抛开以上不论，当你读完本章或下一章后，我想，你也会和我一样，深深叹服于自然母亲的令人着迷！ ?? 从本质上说，任何生物机体不过就是一大堆细胞的集合。每个细胞都包含若干组相同的DNA链，人们一般称之为染色体（chromosome）。染色体中包含的DNA分为两股，这两股DNA链以螺旋状绞合在一起，如下面图3.1所示那样，这就是我们所熟悉的DNA双螺旋结构模型。 图 3.1.. DNA双螺旋结构?? 单个染色体是由称作基因（gene）的更小结构模块组成，而基因则又由称作核苷酸（nucleotide）的物质组成。核苷酸一共只有四种类型，即：腺嘌呤(thymine)、鸟嘌呤(adenine)、胞嘧啶(cytocine)、胸腺嘧啶(guanine)。它们常简写为T、A、C、G（我不知道为什么？...一笑）。这些核苷酸相互连接起来，形成若干很长的基因链，而每个基因编码了生物机体的某种特征，如头发的颜色，耳朵的样子，等。一个基因可能具有的不同设置（如头发的黑色、棕色或金黄色），称为等位基因（allele），它们沿染色体纵向所处的物理部位称为基因的座位（locus）。 一个细胞中的染色体组（collection）包含了复制该机体所需的全部信息。这就是克隆怎样实行的秘密。你可以从被克隆施主（donor）身上，哪怕是一个血细胞中包含的信息，复制出整个生物机体，例如一头羊。新的羊将会在每一个方面和施主羊完全相同。染色体的这一集合就称为生物机体的基因组（genome）。在一特殊基因组中等位基因的一种状态称为该机体的遗传类型（genotype）。这些就是用来生成实际的生物机体? － 所谓表现型（phenotype） － 本身的硬编码指令。你和我都是表现型。我们的DNA携带了我们的遗传类型。如将这些术语用到其他领域中，则，设计汽车用的成套蓝图就是一个遗传类型；在生产线上隆隆作响的成品汽车就是一个表现型；只有设计被定型之前的，那些完全阵旧的设计，才勉强称得上是一个基因组。 行了，行话说到此已经足够了。现在让我们讨论，怎样把所有这些应用到进化中去。如果你属于偶尔有机会离开计算机屏幕的那种人（因为我的朋友告诉我，我才知道外边还有一个世界呢！），你可能已经注意到，对于于千万万的动物和植物 － 小到只有在显微镜下才能看到的单细胞生物，大到从空间卫星上也能见到的巨大珊瑚礁 － 地球是它们共同的家，不管它们的大小怎样、形状或颜色又怎样。一个生物机体被认为取得了成功，如果它得到了配偶并生下了一个子机体，而后者完全有希望来继续进一步复制自己。 为了做到这一点，生物机体必须善长许多工作。例如，能寻找食物和水、能面对掠食者来保卫自己、能使自己吸引潜在的配偶，等。所有这些特长在某种程度上都和生物机体的遗传类型 － 生命的蓝图有关。生物机体的某些基因将会产生有助于它走向成功的属性，而另一些基因则可能要妨碍它取得成功。一个生物的成功的量度就是它的适应性。生物机体愈能适应，它的子孙后代也就愈多。下面转来讨论我们的关键部分... 当两个生物机体配对和复制时，它们的染色体相互混合，产生一个由双方基因组成的全新的染色体组。这一过程就叫重组（recombination）或交叠（crossover,又译杂交,交叉,交换）。这样就意味，后代继承的可能大部分是上一代的优良基因，也可能继承了它们不少的不良基因。如果是前一种情况，后代就可能变得比它的父母更能成功（例如，它对掠食者有更强的自卫机制）；如为后一种情况，后代甚至就有可能不能再复制自己。这里要着重注意的是，愈能适应的子孙后代就愈有可能继续复制并将其基因传给下一个子孙后代。由此就会显示一种趋向，每一代总是比其父母一代生存和匹配得更完美。 作为它的一个很简捷的例子，我们设想，雌性动物仅仅吸引大眼睛的雄性。这样，在追求雌性配偶的雄性中，眼睛的尺寸愈大，其获得成功的可能性也愈大。你可以说，动物的适应性正比于它的眼睛的直径。因此，你就可以看到，从一个具有