树式遗传规划（TGP）

名称

树式遗传规划（Tree-based Genetic Programming, GP），遗传规划（Genetic Programming）

分类

查看分类思维导图

遗传规划是进化计算（Evolutionary Computation）的一个分支，而进化计算又隶属于计算智能（Computational Intelligence）和生物启发计算（Biologically Inspired Computation）。GP 与其他进化算法，如遗传算法（Genetic Algorithms）和进化策略（Evolution Strategies）密切相关。

• 计算智能
  • 生物启发计算
    • 进化计算
      • 进化算法
        • 遗传算法
        • 进化策略
        • 遗传规划
          • 树式遗传规划

策略

遗传规划通过进化计算机程序种群来求解给定问题，这些程序通常表示为语法树。种群中的每个个体都表示一个候选解，其适应度依据其解决当前问题的效果进行评估。

GP 中的进化过程模拟了自然选择与繁殖机制。适应度较高的个体更有可能被选中参与繁殖，繁殖过程中会应用交叉与变异等遗传算子生成新的子代程序。交叉通过组合两个父代程序的遗传成分来产生新个体，而变异则通过对单个父代程序引入随机修改来生成新个体。

选择、繁殖与评估过程在多个世代中反复进行，从而逐步提高种群整体的适应度。随着种群不断进化，更有效、更高效的程序会逐渐涌现，最终得到问题的解或对目标行为的近似实现。

过程

1. 初始化
   1. 定义问题以及进化程序所期望实现的行为或输出
   2. 确定用于构造程序树的函数集和终端集
   3. 设置种群规模、最大代数及其他控制参数
   4. 利用函数集和终端集随机生成初始程序树种群
2. 评估
   1. 对种群中的每个个体：
      1. 执行该个体所表示的程序树
      2. 根据其在给定问题上的表现评估该个体的适应度
3. 选择
   1. 根据适应度，采用某种选择方法（如锦标赛选择、轮盘赌选择）从种群中选出一部分个体
4. 繁殖
   1. 对选中的个体应用遗传算子，生成新的子代程序
      1. 交叉：随机选择两个父代程序，通过交换它们之间的子树来生成新的子代
      2. 变异：随机选择一个父代程序，通过修改其树结构（如用随机生成的子树替换某个子树）来生成新的子代
   2. 将新生成的子代程序加入种群
5. 替换
   1. 用新生成的子代程序替换现有种群中的一部分个体
   2. 可选择使用精英保留策略，以保留上一代中的最优个体
6. 终止
   1. 若达到最大代数，或已找到满意解，则终止算法
   2. 否则，返回步骤 2（评估）
7. 返回进化过程中找到的最优个体作为问题的解

数据结构

• 个体：以程序树形式表示的候选解
• 种群：由多个个体（程序树）构成，并在代际中不断演化
• 函数集：程序树内部节点所使用的函数集合（如算术运算符、逻辑运算符、领域特定函数）
• 终端集：程序树叶节点所使用的变量、常数和零元函数集合

参数

• 种群规模：每一代中的个体数量
• 最大代数：进化过程的停止准则
• 交叉率：应用交叉算子生成新子代的概率
• 变异率：应用变异算子生成新子代的概率
• 锦标赛规模：参与锦标赛选择的个体数量（若采用该方法）
• 树深度上限：程序树允许的最大深度，用于控制复杂度

注意事项

优点

• 灵活性：GP 能够在无需显式编程的情况下，自动为广泛类型的问题进化出程序
• 创造性：GP 能够发现人类程序设计者未必容易想到的新颖解
• 适应性：GP 能够通过持续进化新解来适应变化的问题需求

缺点

• 计算复杂度高：GP 的计算代价通常较高，特别是在种群规模较大或问题复杂时更为明显
• 膨胀：程序树在进化过程中可能变得过大、过复杂，从而降低可解释性和执行效率
• 过拟合：GP 可能进化出在训练数据上表现良好、但对未见样本泛化能力较差的程序

启发式建议

函数集与终端集设计

• 应包含与问题领域相关且具有多样性的函数与终端
• 应保证函数集和终端集足以表达潜在可行解
• 可考虑加入更高层次的函数或构件，以提高效率和可扩展性

种群规模与多样性

• 应使用足够大的种群规模，以维持多样性并有效探索搜索空间
• 可采用小生境或物种划分等技术保持多样性，防止过早收敛

交叉率与变异率

• 交叉率宜设得较高（如 0.8–0.9），以促进个体之间遗传信息的交换
• 变异率宜设得较低（如 0.01–0.1），以在不过度破坏优良解的前提下引入适度扰动
• 应根据问题复杂度以及期望的探索—开发平衡对参数进行调整

树深度限制与膨胀控制

• 应设置合理的树深度上限，以防程序树过度增长
• 可采用简约压力或显式规模限制等膨胀控制技术
• 可考虑使用能够天然抑制膨胀的替代表达方式或算子（如语法演化、子树封装）

适应度评估与选择

• 应设计能够准确衡量个体在目标问题上表现的适应度函数
• 应使用能够平衡探索与开发的选择方法（如中等规模的锦标赛选择）
• 可考虑在适应度评估中融入问题特定知识或启发式信息，以引导搜索过程

终止准则

• 应根据问题复杂度和可用计算资源设置最大代数
• 可基于目标解质量或收敛特性定义额外的终止条件
• 当已找到满意解时，可提前终止算法以节省计算开销