清除法（CGA）

名称

清除遗传算法（Clearing Genetic Algorithm, CGA），清除法（Clearing）

分类

查看分类思维导图

清除遗传算法是经典遗传算法的一种变体，隶属于进化计算（Evolutionary Computation）领域；而进化计算又是计算智能（Computational Intelligence）与生物启发计算（Biologically Inspired Computation）的一个分支。该算法与拥挤法（Crowding）、适应度共享（Fitness Sharing）等其他小生境方法密切相关。

• 计算智能
  • 生物启发计算
    • 进化计算
      • 进化算法
        • 遗传算法
          • 小生境方法
            • 清除遗传算法

策略

清除遗传算法在标准遗传算法的基础上引入清除机制，以维持种群多样性并防止过早收敛。其核心思想是依据个体之间的相似性，将种群划分为若干子种群或小生境。

小生境形成

个体依据某种相似性度量被划分到不同的小生境中，该相似性通常由搜索空间中的距离度量来定义。通过这种方式，可以识别出不同的子种群，从而使其能够并行探索搜索空间中的不同区域。

清除过程

在每个小生境内部，最优个体（即支配个体或获胜者）的适应度得以保留，而其余个体（从属个体）的适应度被重置为零。该清除过程实质上消除了小生境内部的竞争，使得优势个体能够存活并传播其遗传信息。

小生境维持

清除过程会以固定时间间隔（即清除轮次）周期性地执行，以在整个进化过程中维持小生境结构。这有助于保持种群多样性，并防止某一个小生境主导整个种群。

通过引入清除机制，清除遗传算法能够促进稳定小生境的形成与维持，从而并行探索多个最优解。这使其特别适用于多峰优化问题，因为在此类问题中通常希望获得多个优良解。

过程

数据结构

• 个体（Individual）：表示一个候选解的数据结构，其组成包括：
  • 基因型（Genotype）：表示解的遗传编码的数组或字符串。
  • 适应度（Fitness）：个体的适应度值。
• 种群（Population）：由多个个体构成的数组。
• 清除半径（Clearing Radius）：用于判定个体是否属于同一小生境或是否需要被清除的距离阈值。

参数

• 种群规模（Population Size）：种群中的个体数量。
• 最大迭代代数（Maximum Number of Generations）：算法运行的最大代数。
• 交叉概率（Crossover Probability）：应用交叉算子生成后代的概率。
• 变异概率（Mutation Probability）：应用变异算子修改个体的概率。
• 清除半径（Clearing Radius）：用于判定个体小生境归属或清除操作的距离阈值。
• 小生境容量（Niche Capacity）：每个小生境中允许保留的最大个体数。

步骤

1. 初始化种群
   1. 对种群中的每个个体：
      1. 随机初始化其基因型。
      2. 计算该个体的适应度。
2. 对每一代，重复执行直至达到最大迭代代数：
   1. 创建新种群
      1. 当新种群未满时：
         1. 使用某种选择方法（如锦标赛选择）选取父代个体。
         2. 利用遗传算子生成后代
            1. 若随机数小于交叉概率：
               1. 对所选父代执行交叉操作，生成两个后代。
            2. 若随机数小于变异概率：
               1. 对后代执行变异操作。
         3. 计算后代个体的适应度。
         4. 将后代加入新种群。
   2. 执行清除过程
      1. 按适应度值从高到低对种群个体进行排序。
      2. 对排序后的每个个体：
         1. 若该个体尚未被清除：
            1. 将该个体标记为小生境获胜者。
            2. 清除位于该获胜者清除半径范围内的个体。
               1. 对于每一个位于清除半径内的个体：
                  1. 若该小生境中的个体数量超过小生境容量：
                     1. 将该个体从种群中移除。
                  2. 否则：
                     1. 将该个体标记为已清除。
   3. 用新种群替换旧种群。
3. 返回种群中找到的最优个体。

注意事项

优点：

• 通过在进化过程中保留不同的小生境来维持种群多样性
• 通过允许并行探索多个最优解来防止过早收敛
• 适用于希望获得多个优良解的多峰优化问题

缺点：

• 由于额外引入清除过程，计算复杂度有所增加
• 需要定义合适的相似性度量和小生境半径，而这些通常依赖于具体问题
• 在高维搜索空间中，小生境的形成可能更加困难，因此算法效果可能受限

启发式建议

小生境半径的选择

• 小生境半径应根据问题特性及所期望的多样性水平进行设置
• 较小的小生境半径会产生更多小生境并提高多样性，而较大的半径则会导致小生境数量减少，并可能加快收敛速度
• 可通过实验调整不同取值，以在多样性与收敛速度之间取得平衡

清除间隔的设置

• 清除间隔决定了清除过程执行的频率
• 较大的清除间隔可使各小生境在被清除前有更多时间独立演化
• 较小的清除间隔则可更频繁地更新小生境，但可能降低整体收敛速度
• 应根据问题复杂度以及对多样性与收敛平衡的需求进行调整

种群规模与小生境容量

• 种群规模应足够大，以支持多个小生境的形成
• 应结合问题中预期最优解的数量，确保种群规模能够容纳所需数量的小生境
• 在进化过程中监测每个小生境中的个体数量（小生境容量），以保证各小生境得到充分表示

相似性度量的选择

• 应选择能够有效表征问题领域关键特征的相似性度量
• 常见的相似性度量包括欧氏距离（Euclidean Distance）、曼哈顿距离（Manhattan Distance）以及适用于二进制编码的汉明距离（Hamming Distance）
• 在选择相似性度量时，应结合问题性质与编码方式进行综合考虑

探索与开发的平衡

• 可通过调整交叉概率和变异概率来控制探索（exploration）与开发（exploitation）之间的平衡
• 较高的交叉概率有助于促进个体间遗传信息交换，从而增强探索能力
• 较高的变异概率能够引入新的遗传变异，从而进一步拓展搜索空间的探索范围
• 应寻求一种平衡，使算法在保持种群多样性的同时，能够有效开发有前景的搜索区域