01. 简介：生物遗传学背景

这是对《Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence》的笔记，本页对应第一章： Chapter 1： Introduction: The Biological Perspective.

本书可以在斯普林格购买纸质版或者电子版：https://link.springer.com/book/10.1007/3-540-32849-1

本章试图描述两个部分的内容：

1. 区分基因表达式编程和其他两个进化算法：遗传算法和遗传编程的不同。
   
2. 介绍有关遗传学的生物背景

GEP和GA、GP的不同：个体表示、基因型和表现型

对于遗传算法(GA)而言，其个体表示为定长的符号串。对于GA而言，其在基因层面上的操纵，即Genetic Operator的实现非常方便，但因此每个个体所承载的功能非常简单。
GP则是非线性的表示实体（一般为语法树），拥有不同的大小和形状。因此相比于GA，GP的个体可以更方便的使用高密度信息量的表示方法来承载复杂的功能，相对地，GP的Genetic Operator的设计要考虑的问题非常多。
在《自私的基因》一书中，查尔斯·道金斯认为生命的大爆炸（即以自然进化的方式实现涌现）需要突破两层阈值：

• Replicator Threshold
  简单来说即进化单元Replicator可以通过复制保留到下一代的方式来保存和传播它们的优秀的遗传信息(virtue of their own properties)。
  
• Phenotype Threshold
  表现型是实体面对环境作用时候的表现。潜在台词是个体携带的遗传信息与其面对环境时候的表现是不对称的：有可能实体面对环境的时候并不会表现出某些遗传信息；也有可能实体对环境的表现超过了遗传信息的描述。

GA和GP存在优秀遗传物质通过复制到下一代实现传播和扩散的过程（参见各自的Building Block Hypothesis和Schema Theory），因此通过了Replicator Threshold。但是，GA和GP都同时工作在基因型和表现型上，因此都没有通过Phenotype Threshold。
GP中的Developmental GP是一种为了让GP通过Phenotype Threshold的尝试：其中每五个比特会编码为一个符号，但是这种编码方式会产生相当多的非法表达式，由于非法表达式所占据的资源太多，DGP的性能提升并不强。

对于GEP而言，GEP是将非线性的表示实体通过编码转换为简单的定长线性符号串。在这个过程中，非线性的实体表示作为GEP的表现型，定长的线性符号串作为GEP的基因型。和DGP不同的是，GEP通过head/tails的设计来让chromosome产生的后代永远合法，不会因为语法不合规而丧失搜索能力。

生物遗传学

在生物进化中，DNA是遗传信息的载体，RNA是DNA复制的结果。RNA在及其模拟中并没有太大用处。

生物进化的载体

DNA

DNA由两条核苷酸长链构成，通过核苷酸长链上的四种碱基表示信息。DNA的这两条核苷酸长链的碱基对互补，因此单链和双链携带的遗传信息完全相同。双链结构在自然遗传系统中重要，但是对GEP和GA这样的信息系统而言不太重要。
DNA中的遗传信息存在两个层级的表示：

1. 核酸链
2. 双螺旋链：相比于第一层第二层级的遗传信息具有空间结构。

事实上，DNA分支会螺旋为随机的图形，但是DNA分支没有第三级遗传结构，因此无法实现更加复杂的空间结构来实现更加复杂的信息以维持细胞活动。因此，DNA适合存储遗传信息：基本元素的不同组合方式装有强大的遗传信息，但是没有催化活性和结构的多样性。

RNA

(m)RNA可以视为对DNA上一段特定序列的复制。mRNA的结构很单一，但是其分支中存在互补的短序列，如果这些互补的短序列相互碰撞，那么RNA自己会形成短双螺旋。被这些部分的核酸链在化学性质上被屏蔽，但是其他非折叠部分可以参与不同的化学反应，因此RNA具有存储信息和表现的不一致和表现的多样性。
RNA是一种可以同时承载基因型和表现型的分子，因此对于以RNA作为遗传物质的生物而言，任何对RNA的修改都会直接作用于其表现。
GP也是类似于RNA一样的系统由于所有对树的操作直接会被表现出来，因此大量的不合法操作会直接导致个体的不合法，从而让个体淘汰。或者需要在做遗传操作时验证树的合法性。

