克隆选择算法（CLONALG）

名称

CLONALG，克隆选择算法（Clonal Selection Algorithm）

分类

查看分类思维导图

克隆选择算法（CLONALG）是一种受生物机制启发的计算方法，隶属于人工免疫系统（Artificial Immune Systems, AIS）与计算智能（Computational Intelligence）范畴。它与其他免疫启发式算法关系密切，例如否定选择（Negative Selection）和免疫网络理论（Immune Network Theory）。

• 计算智能
  • 生物启发计算
    • 人工免疫系统（AIS）
      • 克隆选择算法（CLONALG）
      • 否定选择
      • 免疫网络理论

策略

CLONALG 受自适应免疫系统中克隆选择原理的启发：能够最好识别抗原的 B 细胞会被选择出来进行克隆和高频变异，从而产生高亲和力抗体。在计算模型中，抗体表示候选解，而抗原则表示待求解或待优化的问题。

该算法首先初始化一个候选解种群（抗体种群），并依据问题特定的目标函数评估其适应度（亲和力）。随后，选择其中表现最优的解进行克隆，且克隆数量与其适应度成正比。这些克隆体接着经历高频变异，其变异率与父代抗体的适应度成反比。由此，算法能够在探索与开发之间实现平衡：高亲和力解因变异较少而更适于局部精细搜索，而低亲和力解因变异较多而更适于全局搜索。

在高频变异完成后，对克隆体进行重新评估，并选取其中表现最优者替换原始种群中表现较差的个体。该过程重复执行，直到达到预设迭代次数或满足停止准则。最终得到的一组高亲和力抗体即对应于问题的优良解。

CLONALG 还包含一种维持种群多样性的机制，即在每次迭代中引入新的随机抗体，以替换部分最差个体。这一机制有助于防止过早收敛，并促使算法探索解空间中的不同区域。

过程

数据结构：

• 抗体（Antibody）：表示问题的一个候选解
• 种群（Population）：由多个抗体构成的集合
• 克隆体（Clone）：抗体的复制体，并在后续经历高频变异

参数：

• 种群规模（Population Size）：种群中抗体的数量
• 克隆规模（Clone Size）：每个被选中抗体可生成的最大克隆数
• 变异率（Mutation Rate）：克隆体发生变异的概率（通常与适应度成反比）
• 替换比例（Replacement Ratio）：每次迭代中被新的随机抗体替换的种群比例
• 最大迭代次数（Max Iterations）：算法终止前允许的最大迭代次数

步骤：

1. 随机初始化抗体种群
2. 评估每个抗体的适应度（亲和力）
3. 重复以下过程，直到满足停止准则：
   1. 根据适应度选择最优抗体
   2. 对每个被选中的抗体：
      1. 按其适应度比例生成克隆体
      2. 对克隆体进行高频变异，且变异率与适应度成反比
      3. 评估克隆体的适应度
      4. 选择最优克隆体替换其父代抗体
   3. 用新的随机抗体替换一部分最差抗体
   4. 评估新抗体的适应度
4. 返回找到的最优抗体作为问题解

注意事项

优点：

• 通过克隆与高频变异的协同作用，能够有效兼顾解空间的探索与开发
• 能够维持种群多样性，降低早熟收敛风险
• 天然具备并行性，适用于分布式优化和多目标优化问题

缺点：

• 需要对种群规模、克隆规模和变异率等参数进行细致调节，才能获得较优性能
• 由于存在克隆与高频变异过程，计算开销可能较大
• 算法性能较大程度依赖于亲和力函数的设计，而该函数通常具有较强的问题相关性，并可能需要领域知识支持

启发式建议

参数选择：

• 种群规模（Population Size）：通常设置在 10 到 100 之间，具体取决于问题复杂度。较大的种群能够覆盖更广的搜索空间，但计算代价也更高。
• 克隆规模（Clone Size）：通常与种群规模及父代抗体亲和力成正比。高亲和力抗体应生成更多克隆，以便进行局部精细优化。
• 变异率（Mutation Rate）：通常与父代抗体亲和力成反比。高亲和力抗体应采用较低变异率，以保留其优良特性；低亲和力抗体则应采用较高变异率，以增强搜索能力。
• 替换比例（Replacement Ratio）：通常设为种群规模的 10% 至 30%。较高的替换比例能够增强多样性，但也可能减缓收敛速度。

亲和力函数设计：

• 亲和力函数应能够准确刻画候选解相对于问题目标的优劣程度。
• 对于多目标问题，可考虑采用 Pareto 支配关系或加权聚合等方法，将多个目标整合为单一亲和力值。
• 应对亲和力数值进行归一化处理，以保证抗体之间比较的公平性。

多样性维持：

• 可在每次迭代中引入新的随机抗体，以维持种群多样性并防止早熟收敛。
• 可考虑采用汉明距离（Hamming Distance）或欧氏距离（Euclidean Distance）等多样性度量，确保新抗体与现有抗体之间具有足够差异。
• 可依据种群当前的多样性水平动态调整替换比例。当多样性较低时，可适当提高该比例，以引入更多新抗体。

停止准则：

• 应根据问题复杂度和可用计算资源设置最大迭代次数。
• 可监测最优亲和力值的变化情况；若在连续若干次迭代中无明显提升（例如达到最大迭代次数的 10%），则可提前终止。
• 对于已知最优解的问题，当最优亲和力达到预设阈值，或与最优值之间误差处于容许范围内时，可停止算法。