笛卡尔遗传规划（CGP）

名称

笛卡尔遗传规划（Cartesian Genetic Programming, CGP）

分类

查看分类思维导图

笛卡尔遗传规划是一种进化算法，属于遗传规划（Genetic Programming）领域；遗传规划是进化计算（Evolutionary Computation）的一个分支，而进化计算又隶属于计算智能（Computational Intelligence）。

• 计算智能
  • 进化计算
    • 进化算法
      • 遗传算法
      • 进化策略
      • 进化规划
      • 遗传规划
        • 树式遗传规划
        • 线性遗传规划
        • 图式遗传规划
          • 笛卡尔遗传规划

策略

CGP 采用由节点笛卡尔坐标编码的有向无环图来表示计算结构。其基因型对程序图进行编码，其中每个节点表示一个特定函数，节点之间的边表示数据流动关系。基因型采用定长表示，这使得演化程序的复杂度能够被限制在有界范围内。

CGP 的进化过程通过对个体种群反复施加遗传操作来实现，例如变异和交叉。每个个体的适应度依据其在给定任务上的表现进行评估，随后选择适应度较高的个体进行繁殖，从而形成下一代种群。

CGP 的一个关键特征是其隐式冗余性，即基因型中的某些节点可能并未连接到输出节点，因此不会对最终程序产生贡献。这种冗余性使中性变异成为可能，从而有助于维持遗传多样性并促进对搜索空间的探索。

过程

数据结构：

• 基因型：用定长整数数组表示程序图，其中每个基因编码一个节点的函数及其连接关系。
• 表型：由基因型解码得到并实际执行以求解给定问题的程序图。

参数：

• 种群规模：每一代中个体的数量。
• 变异率：繁殖过程中基因发生变异的概率。
• 进化代数：进化过程允许执行的最大迭代次数。
• 函数集：用于构造程序图的原始函数集合。

过程：

1. 初始化：
   1. 创建由随机生成基因型构成的初始种群。
   2. 将每个基因型解码为其对应的表型（程序图）。
   3. 通过在给定问题上执行表型来评估每个个体的适应度。
2. 进化：
   1. 根据适应度选择父代个体用于繁殖（例如锦标赛选择）。
   2. 对选定父代施加遗传操作以生成子代：
      1. 变异：以给定变异率随机修改基因型中的基因。
      2. 交叉（可选）：在两个父代基因型之间交换遗传物质以生成子代。
   3. 将子代基因型解码为其对应的表型。
   4. 通过在给定问题上执行子代表型来评估其适应度。
   5. 用子代替换种群中适应度最低的个体。
3. 终止：
   1. 重复执行进化过程（步骤 2），直到满足终止条件，例如达到最大进化代数或找到适应度令人满意的解。
   2. 返回进化过程中找到的最优个体（程序图）作为问题的解。

注意事项

优点：

• 表示灵活：CGP 能够表示多种计算结构，可应用于电路设计、图像处理和机器学习等多个领域。
• 隐式冗余：基因型中非活跃节点的存在使中性变异成为可能，这有助于维持遗传多样性并促进对搜索空间的探索。
• 可扩展性：CGP 通过定长基因型演化复杂程序，因此在计算上具有较高效率，并能扩展到更大规模的问题实例。

缺点：

• 基因型—表型映射复杂：CGP 中基因型与表型之间的映射关系较为复杂，这可能使演化程序的解释与分析变得困难。
• 参数敏感性：CGP 的性能可能对参数选择较为敏感，例如变异率和函数集规模，因此通常需要针对具体问题进行细致调参。
• 交叉有效性有限：由于采用定长基因型，并且交叉可能破坏重要子图，相较于其他进化算法，交叉算子在 CGP 中的效果可能较弱。

启发式建议

函数集选择：

• 应选择能够表达给定问题所需结构、但又不过于复杂的函数集，以避免不必要的计算开销。
• 应纳入与问题领域相关、能够捕捉数据中重要特征或模式的函数。
• 可考虑混合使用算术函数、逻辑函数和领域特定函数，以支持多样化的程序结构。

变异率：

• 可从 1% 到 5% 的变异率开始，并依据问题复杂度以及对探索与开发平衡的需求进行调整。
• 较高的变异率有助于维持遗传多样性并防止过早收敛，但也可能减缓向最优解收敛的速度。
• 较低的变异率可能带来更快的收敛速度，但会增加陷入局部最优的风险。

种群规模：

• 种群规模应足够大，以维持遗传多样性并有效探索搜索空间，但也不宜过大，以免显著增加计算成本。
• 对于 CGP，典型的种群规模通常在 50 到 1000 个个体之间，具体取决于问题复杂度和可用计算资源。
• 对于适应度景观较平滑的问题，可考虑采用较小种群规模并配合较多进化代数；而对于适应度景观较崎岖的问题，则可考虑采用较大种群规模并配合较少进化代数。

基因型长度：

• 应选择能够支持演化程序具有足够复杂性以求解目标问题、但又不会使搜索空间无谓扩张的基因型长度。
• 可从与问题输入数和输出数相关的某个倍数长度开始设置，并根据所需程序复杂度进行调整。
• 可考虑使用动态基因型长度，使其在进化过程中依据个体适应度或搜索进展进行增减。