自动函数定义遗传规划（ADF-GP）

名称

自动函数定义遗传规划（Automatic Function Definition Genetic Programming, AFDGP）

分类

查看分类思维导图

自动函数定义遗传规划（AFDGP）是遗传规划（Genetic Programming, GP）的一种变体，其核心特征是在进化过程中自动定义并演化可复用函数。它与模块化遗传规划（Modular Genetic Programming）和自适应表示遗传规划（Adaptive Representation Genetic Programming）密切相关。

• 人工智能
  • 计算智能
    • 生物启发计算
      • 进化计算
        • 遗传规划（GP）
          • 自动函数定义遗传规划（AFDGP）

策略

AFDGP 在标准遗传规划模型基础上引入了自动定义函数（Automatically Defined Functions, ADFs）的概念。ADF 与主程序树同时进化，并且可在主程序或其他 ADF 中被调用。这使得有价值的代码片段能够被复用，从而促进模块化解的演化。

在 AFDGP 的进化过程中，首先生成一个由多个个体构成的种群，其中每个个体表示为一个程序，该程序由一棵主程序树和一组 ADF 组成。主程序树与 ADF 通过交叉、变异等遗传操作同步演化。个体的适应度依据其在给定问题上的表现进行评估。

在演化过程中，ADF 可以被主程序树或其他 ADF 调用，从而形成分层式、模块化的解结构。该进化机制通过促进具有高性能 ADF 的个体的生存与传播，鼓励对有效代码片段的复用。

过程

数据结构

• 函数集：用于构造程序树的原始函数与算子集合。
• 终端集：作为程序树叶节点的变量与常数集合。
• 个体：表示候选解的数据结构，其组成包括：
  • 主程序树：表示主程序的树结构。
  • 自动定义函数（ADFs）：表示自动定义函数的树结构数组。
  • 适应度：个体的适应度值。
• 种群：由多个个体构成的数组。

参数

• 种群规模：种群中个体的数量。
• 最大代数：算法运行的最大迭代代数。
• 交叉概率：应用交叉算子生成子代的概率。
• 变异概率：应用变异算子修改个体的概率。
• 最大树深：程序树允许的最大深度。
• 最大 ADF 数量：每个个体允许包含的自动定义函数的最大数量。

步骤

1. 初始化种群
   1. 对种群中的每个个体：
      1. 创建主程序树
         1. 使用函数集和终端集随机生成一棵程序树。
         2. 确保树的深度不超过最大树深。
      2. 创建自动定义函数（ADFs）
         1. 对每一个 ADF（不超过最大 ADF 数量）：
            1. 使用函数集和终端集随机生成一棵程序树。
            2. 确保树的深度不超过最大树深。
      3. 评估该个体的适应度。
2. 对每一代重复以下过程，直到达到最大代数：
   1. 创建新种群
      1. 当新种群未填满时：
         1. 采用某种选择机制（如锦标赛选择）选择父代个体。
         2. 使用遗传操作生成子代
            1. 若随机数小于交叉概率：
               1. 对所选父代应用交叉算子。
                  1. 在父代的主程序树和 ADF 树中随机选择交叉点。
                  2. 交换所选交叉点处的子树，以生成两个子代。
            2. 若随机数小于变异概率：
               1. 对子代应用变异算子。
                  1. 在子代的主程序树和 ADF 树中随机选择变异点。
                  2. 用随机生成的子树替换所选变异点处的子树。
         3. 评估子代的适应度。
         4. 将子代加入新种群。
   2. 用新种群替换旧种群。
3. 返回种群中找到的最优个体。

注意事项

优点：

• 能够自动发现并复用有价值的代码片段。
• 有利于模块化与层次化解的进化。
• 相较于标准遗传规划，通常可得到更紧凑且更具可解释性的解。

缺点：

• 由于需要管理 ADF，算法复杂度有所增加。
• 相较于标准 GP，计算代价更高。
• ADF 的最优数量与结构通常具有问题依赖性。

启发式建议

参数设置

• 根据问题复杂度设置种群规模。较大的种群有助于维持多样性，但会增加计算成本。
• 根据可用计算资源和问题难度调整最大代数。
• 设置合适的交叉概率与变异概率，以平衡探索与开发。典型取值范围为：交叉概率 0.7 至 0.9，变异概率 0.01 至 0.1。
• 限制最大树深，以防止解结构过度膨胀。通常 5 到 10 的树深已较为合适。
• 初始时可采用较少数量的 ADF（如 1 到 3 个），并在需要时逐步增加。过多的 ADF 容易导致程序膨胀并降低可解释性。

函数集与终端集

• 在主程序树和 ADF 中纳入与具体问题相关的函数和终端。
• 确保函数集与终端集具有足够的表达能力，以支持目标问题的求解。
• 可考虑引入更高层次的原语或领域特定算子，以提升解质量和收敛速度。

ADF 管理

• 可通过对有效利用 ADF 的个体给予适应度奖励，促进 ADF 的复用。
• 应设计机制抑制 ADF 的过度增长，例如设置规模限制或引入简约压力（parsimony pressure）。
• 允许具有不同元数（参数个数）的 ADF 共同进化，以增强模型的灵活性与适应性。

多样性维持

• 可采用物种划分（speciation）或小生境（niching）等技术维持种群多样性，防止过早收敛。
• 可考虑采用多目标优化方法，以平衡解的适应度与多样性。

面向问题的适应性改进

• 应针对目标问题设计适当的适应度函数，以有效刻画期望行为并引导进化过程。
• 可融入领域知识或问题特定启发式，以提升搜索效率与解的质量。
• 如有必要，可尝试不同的表示方式或 AFDGP 扩展形式，例如强类型遗传规划（strongly typed GP）或语法进化（grammatical evolution）。