蛋白质

蛋白质是具有空间结构的氨基酸长链。每三个核酸表示一种氨基酸，同时每个氨基酸有不止一种编码（冗余的编码可以增加鲁棒性）。核酸编码读取需要从特定的三个核酸组合开始，以特定的三种核酸组合结束。
蛋白质折叠可以产生三维结构。蛋白质的空间结构和更多的基本表示单位（氨基酸）可以让蛋白质实现相当多的功能。

从上述过程中需要注意的几点：

• 从这个角度来看，GA就像是以RNA作为Replicator的遗传信息系统，GP像是以蛋白质为Replicator的信息系统。它们都是单遗传物质系统，这种系统的缺点是：任何的更改都会直接作用于个体的表现上。
  
• 在GEP中，任何与计算机系统无关的部分GEP都并未对其进行模拟，比如：双链结构、RNA的中介、复杂的翻译过程等等。

生物遗传信息的表达

真核生物的DNA上只有2%的基因与蛋白质相关，剩下的区域都是重复的基因区段或者是非编码的区段。
在基因的复制过程中，DNA会解螺旋，双链的两条链会各自被作为遗传物质使用。自然界的组织的多样性来自于基因型的结构调整(restructuring)。自然界中的结构调整包括：

• 突变
  DNA在由亲本向子代的复制过程中会出现不匹配。尽管基因有自我矫正机制（比如双链结构），但仍有一些错误没有被修正并传递给下一代。（也就是说，错误需要大到具有一定的鲁棒性不被修正才可以被传递给下一代）。不同组织中的突变概率是不同的。
  突变会导致四种结果：

  • 改变原有的密码子
  • 将密码子改变为终止密码子，进而让翻译提前结束
  • 新密码子和原密码子对应同一个氨基酸
  • 突变改变的是非编码区的基因

  另外一种突变是一些片段会插入或者从原有序列中删除（用于尝试新的关联关系-插入和检测原来关系的重要性-删除）如果这些操作的对象是小的核酸序列，那么结果取决于有没有改变基因编译的过程；如果操作对象改变的核酸序列大于了3个，那么这样的结果会引入或者删除更多的氨基酸。在改变编译过程的情况下，删除和插入类似于大规模点突变。

  突变对于蛋白质结构和功能的影响可能非常不同。插入和删除也有可能只对蛋白质的表达造成小规模影响。但是有时这种影响会增加蛋白质的功能效率，从而增加组织被选择的概率；在另外一方面，另一些突变改变了基因的编译框架或者是引起了较大规模的变化，这些突变对基因序列会有重大影响，如果这些影响下导致产生的蛋白质更利于组织的存活，那么则会产生新的性状。GEP模拟了突变这种对遗传物质改动“可大可小”的过程。

• 重组
  突变并不是唯一可以产生多样性的结构变化。在重组中，两个亲本的遗传物质片段进行组合，是两个亲本的遗传物质可以在同一个后代中出现。同源重组是发生在非姐妹染色单体之间，或者发生在同一个染色体的同源序列上的重组。基因的头尾不会发生交叉（即使发生交叉结果也不没有任何的变化）。
  对GEP而言，GEP的交叉是一种对位交叉，由于GEP的个体本身就是同源的，因此GEP的重组过程并不需要同源。尽管GEP的交叉过程看起来非常像同源重组，但是事实上并不是同源的。

• 易位(Transpose)
  生物学上并不是所有的基因都可以在基因型中从一个位置跳到另一个位置。
  易位的结果包括：

  • 扰乱原本的基因
  • 如果易位的对象是一个启动子，那么跳转后有可能将不表现的基因激活
    
  • 通过产生同源序列让染色体重构，这些同源序列可能会在之后的同源交叉中用到

  值得一提的是，这些发生易位的基因有时候甚至可以超过物种隔离。
  易位现象本身在自然界中非常常见，易位对染色体的影响非常大，大部分时候易位和非同源重组效果都是有害的，但是有时候也可以通过这个办法产生新的蛋白质序列。
  GEP中的易位只限定在同一个染色体当中，易位的对象是一个或者是一段基因，但是没有任何的特定限制。对于小范围的序列易位，发生易位的对象被复制到目标位置中，复制而不是删除的目的是此法可以创造出重复序列（个体中的重复序列对进化的影响可以参照Altenberg的The Evolution of Evolvability in Genetic Programming一文）；对于基因易位，发生易位后原来的基因会被直接删除。

