1.基因表达式编程起源
    基因表达式编程(Gene Expression Programming,GEP)是一种全新的进化算法，它是葡萄牙科学家Candida Ferreira于2000年提出来的。随后Candida Ferreira注册了公司www.gene-expression-programming.com，专门研究有关GEP在函数发现、分类、时间序列分析等方面的工作，已经取得了一定的成果，并形成了具有自主知识产权的GEP软件GepSoft。GEP起源于生物学领域，它继承了传统的遗传算法和遗传编程的优点，在此基础上发展了属于GEP特有的遗传操作，大量的实验表明，GEP算法以及各种改进的GEP算法在发现未知先验知识的数据函数关系以及对时间序列分析都有着非常好的表现。

    2.GEP、GA和GP比较
    GEP、GA以及GP都属于进化计算家族的分支，所以它们之间既有联系又有区别，在本小节主要介绍三者之间的相同点和共同点，图1显示了三者之间的关系。

图1 GEP、GA以及GP之间的关系

    2.1 遗传算法(GA)简介
    20世纪60年代由J.Holland提出。GA是一种基于自然选择和遗传变异等生物进化机制的全局性概率搜索算法。与基于导数的解析方法和其他启发式搜索方式（如爬山算法，模拟退火算法，Monte Carlo方法）一样，GA在算法形式上也是一种迭代方法。它从选定的初始解出发，通过不断迭代改进当前解，直到搜索到优秀的解决方案或满意解。在GA中，迭代计算过程采用了模拟生物的进化机制，从一组解（种群）出发，采用类似于自然选择和繁殖的方式，在继承原有优良基因的基础上，生成具有更好性能的下一代解种群。

    GA编码
    整个遗传算法GA的编码是通过基因链码来决定。何为基因链码？
    基因链码：生物的性状是由生物遗传基因的链码所决定。
    使用遗传算法时，需要把问题的每一个解编码成为一个基因链码。设1552是问题的一个解，我们可以用二进制形式11000010000来表示这个解所对应的基因链码，每个基因链码也被称作个体。
    一个群体是若干个体的集合。由于每个个体代表问题的一个解，所以一个群体就是问题的一些解的集合。

    GA编码方法
    编码方法：二进制编码、格雷码编码、浮点数编码、符号编码、多参数级联编码、多参数交叉编码。
    二进制编码可以是实数的二进制表示，也可以是按某种规则进行的二进制编码，但是要求二进制编码与实数之间一一对应。
    例1： 在[0,31]的整数上求F(x)=x2的最大值问题，可以直接利用实数的二进制表示，x={10111}表示16+4+2+1=23。问题转化为求解：

    GA交叉
    对两个相互配对的染色体按某种方式相互交换部分基因，从而形成两个新的个体。
    配对策略：随机配对，即将群体中的M个个体按随机的方式组成。对配对个体组随机确定交叉点的位置。
    基因交换方式：单点交叉、两个交叉
    交叉结果如下所示：
    A: x x x| x x x x A’: x x x y y y y
    B: y y y| y y y y B’: y y y x x x x
    GA变异
    将个体染色体编码串中的某些基因座上的基因值用该基因座上的其它等位基因来替换，从而形成新的个体，称为变异。
