基因表达式编程（GeneExpressionProgramming,GEP）
前⾔
该算法旨在在⼀组数据点中，⽤基因表达式编程的⽅法，根据基因遗传定律，物竞天择、优者⽣存，劣者淘汰的思想，不断进化种群，找出适宜度最⾼的染⾊体来模拟出数据点之间所存在的数学表达式关系。通常该算法⽤来解决符号回归问题：符号回归（Symbolic Regression）作为⼀种⼀种监督学习⽅法，试图发现某种隐藏的数学公式，以此利⽤特征变量预测⽬标变量。符号回归的优点就是可以不⽤依赖先验的知识或者模型来为⾮线性系统建⽴符号模型。符号回归基于进化算法，它的主要⽬标就是利⽤进化⽅法综合出尽可能好的解决⽤户⾃定义问题的⽅法（数学公式，计算机程序，逻辑表达式等）。
1 编码规则
1.1 基因
⼀段基因由两部分组成：头部和尾部，形如：
其中，红⾊部分为头部基因，其长度为9，绿⾊部分为尾部基因，其长度为8。
基因中的每个元素分为两种形式：函数和终点，它们分别从函数集和终点集中进⾏选择：
函数集
算术运算符：例如+、-、*、/等
初等数学函数，例如：sin、开⽅、cos等
其它⼀些函数，例如：max、min等
布尔运算符：例如与、或、⾮
关系运算符：例如<、>、=等
条件运算符：例如 if 等
终点集
变量数值：例如x1、x2
常量数值：例如π、e
⽆参函数：例如rand()等
基因头部长度我们⽤h表⽰，尾部长度⽤t表⽰，函数集所需最⼤参数⽤n表⽰，⽐如⼀个函数集为{+、-、*、/、sin、cos}，其中所需参数的最⼤个数为2，则n为2
那么h、t、n三者之间的关系是：t=h∗(n−1)+1
维持这样的关系，可以保证产⽣的基因编码都是合法编码。
1.2 基因编码原理
月经能喝咖啡吗⽐如下⽅的数学表达式：
翻译成表达式树为，其中Q表⽰开⽅：
当官记那么可以得到它的基因型为：
下⾯来看看⼀个基因型翻译成表达式的过程：
基因型如下：
基因的起点对应表达式树的根：
Q(开⽅)需要⼀个参数，那么往后取⼀个参数：
乘法需要两个参数，往后取两个参数：
以此类推，可以画出该基因型的表达式树为：
我们可以看出，表达式树的根⼀定要是函数集的元素，叶⼦节点⼀定是终点集的元素。
Processing math: 100%
1.3 染⾊体
⼀条染⾊体可以由多个基因构成，那么我们需要设定基因连接符，⽐如⽤+、-、 *、/等符号进⾏连接，⽐如：
这三个⼦树我们可以通过+进⾏连接：
其次⼀条染⾊体代表⼀个个体，那么⼀个种群就可以有多个染⾊体。
1.4 Dc域
在符号回归问题种，我们使⽤这样的结构来操纵随机数值常量。例如，如下的染⾊体：
含有⼀个附加域 Dc，这个附加域⽤来对随机数值常量进⾏编码。该染⾊体的翻译过程如下图所⽰：
1.5 进化过程
基因的进化分为以下⼏种：
变异
转座
IS转座
RIS转座
基因转座
重组
单点重组
两点重组
基因重组
下⾯我们对进化操作分别进⾏讲解：
1.5.1 变异
变异的原则：
基因⾸位元素必须是函数集元素
除过⾸位外的头部基因可以从函数集或者终点集进⾏选择
尾部元素必须是终点集元素
变异过程将随机从种群中选择个体（染⾊体），再从染⾊体中随机选择⼀个基因，从基因中随机选择⼀个位置。
void Gene::mutation()
{
int index = rand() % gene_len;
char ch;
if (index <= HEAD_LEN)
ch = getRandomElem();
el
ch = getTermElem();
text[index] = ch;
}
1.5.2 转座
1.5.
2.1 IS转座
IS转座是从种群中随机选择⼀个染⾊体，然后随机从IS转座长度中选择IS长度，然后在染⾊体中选择IS长度的基因⽚段，并随机选择基因，插⼊到除基因⾸元素之外的头部部分中，如下所⽰：
void Individual::transposition_is()
{
// 随机选取转座长度
int len_array = sizeof(IS_LEN) / sizeof(int);
int index = rand() % len_array;
int len_is = IS_LEN[index];
// 从整段染⾊体中随机选取len_is个长度的⽚段
index = rand() % (len - len_is); // 随机起始索引
string str = content_without_space().substr(index, len_is); // 截取字符串
// 随机选择基因
index = index_rand(); gene[index].transposition(str);
}
1.5.
2.2 RIS转座
所有的RIS元素都是从⼀个函数开始，因此是选⾃头部分中的序列。因此在头中任选⼀点，沿基因向后查找，直到发现⼀个函数为⽌。该函数成为RIS元素的起始位置。如果找不到任何函数，则变换不执⾏任何操作。该算⼦随机选取染⾊体，需要修饰的基因，RIS元素以及其长度。变化过程如图所⽰：
void Individual::transposition_ris()
{
// 随机选择基因
int index = index_rand();
// 在头中随机选取⼀点
int pos = rand() % HEAD_LEN;
/
/ 沿该点向后查找直到发现⼀个函数该点即为RIS转座的起始点
int a;
if ((a = gene[index].find_func(pos)) == -1)
元旦节的画return;
pos = a + Gene::length() * index;
// 随机选取RIS转座长度
int len_array = sizeof(RIS_LEN) / sizeof(int);
职业心态index = rand() % len_array; int len_ris = RIS_LEN[index];
// 从起始点向后取len_ris个长度的⽚段 string str = content_without_space().substr(pos, len_ris);
index = index_rand(); gene[index].transposition(str);
}
1.5.
2.3 基因转座
基因转座仅仅改变基因在同⼀染⾊体中的位置，如图所⽰：
void Individual::transposition_gene()
{
// 随机选取两个不同位置的基因
if (GENE_NUM > 1)
{
int index1 = 0;
int index2 = 0;
while (index1 == index2)
{
index1 = index_rand();
index2 = index_rand();
}
Gene temp(gene[index1]);
关于黄山的诗句gene[index1] = gene[index2];
gene[index2] = temp;
}
}
1.5.3 重组
1.5.3.1 单点重组
进⾏单点重组的时候，⽗代染⾊体相互配对并在相同的位置切断，两个染⾊体相互交换重组点之后的部分，如图所⽰：
void Population::recombination_one()
{
double prob = rand() / double(RAND_MAX);
if (prob < PROB_RECOMBE_ONE)
{
// 随机选取两个不同个体
int index1 = 0;
int index2 = 0;
while (index1 == index2)
{
index1 = rand() % count;
index2 = rand() % count;
}
// 随机选取重组点
int pos = rand() % Individual::length();
string subStr1 = individual[index1].content_without_space().substr(0, pos);
string subStr2 = individual[index2].content_without_space().substr(0, pos);
// 交换两个染⾊体的⽚段 individual[index1].recombination(0, pos, subStr2);
individual[index2].recombination(0, pos, subStr1);
}
}
1.5.3.2 两点重组
进⾏两点重组的时候，⽗代染⾊体相互配对，在染⾊体中随机选择两个点，将染⾊体切断。两个染⾊体相互交换重组点之间的部分，形成两个新的⼦代染⾊体。如图所⽰：
void Population::recombination_two()
{
double prob = rand() / double(RAND_MAX);
if (prob < PROB_RECOMBE_TWO)
{
// 随机选取两个不同个体
int index1 = 0;
int index2 = 0;
while (index1 == index2)
{
index1 = rand() % count;
index2 = rand() % count;和蔼意思
}
// 随机选取左、右重组点
int pos_left = rand() % Individual::length();
int pos_right = (rand() % (Individual::length() - pos_left)) + pos_left;
int len = pos_right - pos_left + 1; // 重组点之间的距离
// 重组点之间的字符串，包括左、右重组点
string subStr1 = individual[index1].content_without_space().substr(pos_left, len);
string subStr2 = individual[index2].content_without_space().substr(pos_left, len);
/
/ 交换两个染⾊体的⽚段
individual[index1].recombination(pos_left, len, subStr2);
individual[index2].recombination(pos_left, len, subStr1);
}
}
菠萝蜜口感
1.5.3.3 基因重组
在 GEP 的第三种重组中，两个染⾊体中的整个基因相互交换，形成的两个⼦代染⾊体含有来⾃两个⽗体的基因。
void Population::recombination_gene()
{
double prob = rand() / double(RAND_MAX);
if (prob < PROB_RECOMBE_GENE)
{
// 随机选取两个不同个体 int index1 = 0;
int index2 = 0; while (index1 == index2)
{
index1 = rand() % count; index2 = rand() % count;
}
// 随机选取基因索引
int index = rand() % GENE_NUM;
// 获取两个个体相应索引的基因
string subStr1 = individual[index1].content_without_space().substr(index * Gene::length(), Gene::length());
string subStr2 = individual[index2].content_without_space().substr(index * Gene::length(), Gene::length());
// 交换
individual[index1].recombination(index * Gene::length(), Gene::length(), subStr2);
individual[index2].recombination(index * Gene::length(), Gene::length(), subStr1);
}
}
1.6 适应度函数
个体程序 的适应度 可以⽤第⼀个⽅程来表⽰，当误差类型选为相对误差的时候，个体程序的适应度 可以⽤⽅程（3.1b）来表⽰：
其中M是选择范围，C(i,j)是染⾊体个体i对于适应度样本j（来⾃C t集合中）的返回值。⽽T j是适应度样本j的⽬标值。请注意，两个⽅程中的绝对值项都对应各⾃的误差（前⼀个⽅程中对应于绝对误差，
后⼀个⽅程中对应于相对误差）。该项称为精度p。因此，对于⼀个完美适应的情况， 且 C(i,j)=C t且f i=f max=C t M。
1.7 个体的选择
在 GEP 中，个体通过赌盘轮采样策略根据其适应度进⾏选择。每个个体⽤圆形赌盘的⼀块来代表其适应度的⽐例。赌盘按照群体中个体数的值进⾏相应次数的旋转，从⽽始终保持群体的⼤⼩不变。
采⽤这种选择策略，确实有时候会丢失⼀些最佳个体，⽽⼀些普通个体进⼊到了下⼀代。但是这样也不⼀定就不好，因为种群会⼀代⼀代地向前推进。⽽且，因为我们使⽤每⼀代中的最佳个体复制策略，所以最佳个体的存在和复制能够得到保证。这样，⾄少最优的特性从来没有丢失过，并且能够达到不断学习的⽬的。
还有⼏种其他最常⽤的选择算法——赌盘选择、确定性选择、锦标赛选择。
2 符号回归
2.1 算法流程图
2.2 测试函数及数据
y=2x2+5x+3
2.3 参数设置
参数名称参数值
函数集{+、-、*、/}
终点集a
头部长度7
是否开启Dc域True
Dc域最⼤值10.0
真皮沙发怎么保养和清洗Dc域最⼩值0.0
Dc域元素个数10
基因数⽬4
基因连接符+
种群⼤⼩20
繁衍代数1000
