语法引导遗传规划（GGGP）

名称

语法引导遗传规划（Grammar-Guided Genetic Programming, GGGP），又称基于语法的遗传规划（Grammar-based Genetic Programming）、语法引导 GP、G3P

分类

查看分类思维导图

语法引导遗传规划是遗传规划（Genetic Programming, GP）的一种专门形式，它通过引入语法来约束并引导进化过程。它与其他基于语法的进化算法（如语法演化，Grammatical Evolution, GE）密切相关，可视为传统遗传规划的一种扩展。

• 人工智能
  • 计算智能
    • 进化计算
      • 进化算法
        • 遗传规划（GP）
          • 语法引导遗传规划（GGGP）

策略

语法引导遗传规划结合了进化计算的搜索能力与语法所提供的结构约束，以求解复杂问题。GGGP 的核心思想在于：利用语法来定义可能解的搜索空间，从而确保进化得到的程序在语法上是正确的，并符合期望的结构约束。

表示

在 GGGP 中，种群中的个体通常表示为由给定语法导出的推导树（derivation tree）或抽象语法树（Abstract Syntax Tree, AST）。语法规定了有效的构造单元及其组合规则，以生成合法程序。这种基于语法的表示方式使搜索能够集中在受约束的解空间内，从而提升搜索的针对性。

初始化

GGGP 的初始种群通过随机选择语法产生式规则并据此构造合法的推导树生成。该初始化过程能够保证种群中的所有个体都满足给定语法所施加的语法约束。

遗传算子

GGGP 使用专门作用于推导树、且同时保持语法结构合法性的遗传算子：

• 交叉：交叉算子从两个父代个体中选择兼容的子树并进行交换，以生成子代。子树之间的兼容性由语法决定，从而保证生成的子代仍然满足语法规则。
• 变异：变异算子对个体的推导树引入随机扰动。其做法是选择树中的某个节点，并用另一个由语法导出的兼容子树替换它。变异算子有助于维持种群多样性，并促进对新解的探索。

适应度评估

种群中每个个体的适应度根据其在给定问题上的表现进行评估。适应度函数通过执行进化得到的程序，并衡量其解决目标问题的能力来评价程序质量。具体的评估方式取决于问题本身，可能涉及准确率、效率或其他相关指标。

选择与替换

GGGP 根据适应度采用相应的选择机制来挑选个体参与繁殖。常见的选择方法包括锦标赛选择、轮盘赌选择和基于排序的选择。被选中的个体经过遗传操作生成子代，随后对子代进行适应度评估。子代可以替换种群中适应度较低的个体，从而使种群在代际演化中不断改进。

过程

数据结构：

• 语法：用于规定程序合法结构及构造单元的形式语法。
• 推导树：由语法导出的、表示单个程序个体的树结构。
• 种群：由多个推导树组成的当前候选解集合。

参数：

• 种群规模：种群中的个体数量。
• 最大代数：算法运行的最大迭代代数。
• 交叉率：对选中个体应用交叉算子的概率。
• 变异率：对个体应用变异算子的概率。
• 选择方法：用于选择繁殖个体的方法（如锦标赛选择、轮盘赌选择）。
• 替换策略：用子代替换种群中个体的策略（如世代替换、稳态替换）。

算法步骤：

1. 初始化种群：
   1. 创建空种群。
   2. 重复以下过程，直到达到种群规模：
      1. 从语法的根符号开始。
      2. 递归地选择并应用产生式规则，生成一个合法的推导树。
      3. 将生成的推导树加入种群。
2. 评估种群中每个个体的适应度。
3. 重复以下过程，直到达到最大代数或找到满意解：
   1. 根据选择方法从种群中选择个体。
   2. 对选中的个体应用遗传算子：
      1. 交叉：
         1. 选择两个父代个体。
         2. 在它们的推导树中选择兼容的交叉点。
         3. 交换所选交叉点处的子树，生成两个子代。
      2. 变异：
         1. 选择一个个体。
         2. 在其推导树中选择一个变异点。
         3. 用由语法导出的一个新的兼容子树替换该变异点处的子树。
   3. 评估子代的适应度。
   4. 根据替换策略，用子代替换种群中的个体。
4. 返回整个进化过程中找到的最优个体。

注意事项

优点：

• 通过遵循给定语法，能够保证进化程序的语法合法性。
• 能够在语法定义的受约束解空间内进行更有针对性的搜索。
• 可以通过语法设计将领域知识融入进化过程。

缺点：

• 需要预先定义合适的语法，而这在复杂问题领域中往往具有较大难度。
• 语法的选择会显著影响进化程序的性能与表达能力。
• 对于大规模语法和复杂问题，进化过程的计算代价可能较高。

启发式建议

语法设计

• 应设计能够刻画问题领域核心组成与结构特征的语法。
• 需要在语法表达能力与复杂度之间取得平衡。表达能力更强的语法能够覆盖更广泛的解空间，但也可能扩大搜索空间。
• 可考虑将领域特定知识和约束融入语法中，以引导搜索朝更有前景的区域发展。

种群初始化

• 可通过随机化推导树生成方式，保证初始种群具有足够多样性。
• 可结合启发式信息或领域特定规则，生成更有意义的初始个体。

遗传算子配置

• 应根据问题复杂度以及所需的探索—开发平衡调整交叉率和变异率。较高的交叉率有助于利用已有优良解，较高的变异率则有助于探索新解。
• 可针对具体问题领域和语法结构，尝试不同类型的交叉与变异算子。

适应度评估

• 应设计能够准确反映问题目标与期望性质的适应度函数。
• 如有必要，可在适应度评估中引入多目标或约束条件。
• 对于计算代价较高的问题，应优化适应度评估过程，以尽量降低计算开销。

选择与替换策略

• 应选择能够在保持适当选择压力的同时维持种群多样性的选择方法。锦标赛选择和基于排序的选择是常用方案。
• 可尝试不同替换策略，例如世代替换（用子代替换整个种群）或稳态替换（仅替换部分个体），以找到更适合具体问题的配置。

终止准则

• 应根据问题需求设置合适的终止准则，例如达到最大代数、找到质量足够高的解，或观察到种群已趋于收敛。
• 可考虑引入早停机制，以便在算法较早收敛到满意解时避免不必要的计算。