语法演化（GE）

名称

语法演化（Grammatical Evolution, GE）

分类

查看分类思维导图

语法演化是一种利用语法引导遗传规划技术来进化计算机程序或规则的进化算法。它与遗传规划（Genetic Programming, GP）和遗传算法（Genetic Algorithms, GA）密切相关。

• 计算智能
  • 生物启发计算
    • 进化计算
      • 遗传规划
        • 语法演化

策略

语法演化是一种基于种群的优化算法，它利用上下文无关文法来引导解的生成与进化。该文法通常以巴科斯-诺尔范式（Backus-Naur Form, BNF）表示，用于定义可进化解的结构与语法。

基因型表示

在 GE 中，解被表示为可变长度的整数数组，称为基因型。基因型中的每个整数对应文法中的一条产生式规则。在映射过程中，基因型被用于从文法中选择产生式规则。

基因型到表型的映射

基因型到表型的映射过程依据文法所定义的规则，将整数基因型转换为合法解（表型）。映射从文法的起始符号开始，并根据基因型中的整数值递归地应用产生式规则，直到生成完整解为止。

演化过程

GE 遵循标准的进化过程，包括选择、交叉和变异。每个解的适应度由预先定义的适应度函数进行评估。父代根据适应度被选择用于繁殖，而子代则通过在基因型上施加交叉与变异操作生成。

回绕与无效解

如果在映射过程中，基因型已使用到末尾但仍未生成完整解，则采用回绕机制，从头重新使用基因型中的整数。若映射过程产生了违反文法规则的无效解，则会为该解赋予较低的适应度值，以降低其在后续世代中被选中的概率。

过程

1. 初始化种群
   1. 生成由随机整数基因型构成的种群
   2. 利用文法将每个基因型映射为相应表型
   3. 评估种群中每个个体的适应度
2. 当终止条件未满足时，重复以下过程：
   1. 根据适应度选择父代个体用于繁殖
   2. 在基因型上执行交叉与变异操作生成子代
      1. 对选中的父代应用交叉操作，生成子代基因型
      2. 对子代基因型应用变异操作
   3. 利用文法将子代基因型映射为相应表型
   4. 评估子代的适应度
   5. 根据适应度选择下一代个体（例如，用子代替换适应度最低的个体）
3. 返回找到的最优解

数据结构

• 基因型：表示搜索空间中解的整数数组
• 表型：通过文法将基因型映射后得到的实际解
• 文法：定义合法解结构与语法的上下文无关文法
• 种群：由个体（基因型及其对应表型）构成的集合

参数

• 种群规模：种群中的个体数量
• 最大代数：算法运行的最大世代数
• 交叉概率：对选中父代应用交叉操作的概率
• 变异概率：对子代基因型应用变异操作的概率
• 回绕次数：映射过程中允许对基因型进行回绕的最大次数

注意事项

优点

• 能够进化出由文法定义的、具有复杂结构与约束的解
• 搜索空间（基因型）与解空间（表型）相分离，因此表示方式更加灵活
• 适用于最优解结构事先未知的问题

缺点

• 针对具体问题领域设计合适文法往往较为困难且耗时
• 映射过程可能具有较高计算代价，尤其是在文法规模较大、基因型较长时更为明显
• 基因型表示中的冗余性可能导致搜索过程效率下降

启发式建议

文法设计

• 采用模块化、层次化的文法结构，以促进有意义解的进化
• 确保文法能够覆盖必要的解空间，同时避免不必要的复杂性
• 可考虑将领域知识融入文法中，以更有效地引导搜索过程

种群初始化

• 生成具有较高多样性的初始种群，以探索搜索空间中的不同区域
• 确保初始基因型长度足以生成合法表型

选择与繁殖

• 采用能够平衡探索与开发的选择方法，如锦标赛选择或基于排序的选择
• 根据问题复杂度以及期望的探索强度，调整交叉概率与变异概率

回绕与无效解处理

• 设定适当的回绕次数，以在复用基因型信息和避免过度回绕导致低效之间取得平衡
• 可考虑引入修复机制或惩罚函数，以处理无效解并引导搜索朝合法解区域进行

参数调节

• 通过实验测试不同参数设置，以找到适合具体问题的最优配置
• 可采用参数控制技术，如自适应参数或自适应进化参数，在演化过程中动态调整参数

混合化

• 可考虑将语法演化与其他优化技术（如局部搜索或机器学习）进行混合，以提升搜索效率与解质量
• 可将领域特定启发式或知识融入演化过程，以引导搜索朝更有前景的区域发展