链接树遗传算法（LTGA）

Goat_Yang2026/3/21约 1684 字大约 6 分钟

链接树遗传算法（LTGA）

名称

链接树遗传算法（Linkage-Tree Genetic Algorithm, LTGA），链接树遗传算法，LTGA

分类

查看分类思维导图

链接树遗传算法是一类遗传算法。遗传算法是一种基于种群的元启发式优化技术，其思想来源于自然选择与遗传机制；而遗传算法又隶属于更广义的进化计算领域，进化计算则是计算智能的重要分支之一。

计算智能
- 进化计算
  - 进化算法
    - 遗传算法
      - 链接树遗传算法

策略

问题分解

链接树遗传算法旨在解决优化过程中如何高效识别并利用问题变量之间链接关系（即依赖关系）的问题。其核心做法是构建一个关于变量链接结构的层次化模型，并将其表示为一棵树；随后利用该树来指导变异算子与交叉算子，使搜索过程能够尊重已识别出的依赖关系，并保留具有潜力的局部优良结构。

链接学习

链接树采用自底向上的方式构建：首先将每个变量视为一个叶节点，然后反复合并依赖关系最强的一对节点，直到最终形成唯一的根节点。变量之间的依赖程度通常通过某种链接函数来度量，例如互信息或卡方统计量，这些指标能够基于种群中变量的共现情况刻画变量之间关系的强弱。

变异算子

在链接树构建完成后，LTGA 会采用能够保持依赖结构的专门变异机制。其交叉操作通常采用基因池最优混合（Gene-Pool Optimal Mixing, GPOM）算子：从链接树中选取若干节点子集，并通过在两个父代解之间混合这些节点对应的遗传信息来生成子代。随后，再通过变异操作对子代施加随机扰动，以维持对新解区域的探索能力。

种群更新

LTGA 通常采用稳态种群更新策略，即在每一代中只用新生成的一部分子代替换当前种群中的部分个体。被替换个体的选择通常与适应度相关，适应度较差的个体具有更高的被替换概率。通过这一机制，种群能够在保持一定多样性的同时逐步提升整体质量。

流程

数据结构：

种群：一组候选解，每个候选解表示为定长决策变量向量。
链接树：一种用于表示变量依赖关系的层次结构，其中叶节点对应单个变量，内部节点对应具有依赖关系的变量组。

参数：

种群规模：种群中候选解的数量。
子代规模：每一代中生成的子代数量。
链接函数：用于度量变量依赖关系的方法，如互信息、卡方统计量等。
混合算子：利用链接树中选定节点的遗传信息生成子代的算子，如基因池最优混合（GPOM）。
变异率：对子代中每个变量施加变异的概率。
终止条件：算法停止运行的判据，如最大代数或收敛阈值。

流程：

随机初始化种群。
计算种群中每个候选解的适应度值。
当未满足终止条件时，重复步骤 4–9。
利用选定的链接函数构建链接树。
1. 将每个变量初始化为一个叶节点。
2. 反复合并依赖关系最强的一对节点，直到形成唯一根节点。
利用混合算子生成子代。
1. 从链接树中选取若干节点子集。
2. 在两个父代之间混合这些节点对应的遗传信息，以生成子代。
按照设定的变异率对子代执行变异。
计算子代的适应度值。
通过用子代替换适应度较差的个体来更新种群。
若满足终止条件，则返回当前找到的最优解；否则转到步骤 4。

注意事项

优点：

能够有效识别并利用问题变量之间的依赖关系，从而提升优化效率。
在变异与重组过程中尊重已识别出的依赖结构，因此能够更好地保留优良局部结构。
适用于具有复杂变量交互关系的多类优化问题。

缺点：

构建链接树的计算代价较高，尤其在高维问题中更为明显。
算法性能较大程度上依赖于链接函数的选择以及链接学习结果的准确性。
在参数设置和链接函数选取上，可能需要一定的问题相关知识支持。

启发式建议

种群规模与子代规模

种群规模应足够大，以维持多样性并有效探索搜索空间；通常可设在 50 到 1000 之间，具体取值取决于问题复杂度。
子代规模通常取种群规模的一部分，常见范围为 10% 到 50%，以平衡探索与开发。

链接函数选择

互信息和卡方统计量是较常用的链接函数，能够较好刻画变量之间的非线性依赖关系。
链接函数的选择应结合具体问题特征以及预期的变量交互类型进行确定。

混合算子配置

基因池最优混合（GPOM）是 LTGA 中较常用的算子，因为它能够有效重组具有潜力的局部优良结构。
参与混合的节点数量应在保护优良模块与引入足够多样性之间取得平衡，通常可取链接树节点数的 10% 到 50%。

变异率

变异率应设置得足够低，以避免破坏已获得的优良解；同时又应足够高，以维持多样性并防止早熟收敛。
一个常见的初始经验范围是 $1/N$ 到 $1/\sqrt{N}$ ，其中 $N$ 表示问题规模（变量个数）。

终止条件

最大代数应根据可用计算资源与目标解质量要求进行设定，常见范围为 100 到 10,000 代。
当最优适应度值或种群多样性在连续若干代内（如 50–100 代）未出现显著改善时，可判定算法收敛并停止运行。