基因表达式编程（GEP）

名称

基因表达式编程（Gene Expression Programming, GEP）

分类

查看分类思维导图

基因表达式编程是进化计算（Evolutionary Computation）的一个分支，而进化计算隶属于计算智能（Computational Intelligence）与生物启发计算（Biologically Inspired Computation）范畴。它与遗传规划（Genetic Programming, GP）和遗传算法（Genetic Algorithms, GA）密切相关。

• 计算智能
  • 生物启发计算
    • 进化计算
      • 进化算法
        • 遗传算法（GA）
        • 遗传规划（GP）
          • 基因表达式编程（GEP）

策略

基因表达式编程是一种进化算法，其通过进化计算机程序或数学表达式来求解给定问题。GEP 与其他进化算法（如 GP）的关键区别在于基因型与表型的分离。

基因型—表型分离

在 GEP 中，个体被编码为固定长度的线性字符串（基因型），随后再将其翻译为大小和形状可变的表达式树（表型）。这种分离机制使得一个个体可以包含多个基因，每个基因编码一棵子表达式树；随后再将这些基因连接起来，形成更复杂的多子单元表达结构。

遗传算子

GEP 采用与 GA 和 GP 类似的遗传算子，例如变异、转座和重组。这些算子作用于线性基因型之上，之后再将其翻译为表达式树以进行适应度评估。

适应度评估

每个个体的适应度依据其表达式树对给定问题的求解效果进行评估。通常做法是将表达式树作用于一组训练数据，并测量其输出与期望输出之间的误差或偏差。

选择与繁殖

个体根据适应度被选择用于繁殖，适应度较高的个体具有更大的被选中概率。被选中的个体随后经历遗传操作，以生成下一代候选解。

过程

数据结构

• 染色体：表示个体基因型的固定长度线性字符串。
• 基因：染色体中的一个子串，用于编码一棵表达式树。
• 表达式树：表示个体表型的树状结构，可被执行以求解问题。

参数

• 种群规模：每一代中的个体数量。
• 进化代数：算法运行的最大迭代次数。
• 变异率：基因发生变异的概率。
• 转座率：基因发生转座的概率。
• 重组率：两个个体交换遗传物质的概率。

算法步骤

1. 用随机生成的染色体初始化种群。
2. 当终止条件未满足时，执行：
   1. 对种群中的每个个体：
      1. 将染色体翻译为表达式树。
      2. 在训练数据上执行表达式树。
      3. 根据其表现计算个体适应度。
   2. 根据适应度选择个体用于繁殖。
   3. 对选中的个体应用遗传算子（变异、转座、重组），生成新一代。
   4. 用新一代替换当前种群。
3. 返回搜索过程中找到的最优个体。

注意事项

优点

• 实现了基因型与表型的分离，使搜索过程更灵活且更高效。
• 能够进化出复杂的多子单元表达式。
• 采用简单的线性基因型表示。

缺点

• 需要针对具体问题领域精心设计函数集与终端集。
• 可能出现膨胀（bloat）现象，即表达式规模增大但适应度并未相应提升。
• 在大规模种群和长染色体情况下，计算代价可能较高。

启发式建议

函数集与终端集

• 选择与问题领域相关且足够完备的函数和终端。
• 应包含具有多样性的函数，以支持复杂表达式的进化。
• 确保函数集与终端集满足封闭性，即任一函数都能接受其他任一函数或终端的输出作为输入。

种群规模与进化代数

• 采用能够兼顾多样性与计算效率的种群规模，典型取值通常在 50 到 1000 个个体之间。
• 根据问题复杂度和可用计算资源设定进化代数，并通过监测适应度变化来判断是否需要增加代数。

遗传算子概率

• 可从约 0.1 的变异率开始，并根据具体问题及种群多样性进行调整。
• 可采用较低的转座率（如约 0.05），以对表达结构引入小幅变化。
• 可将重组率设置在约 0.7，以促进个体间遗传物质的交换。

适应度函数

• 设计能够准确衡量个体在目标问题上表现的适应度函数。
• 可考虑采用多目标适应度函数，以平衡准确性与表达式复杂度等多个指标。
• 对适应度值进行归一化，以保证个体之间的公平比较。

终止条件

• 设置最大进化代数作为停止条件，以避免无限运行。
• 监测适应度提升情况，若在连续若干代内未出现显著改进，则可终止算法。
• 可设置目标适应度阈值，当某个个体达到或超过该值时停止算法。