基因表达编程

在计算机编程中，基因表达编程（GEP）是一种创建计算机程序或模型的进化算法。这些计算机程序是复杂的树状结构，通过改变其大小、形状和组成来学习和适应，很像一个生物体。而像生物体一样，GEP的计算机程序也被编码在固定长度的简单线性染色体中。因此，GEP是一个基因型-表型系统，受益于简单的基因组来保持和传递遗传信息，以及复杂的表型来探索环境和适应环境。

进化算法使用个体种群，根据适合度选择个体，并使用一个或多个遗传算子引入遗传变异。它们在人工计算系统中的应用可以追溯到20世纪50年代，当时它们被用来解决优化问题（例如Box1957和Friedman1959）。但随着1965年Rechenberg对进化策略的介绍，进化算法才得到了普及。关于进化算法的一个很好的概述文本是Mitchell（1996）的《遗传算法简介》一书。基因表达式编程属于进化算法家族，与遗传算法和遗传编程密切相关。从遗传算法中，它继承了固定长度的线性染色体；而从遗传编程中，它继承了不同大小和形状的表达式解析树。在基因表达编程中，线性染色体作为基因型工作，解析树作为表型工作，形成了一个基因型/表型系统。这个基因型/表型系统是多基因的，因此在每条染色体上编码了多个解析树。这意味着GEP创建的计算机程序是由多个解析树组成的。由于这些解析树是基因表达的结果，在GEP中它们被称为表达树。

基因表达编程的基因组由一个固定长度的线性符号字符串或染色体组成，由一个或多个大小相同的基因组成。这些基因尽管长度固定，但对不同大小和形状的表达树进行编码。一个有两个基因的染色体的例子，每个基因的大小为9，是一个字符串（零号位置表示每个基因的开始）。012345678012345678L+a-baccd**cLabacd其中"L"代表自然对数函数，"a"、"b"、"c"、"d"代表问题中使用的变量和常数。表达树：表征如上所示，基因表达编程的基因都有相同的大小。然而，这些固定长度的字符串为不同大小的表达树编码。这意味着编码区的大小因基因而异，使适应和进化得以顺利进行。

这种表达树由GEP基因的表型表达组成，而基因是编码这些复杂结构的线性字符串。对于这个特殊的例子，线性字符串对应的是。这是对表达树从上到下和从左到右的直读。这些线性字符串被称为k-表达式（来自Karva符号）。从k表达式到表达树也非常简单。例如，下面这个k表达式。01234567890Q*b**+baQba是由两个不同的终端（变量"a"和"b"），两个不同的两个参数的函数（"*"和"+"），和一个参数的函数（"Q"）组成。其表达式给出了。

基因表达式编程的K-表达式对应于得到表达的基因区域。这意味着基因中可能有不被表达的序列，这对大多数基因来说确实如此。之所以有这些非编码区，是为了提供一个终端的缓冲区，以便GEP基因中编码的所有K表达总是对应于有效的程序或表达。因此，基因表达程序的基因是由两个不同的域组成的--头和尾--每个域都有不同的属性和功能。头部主要用于编码为解决手头问题而选择的函数和变量，而尾部虽然也用于编码变量，但基本上提供了一个终端库，以确保所有程序都没有错误。对于GEP基因来说，尾巴的长度由公式给出。其中，h是头的长度，nmax是xxx算数。例如，对于使用函数集F={Q,+,-,∗,/}和终端集T={a,b}创建的基因，nmax=2。而如果我们选择头的长度为15，那么t=15（2-1）+1=16，即