• 基因复制
  自然界中基因有时候会被复制两次，这种复制在大多数时候是无害的：一方面这个基因对应地蛋白质需求量增大，另一方面是让同一个基因有不同的进化方向。
  GEP中没有为基因复制设置单独的operator，但是可以通过重组和易位联用来达到同样的效果。
  另外，GEP中观察到有重复基因出现的chromosome更容易被作为best individual。

• 转录
  自然界中遗传信息的表示发生在细胞质中，而DNA无法走出细胞核。因此将遗传信息从细胞核传递到细胞质中的任务交给mRNA进行，mRNA与DNA的一条单链进行配对，然后将遗传物质带入细胞质中。在信息系统中，mRNA作为中间介质的意义并不是特别的大。

• 翻译
  生物中翻译的过程是以mRNA作为模板，核糖体作为解码的场所，由tRNA进行组装氨基酸的过程。tRNA自身没有识别氨基酸的功能，但是其三维结构可以让特定的酶进行识别，由酶进行氨基酸的正确匹配。每个密码子后面还有一个额外的核酸用于描述蛋白质的结构。
  另外一种参与翻译的RNA是rRNA，rRNA的三维结构可以让其像酶一样参与化学反应。
  GEP中chromosome的翻译中，功能和基因型是一对一映射的。

• 译后修饰
  翻译结束时产生的蛋白质并不具有功能性，还需要对其进行折叠，产生空间结构。有些折叠后的蛋白质需要和其他蛋白质聚合才能发挥作用。蛋白质的聚合和折叠在基因中都有记录。
  GEP中的折叠表示为基因中elements距离的调整。

适应和进化

大部分蛋白质的效率差异并不大，但是少部分蛋白质会表现出对环境更加适应的性状。在进化中，特定组织存活的唯一方式就是留下后代。个体的后代后可能更加适应环境，更加适应环境的结果是采样率增加病缠身更多的后代。自然界的进化是不会停止的，因为环境永远都在变化。
但是在进化算法中，进化的环境，进化的目标是确定的，因此其进化是会停下的。进化算法中fitness表示个体被选择的概率，它是个体存活和繁殖的概率性度量。
自然界中选择因素是复杂的，fitness只能通过后代的数量进行衡量。但是信息系统中的fitness很容易衡量，再使用fitness进行选择。实验和理论分析说明轮盘赌对自然选择的模拟更好。由于fitness的目标在算法运行之前就已经被人类定好，因此个体的繁殖和选择都是为了解决人类问题而存在。

进化算法简述

GA

GA的表示是定长的二进制位串，原版中GA的遗传操作有交叉突变和倒位，现在倒位已经不常用。GA的表现型和基因型没有分开，个体的结构决定了个体的表现，结果是个体即是选择的对象也是operator改变的对象，任何的operator的作用会直接体现在选择结果上。在自然界中，选择只作用于表现型，与基因型无关。

GP

GP的语法树允许更多的表示能力，但是也是简单的replicator系统，选择和genetic opeartor都直接作用于个体。GA和GP个体表示的差异造成了modification和adaption的差异。GP允许个体的形状和大小不同，因此种群会进化出相当复杂的个体。 GP中genetic operator更像是数学变换而非自然进化的操作。

GEP

GEP中，各种性状的个体最终被统一编码为线性的chromosome，这一编码的过程创造了表现型和基因型。所有的genetic operator都发生在线性结构上。并且GEP的个体始终保持有效，因此搜索的diversity更广，不会因为非法而被赋予极高适应度从而被选择淘汰。