遗传网络规划（GNP）

名称

遗传网络规划（Genetic Network Programming, GNP）

分类

查看分类思维导图

遗传网络规划是一种将遗传算法与基于图的程序表示相结合，用于进化优化与学习的技术。它与遗传规划和进化算法密切相关。

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

策略

遗传网络规划将解表示为称作 GNP 个体的有向图结构。图中的每个节点都包含处理功能以及与其他节点的连接，从而能够执行复杂行为。图结构支持条件分支与迭代处理，因此为程序进化提供了一种灵活且具有较强表达能力的表示方式。

GNP 算法遵循进化过程来优化基于图的程序。它首先生成一个由随机 GNP 个体构成的初始种群。随后依据适应度函数对每个个体进行评估，适应度函数用于衡量其在给定任务上的表现。适应度较高的个体被选中参与繁殖，并通过交叉、变异等遗传操作生成新一代子代。该过程不断迭代，使每一代相较前一代逐步改进，直到找到满意解或满足终止条件。

GNP 的图结构使模块化和层次化程序的进化成为可能。节点可以表示高层功能或子任务，而节点之间的连接决定执行流程。这种模块化表示支持子程序复用，并能够通过组合较简单的组件演化出复杂行为。

过程

1. 初始化：
   1. 定义问题并指定适应度函数。
   2. 设置种群规模、交叉率、变异率及其他参数。
   3. 创建由随机 GNP 个体构成的初始种群。
2. 评估：
   1. 在给定任务上执行每个 GNP 个体。
   2. 根据其表现计算每个个体的适应度得分。
3. 选择：
   1. 根据适应度得分从种群中选择一个个体子集。
   2. 常用选择方法包括锦标赛选择、轮盘赌选择或基于排序的选择。
4. 繁殖：
   1. 交叉：
      1. 从选中的个体子集中随机选择成对的父代个体。
      2. 应用交叉算子，在父代个体之间交换遗传信息。
      3. 通过组合父代的遗传信息生成新的子代个体。
   2. 变异：
      1. 应用变异算子，在子代个体中引入随机变化。
      2. 变异可以修改节点功能、连接权重或图结构。
5. 替换：
   1. 用新生成的子代个体替换种群中的一部分个体。
   2. 常见替换策略包括整代替换或稳态替换。
6. 终止：
   1. 检查是否满足终止条件，例如达到最大代数或找到满意解。
   2. 若未满足条件，则返回步骤 2，继续进化过程。
   3. 若满足条件，则返回找到的最优 GNP 个体作为问题的解。

数据结构

• GNP 个体：将候选解表示为一个有向图。
  • 节点：包含处理功能以及与其他节点的连接。
  • 连接：表示节点之间的执行流程。
• 种群：存储多个 GNP 个体的集合。
• 适应度函数：用于评估 GNP 个体在给定任务上的表现。

参数

• 种群规模：每一代中 GNP 个体的数量。
• 交叉率：对一对父代个体应用交叉算子的概率。
• 变异率：对子代个体应用变异算子的概率。
• 最大代数：算法终止前允许的最大迭代次数。

注意事项

优点

• 灵活性：GNP 通过基于图的结构能够表示复杂程序和行为。
• 模块化：图表示支持模块化与层次化程序的进化。
• 表达能力强：GNP 能够进化出具有条件分支和迭代处理能力的程序。

缺点

• 计算复杂度高：对基于图的程序进行评估和进化可能计算代价较高。
• 参数调节困难：GNP 的性能依赖于参数的合理选择，通常需要通过实验进行调优。
• 可解释性较弱：进化得到的图结构可能较为复杂，难以解释。

启发式建议

种群规模

• 初始种群规模应足以提供用于搜索的多样性。
• 对于更复杂的问题或更大的搜索空间，可适当增大种群规模。
• 需要权衡计算资源消耗与种群多样性之间的关系。

交叉率与变异率

• 交叉率应设置得足够高，以促进个体之间遗传信息的交换。
• 变异率应保持相对较低，以避免破坏已有的优良解。
• 应根据问题复杂度以及期望的探索—开发平衡调整这两个概率。

图结构

• 初始图结构的设计应能够刻画问题的关键组成部分及其关系。
• 应允许图结构在进化过程中发生演化，从而发现新的解。
• 可考虑将领域知识或约束融入图表示之中。

适应度函数

• 应定义能够准确衡量 GNP 个体在给定任务上表现的适应度函数。
• 适应度函数应便于高效计算，并能为选择过程提供有意义的区分依据。
• 如有需要，可在适应度评估中纳入多目标或约束条件。

终止条件

• 应设置最大代数，以防止计算开销过大。
• 可基于适应度改进幅度或种群多样性定义收敛判据。
• 若已找到满意解，可提前终止算法。