遗传规划（GP）

名称

遗传规划（Genetic Programming, GP）

分类

查看分类思维导图

遗传规划是进化计算（Evolutionary Computation）的一个分支，而进化计算又是计算智能（Computational Intelligence）的一个子领域。它与其他进化算法密切相关，例如遗传算法（Genetic Algorithms）、进化策略（Evolution Strategies）和进化规划（Evolutionary Programming）。

• 计算智能
  • 进化计算
    • 进化算法
      • 遗传规划

策略

表示

在遗传规划中，解通常表示为树结构，其中树中的每个节点对应一个函数或终端。函数节点是内部节点，用于对其子节点执行运算；终端节点是叶节点，用于表示变量或常数。具体采用哪些函数和终端取决于问题领域，这一集合通常称为原语集（primitive set）。

初始化

候选解的初始种群通常通过随机方式或基于问题特定启发式的方法生成。种群中的每个个体通过递归地从原语集中选择函数和终端来构造，直到形成一棵完整的树。为了防止生成规模过大的个体，通常会对树的深度加以限制。

评估

种群中的每个个体都通过适应度函数进行评估，以衡量其对给定问题的求解效果。适应度函数会为每个个体赋予一个数值，数值越高表示解的质量越好。具体的适应度函数依赖于具体问题，可能需要在一组测试样例上运行所进化得到的程序，或在模拟环境中评估其性能。

选择

选择是从当前种群中挑选个体作为下一代父代的过程。常见的选择方法包括锦标赛选择，即随机选取固定数量的个体并从中挑选适应度最高者；以及适应度比例选择，即个体以与其适应度成比例的概率被选中。

遗传算子

对选中的父代施加遗传算子以产生新的子代。遗传规划中主要使用的两类算子包括：

1. 交叉：选择两个父代个体，并交换各自的某些子树，从而生成两个新的子代。交叉点随机选择，生成的子代将同时继承两个父代的部分特征。
2. 变异：选择一个父代个体，并将该个体中的某棵随机子树替换为一棵新生成的子树。变异能够向种群中引入新的遗传信息，并有助于维持种群多样性。

替换

新生成的子代在经过适应度评估后，会替换当前种群中的部分或全部个体。常见的替换策略包括世代替换，即整代种群全部由子代替换；以及稳态替换，即每一代仅替换其中一部分个体。

终止

评估、选择、遗传操作和替换这一过程会持续进行，直到达到预设的进化代数，或找到令人满意的解为止。在进化过程中找到的最优个体通常被作为最终解输出。

过程

1. 定义原语集：
   1. 指定进化程序中要使用的函数集和终端集。
   2. 确保原语集足以表达给定问题的解。
2. 初始化种群：
   1. 设置种群规模以及初始个体的最大深度。
   2. 对种群中的每个个体：
      1. 从原语集中随机选择一个函数作为根节点。
      2. 递归地为每个子节点随机选择函数或终端，直到达到最大深度，或所有分支均以终端结束。
3. 评估种群：
   1. 对种群中的每个个体：
      1. 执行该个体所表示的进化程序。
      2. 使用指定的适应度函数计算其适应度值。
4. 当终止条件未满足时，重复执行：
   1. 选择父代：
      1. 采用某种选择方法（如锦标赛选择或适应度比例选择）从种群中选取一个个体子集。
   2. 应用遗传算子：
      1. 交叉：
         1. 从选出的个体子集中选择两个父代个体。
         2. 在每个父代中随机选择交叉点。
         3. 交换以交叉点为根的子树，生成两个子代。
      2. 变异：
         1. 从选出的个体子集中选择一个父代个体。
         2. 在该个体内部随机选择一个变异点。
         3. 用新生成的子树替换以该变异点为根的原子树。
   3. 评估子代：
      1. 对每个子代个体：
         1. 执行该子代所表示的进化程序。
         2. 计算其适应度值。
   4. 替换种群：
      1. 根据某种替换策略（如世代替换或稳态替换），从当前种群和子代中选择个体构成新种群。