例如，对于二进制编码的个体，其编码字符集为{0,1}，变异操作就是将个体在变异点上的基因值取反，即用0替换1，或用1替换0。
    01001101 01000101
    使用变异算子的目的：
    （1）改善GA的局部搜索能力。交叉算子已经从全局的角度出发找到了一些较好的个体编码结构，这是再使用变异算子来调整个体编码串中的部分基因值，就可从局部角度出发使个体更逼近优秀的解决方案。
    （2）维持群体的多样性。变异算子用新的基因值替换原有基因值，从而可以改变个体编码结构，维持群体的多样性，防止早熟现象。

    适应度
    每个个体对应于优化问题的一个解xi,每个解xi对应于一个函数值fi,fi越大（如果优化问题要求取最大），则表明xi越好，即对环境的适应度越高，所以可用每个个体的函数值fi作为它对环境的适应度。

    遗传算法的不足之处
    （1）个体编码形式：固定长度、线形符号串、仅使用染色体表示问题；
    （2）必须对求解的问题编码，难！
    （3）个体是基因型和表现型的综合体（选择操作的目标，遗传信息的载体）；
    （4）对基因组的任何变动都会影响适应度和选择操作；
    （5）GA个体的二面性及其简单结构，导致不能用个体的某一部分来表示问题解，这将严重约束系统的性能；


    2.2.遗传编程(GP)简介
    1985年由Cramer首次提出，1992由Koza教授将其完善发展。GP是一种全局性概率搜索算法，它的目标是根据问题的概括性描述自动产生解决该问题的计算机程序。GP吸取了遗传算法（GA）的思想和达尔文自然选择法则，将GA的线性定长染色体结构改变为递归的非定长结构。这使得GP比GA更加强大，应用领域更广。

    GP的应用现状
    （1）机器人路径规划
    （2）响应agent
    （3）预测和分类
    （4）图像和信号处理
    （5）数据挖掘
    （6）信息检索
    （7）进化硬件
    （8）电子电路设计

    GP的算法框架
    Step1：随机产生初始化种群；
    Step2：计算种群中个体的适应度值；
    Step3：执行复制、交叉以及变异操作，产生新一代种群；
    Step4：计算新种群中每个个体的适应度值；
    Step5：当满足条件时，输出适应度值最优的个体，否则，转到Step3继续执行； 

    GP总结 
    （1）在只有问题的概括性描述而没有解决问题的具体算法细节的情况下自动解决问题；
    （2）全局的（基于群体）、并行的（从群体到群体）、概率性（非确定的）的搜索，增大了发现优秀的解决方案的可能性；
    （3）个体（解析树）既是基因型又是表现型，由整棵树构成问题解得表达方式不够简单灵活；
    （4）所有的遗传操作都是直接在树上进行，为了产生有效的结构，不得不受诸多的语义限制；
    （5）初始种群数量大（几百个），由于GP的遗传操作不能很好的产生新个体；


    2.3.基因表达式编程(GEP)简介
    GEP继承了GAs和GP的优点：使用简单、线形、固定长度的个体表达了不同大小和形状的结构(simple,plastic structure)。这种结构能：编码任何可能的程序并高效的进化；轻易的利用功能强大的遗传算子有效的搜索解空间；不会产生无效的个体。在进化计算中唯一使用了多基因的算法（更高的层次，许多新的值得探索的东西）。使用Karva language读取和表达存贮在GEP个体中的信息。

    GEP、GA以及GP的比较
    （1）GA个体编码简单，因此操作方便，但只能处理简单问题；
    （2）GP个体编码复杂，因此操作麻烦，且遗传操作不具备封闭性，很多资源消耗在处理无效结构上，但常用于求解复杂问题；
    （3）GEP是简单编码解决复杂问题，而且遗传操作方便，不会产生无效结构。

    3.GEP的基因结构
    GEP的基因结构主要包括两个主要的成员：染色体(Chromosome)和表达式树(K-Expression)。两者之间的关系是：染色体中所包含的遗传信息由表达式树来解码。其中染色体是由一个或者多个基因组成，每个基因包括头部(head)和尾部(tail)。
    GEP基因组
GEP中基因组（染色体）由一个线性的定长基因符号串组成。它是一种ORF(Open reading frames and genes)的编码序列。
    例2：对于数学表达式： ，它对应的表达式树如图2所示：

    对应的K-表达式为：

    这种ORF结构具有如下优势：
   （1）GEP染色体由一个或几个基因组成；
    （2）染色体长度确定，ORF长度灵活可变。
    GEP的基因结构
    GEP的基因主要有头部（head）和尾部（tail）构成。其中头部是从函数集F和终点集T中随机产生，而尾部只能从终点集T中随机产生。整个基因的长度（lchrom）等于基因头长（head）加上基因尾长（tail），也即lchrom＝head＋tail，其中tail=head* (n-1)+1 ，n为函数集中得最大操作目数。
    例3：函数集 F = {Q, *, /, -, +} ，终结点集 T = {a, b}
    预设头部长度h＝15，则有尾部长度：t = 15 x (2 - 1) + 1 = 16。基因长度15 + 16 = 31，则一个可能的基因：
    0123456789012345678901234567890
    *b+a-aQab+/ /+b+babbabbbababbaaa
    GEP的多基因染色体
    （1）复杂个体的进化需要使用多基因染色体；
    （2）GEP染色体通常由多个等长基因组成；
    （3）对于每个特定问题，基因数量和头部长度事先确定；
    （4）每条基因解码为一个子表达式树，子表达式树交互组成复杂实体。
    例4：有如下多基因染色体，头部长度为6，染色体长度为39，基因数为3。基因编码如下：
    012345678901201234567890120123456789012
    *Qb+*/bbbabab-a+QbQbbababa/ba-/*bbaaaaa
    对应的表达树为：

    多基因染色体包含多个ORF，每个ORF解码为结构和功能上独立的子表达式树。各个子表达式数有独立的适应度，由多个子表达式树组成复杂的表达式树，子表达式树既是一个独立实体，也是一个复杂整体的一部分。

    对于不同问题，GEP染色体可以采用简单的形式也可以采用复杂的形式。比如TSP问题，每个基因表示一个城市，整个TSP的编码就是一个多基因构成的染色体结构；比如在基于GEP优化的BP网络中，就需要设置特殊的结构来表示BP网络的结构。