强类型遗传规划（STGP）

名称

强类型遗传规划（Strongly Typed Genetic Programming, STGP）

分类

查看分类思维导图

强类型遗传规划是遗传规划（Genetic Programming, GP）的一种专门形式，它将计算机科学中的强类型思想引入进化过程。它与标准遗传规划（Standard Genetic Programming）和语法引导遗传规划（Grammar-Guided Genetic Programming）密切相关。

• 人工智能
  • 计算智能
    • 进化计算
      • 遗传规划（GP）
        • 标准遗传规划
        • 语法引导遗传规划
        • 强类型遗传规划（STGP）

策略

强类型遗传规划是在标准遗传规划范式的基础上引入强类型系统而形成的扩展方法。在 STGP 中，程序树中的每个节点都与特定的数据类型相关联，且遗传算子的设计需要在整个进化过程中保持类型一致性。

引入强类型机制的主要优势在于，它能够通过排除无效程序或语义错误程序的生成来缩小搜索空间。通过施加类型约束，STGP 能够保证进化得到的程序在语法上正确，并符合预先规定的类型系统。

在初始化阶段，STGP 会生成由类型一致程序树构成的初始种群。交叉、变异等遗传算子也会被修改，以满足类型约束。例如，在两个父代程序之间执行交叉时，STGP 会确保交叉点处被交换的子树在类型上相互兼容。

STGP 中的适应度评估与标准遗传规划基本类似，即在一组训练数据上执行进化得到的程序，并依据预定义适应度函数评估其性能。不过，STGP 还可以在适应度评估中加入与类型相关的指标或惩罚项，以引导搜索朝类型正确的解发展。

过程

1. 初始化种群：
   1. 为每一种数据类型定义对应的函数集和终端集。
   2. 根据各自的数据类型，通过随机选择函数和终端，创建由类型一致程序树构成的种群。
2. 评估种群中每个个体的适应度：
   1. 在训练数据上执行每棵程序树。
   2. 根据程序的性能以及其对类型约束的满足情况计算适应度得分。
3. 重复执行遗传操作，直到满足终止条件：
   1. 选择：根据适应度得分从种群中选择父代个体。
   2. 交叉：
      1. 在每个父代程序树中随机选择一个交叉点。
      2. 交换交叉点处的子树，并确保交换后的子树在类型上兼容。
   3. 变异：
      1. 在程序树中随机选择一个节点。
      2. 用一个具有相同数据类型的随机生成子树替换该节点。
   4. 通过将新生成的子代与上一代中的精英个体结合，形成新一代种群。
4. 返回最终一代中表现最优的个体作为问题的解。

数据结构

• 程序树：表示进化程序的层次化结构，其中每个节点都关联一个特定的数据类型。
• 函数集：针对每一种数据类型定义的一组函数，用作程序树中的内部节点。
• 终端集：针对每一种数据类型定义的一组变量、常数和零元函数，用作程序树中的叶节点。
• 适应度函数：衡量程序在给定问题上的性能，同时考虑程序输出结果及其对类型约束的满足情况。

参数

• 种群规模：每一代中的个体数量。
• 迭代代数：进化过程允许执行的最大迭代次数。
• 交叉率：在两个父代程序之间执行交叉的概率。
• 变异率：对单个程序应用变异的概率。
• 锦标赛规模：参与锦标赛选择的个体数量。
• 精英保留数：直接复制到下一代且不参与遗传操作的最优个体数量。

注意事项

优点

• 通过消除无效程序或语义错误程序的生成，提高了搜索效率。
• 由于施加了类型约束，进化得到的程序通常具有更好的可读性与可解释性。
• 能够利用领域相关的类型信息，使搜索更加有针对性且更有效。

缺点

• 为保持类型一致性，遗传算子的实现复杂度更高。
• 严格的类型约束可能限制进化程序的表达能力。
• 需要为每一种数据类型预先定义良好的类型系统以及相应的函数集和终端集。

启发式建议

函数集与终端集

• 应确保每种数据类型对应的函数集和终端集具有足够的表达能力，以求解给定问题。
• 应包含多样化的函数和终端，以支持复杂且有意义程序结构的进化。
• 可考虑引入领域特定的函数和终端，以刻画与问题相关的重要特征和操作。

遗传算子

• 应根据问题复杂度以及探索与开发之间所需的平衡，对交叉率和变异率进行调整。
• 可尝试不同的选择方法，如锦标赛选择或基于排序的选择，以维持种群多样性并防止过早收敛。
• 可采用精英保留策略，以在代际演化过程中保留表现最优的个体，避免优良解丢失。

种群规模与代数

• 应依据问题复杂度和可用计算资源设定合适的种群规模。
• 迭代代数应设置得足够大，以便演化出有效解，但同时要避免不必要的计算开销。
• 应监测种群收敛情况，并可考虑设置早停准则以避免无效迭代。

适应度评估

• 应设计能够准确刻画进化程序期望行为与性能的适应度函数。
• 可在适应度评估中加入与类型相关的指标或惩罚项，以引导搜索朝类型正确的解演化。
• 对于复杂问题，可考虑在适应度函数中引入多目标或约束条件。

参数调优

• 可通过经验实验识别关键参数（如种群规模、交叉率、变异率）的较优取值。
• 可利用网格搜索、随机搜索或进化参数优化等方法，对参数进行自动调优。
• 在选择参数时，应综合权衡计算效率与解质量之间的关系。