动态克隆选择（DCS）

名称

动态克隆选择（Dynamic Clonal Selection, DCS）

分类

查看分类思维导图

动态克隆选择是一种基于种群的元启发式优化技术，属于生物启发计算领域中的人工免疫系统范畴。它与克隆选择算法（Clonal Selection Algorithm, CSA）和人工免疫识别系统（Artificial Immune Recognition System, AIRS）密切相关。

• 计算智能
  • 生物启发计算
    • 人工免疫系统
      • 克隆选择算法
        • 动态克隆选择（DCS）

策略

动态克隆选择是一种受生物系统适应性免疫响应启发的种群型优化算法。该算法维持一个由候选解构成的种群，这些候选解被称为抗体，并通过迭代不断优化，以搜索给定问题的最优解。

克隆选择与扩增

DCS 算法的核心在于克隆选择与扩增过程。在每次迭代中，算法依据抗体对当前问题的亲和力（适应度）进行选择。被选中的抗体会经历克隆扩增，其生成的克隆数量与其亲和力成正比。这一机制使算法能够重点探索搜索空间中更具潜力的区域。

亲和力成熟

在克隆扩增之后，克隆体会经历亲和力成熟过程，该过程主要包括两个环节：高频变异和受体编辑。高频变异会对克隆体施加随机扰动，且变异率与父代抗体的亲和力成反比，从而能够在高亲和力解附近开展局部搜索。另一方面，受体编辑会对部分克隆体引入幅度更大的变化，以增强种群多样性并促进对新区域的探索。

种群更新

在亲和力成熟之后，算法对克隆体进行评估，并将其亲和力与原始抗体进行比较。若某个克隆体的亲和力高于其父代抗体，则用该克隆体替换父代个体。此外，算法还会用随机生成的抗体替换低亲和力抗体，以维持种群多样性并防止早熟收敛。

动态参数调整

DCS 的一个关键特征在于，会根据搜索过程的进展动态调整算法参数。克隆扩增率、高频变异率以及执行受体编辑的克隆比例都会在优化过程中自适应变化。这种动态机制使算法能够在探索与开发之间实现更好的平衡，从而增强其跳出局部最优并逐步逼近全局最优解的能力。

过程

数据结构

• 抗体（Antibody）：表示优化问题中的一个候选解。每个抗体都具有一个对应的亲和力值，用于表征其适应度。
• 种群（Population）：由多个抗体组成的集合，并在优化过程中不断演化。

参数

• 种群规模（Population Size）：种群中抗体的数量。
• 克隆扩增率（Clonal Expansion Rate）：决定每个被选中抗体生成的克隆数量。
• 高频变异率（Hypermutation Rate）：控制亲和力成熟过程中施加于克隆体的变异程度。
• 受体编辑率（Receptor Editing Rate）：指定执行受体编辑的克隆体比例。
• 替换阈值（Replacement Threshold）：决定低亲和力抗体是否被替换的亲和力阈值。

算法步骤

1. 随机初始化抗体种群。
2. 计算种群中每个抗体的亲和力。
3. 当停止准则尚未满足时，重复步骤 4–10。
4. 选择一部分高亲和力抗体进行克隆扩增。
5. 为每个被选中的抗体生成克隆体，克隆数量与该抗体的亲和力成正比。
6. 对克隆体执行亲和力成熟：
   1. 对每个克隆体施加高频变异，且变异率与父代抗体的亲和力成反比。
   2. 对部分克隆体执行受体编辑。
7. 评估克隆体的亲和力。
8. 比较每个克隆体与其父代抗体的亲和力。若克隆体的亲和力更高，则用其替换父代抗体。
9. 用随机生成的抗体替换种群中的低亲和力抗体。
10. 根据搜索进展动态调整算法参数（克隆扩增率、高频变异率、受体编辑率）。
11. 返回亲和力最高的抗体，作为搜索得到的最优解。

注意事项

优点

• 能够适应搜索景观：DCS 会根据搜索进展动态调整参数，因此能够更好地适应问题景观的特征。
• 能够平衡探索与开发：克隆选择、高频变异和受体编辑的结合，使 DCS 既能够有效探索搜索空间，又能够充分开发潜在优良区域。
• 能够维持种群多样性：通过用随机生成的抗体替换低亲和力个体，算法能够保持多样性并抑制早熟收敛。

缺点

• 参数敏感性较强：DCS 的性能可能对参数初值较为敏感，因此通常需要针对具体问题进行仔细调参。
• 计算复杂度较高：克隆扩增和亲和力成熟过程可能带来较高的计算开销，尤其是在种群规模较大或问题维度较高时更为明显。
• 缺乏理论收敛保证：与许多元启发式算法类似，DCS 通常无法提供收敛到全局最优解的严格理论保证。

启发式建议

参数设置

• 种群规模：应根据问题复杂度设置种群规模。较大的种群有利于覆盖更广的搜索空间，但也会增加计算成本。
• 克隆扩增率：可在初始阶段设定较高的克隆扩增率，以增强探索能力；随后随着优化过程推进逐步降低，从而更侧重开发。
• 高频变异率：可根据预期所需的多样性水平设定初始高频变异率，并根据搜索进展动态调整该参数。
• 受体编辑率：可采用较低的受体编辑率（如 0.1–0.2），以在不过度破坏搜索过程的前提下引入多样性。
• 替换阈值：应合理设置替换阈值，以在保留高亲和力解与促进多样性之间取得平衡。

问题表示

• 应将问题相关信息合理编码到抗体表示中，并确保该表示方式支持有意义的变异与评估操作。
• 在条件允许的情况下，可采用便于融入问题特定知识和约束的信息表示方式。

亲和力函数设计

• 应设计能够准确衡量候选解质量的亲和力函数，使其与优化问题目标保持一致。
• 由于亲和力函数在优化过程中会被频繁调用，因此还应保证其计算效率。

停止准则

• 应根据具体问题需求设计合适的停止准则，例如最大迭代次数、目标亲和力值或某种收敛度量。
• 应持续监测搜索进展；若算法明显停滞，或计算预算有限，则可考虑提前终止。

混合化

• 可考虑将 DCS 与其他优化技术相结合，例如局部搜索方法或其他元启发式算法，以提升其在特定问题上的性能。
• 也可融入问题特定的启发式策略或算子，以增强搜索过程并更充分地利用领域知识。