5. 返回进化过程中找到的最优个体作为最终解。

数据结构

• 个体：表示种群中的一个候选解，通常实现为树结构，其中每个节点包含一个函数或终端。
• 种群：由多个个体组成的集合，通常实现为数组或列表。
• 适应度函数：根据个体在给定问题上的表现为其赋予数值的函数。适应度函数具有问题依赖性，需要由用户针对具体任务定义。

参数

• 种群规模：种群中个体的数量。较大的种群能够探索更广阔的搜索空间，但也会消耗更多计算资源。
• 最大深度：个体树结构允许达到的最大深度，用于控制进化程序的复杂度。
• 交叉概率：对一对选中父代应用交叉算子的概率。较高的交叉概率有助于促进个体间遗传物质的交换。
• 变异概率：对选中个体应用变异算子的概率。较高的变异概率能够向种群中引入更多多样性。
• 锦标赛规模：在锦标赛选择中参与竞争的个体数量。较大的锦标赛规模会提高对高适应度个体的选择压力。
• 进化代数：进化过程允许执行的最大迭代次数，用于决定分配给搜索过程的计算预算。

注意事项

优点

• 灵活性：遗传规划能够在无需用户预先指定解结构的情况下自动进化解，并可能发现新颖甚至出人意料的解决方案。
• 可扩展性：遗传规划能够通过遗传算子高效探索搜索空间中的潜在优良区域，因此可以处理搜索空间较大的复杂问题。
• 自适应性：遗传规划能够依据适应度函数所提供的反馈持续进化解，从而适应变化的问题环境。

缺点

• 计算代价高：需要对种群中的每个个体进行适应度评估，这通常计算开销较大，尤其是在需要在大规模数据集上执行进化程序或在复杂仿真环境中评估时更为明显。
• 膨胀：遗传规划容易产生规模大于实际所需的解，这种现象称为膨胀（bloat）。膨胀后的解通常效率更低，也更难解释。
• 过拟合：与其他机器学习方法类似，遗传规划也容易发生过拟合，即进化得到的解在训练数据上表现良好，但对未见样本的泛化能力较差。

启发式建议

函数与终端的选择

• 选择与问题领域相关、能够表达有意义解的函数和终端。
• 确保原语集具有完备性，即能够表达该问题的任意可能解。
• 应包含多样化的函数和终端，以支持对不同解结构的探索。

种群初始化

• 将初始最大深度设置在合理范围内（如 5–10），以防止生成规模过大的个体。
• 可以考虑利用问题特定启发式，或用已知的优良解对初始种群进行播种，以为进化提供更好的起点。

适应度函数设计

• 设计能够准确衡量解质量的适应度函数，使其符合具体问题背景。
• 若问题涉及多个优化目标，可考虑在适应度函数中纳入多目标机制。
• 使用足够数量的测试样例，或采用具有代表性的问题样本来评估个体。

遗传算子概率

• 可将交叉概率设置得较高（如 0.8–0.9），以促进个体之间遗传物质的交换。
• 可将变异概率设置得较低（如 0.01–0.1），以在不显著破坏优良解的前提下引入多样性。
• 应依据问题复杂度以及对探索与开发平衡的需求，对算子概率进行调整。

膨胀控制

• 可通过限制进化程序的最大深度等方式抑制膨胀现象。
• 可采用简约压力（parsimony pressure），即在适应度函数中加入针对个体规模的惩罚项。
• 可对进化程序应用简化或剪枝技术，以删除冗余或无贡献的部分。

并行化

• 可将个体评估过程分配到多个处理器或多台机器上执行，以降低整体计算时间。
• 可采用岛模型（island model），即让多个子种群独立进化，并周期性交换个体，以维持多样性并探索搜索空间的不同区域。