协同进化共享小生境（CSN）

名称

协同进化共享小生境（Coevolutionary Shared Niching，CSN）

分类

查看分类思维导图

协同进化共享小生境是一种隶属于进化计算（Evolutionary Computation）领域的技术，而进化计算又是计算智能（Computational Intelligence）的一个分支。该方法与其他协同进化算法（coevolutionary algorithms）密切相关，例如合作协同进化（Cooperative Coevolution）和竞争协同进化（Competitive Coevolution）。

• 计算智能
  • 进化计算
    • 进化算法
      • 遗传算法
      • 协同进化算法
        • 合作协同进化
        • 竞争协同进化
        • 协同进化共享小生境

策略

协同进化共享小生境是一种结合协同进化与小生境机制思想的方法，其目标在于维持种群多样性并防止进化算法中的过早收敛。该算法维护多个子种群，其中每个子种群聚焦于搜索空间中的一个特定子问题或小生境。

子种群与小生境

在 CSN 中，种群被划分为若干子种群，每个子种群对应一个不同的小生境或子问题。这些子种群彼此独立演化，从而能够在各自的小生境中形成专门化搜索。这样的划分有助于保持种群多样性，并防止单一子种群主导整个搜索过程。

协同进化与交互

CSN 中的各个子种群以协同进化的方式共同演化，即它们通过相互作用影响彼此的演化过程。来自不同子种群的个体，其适应度评估不仅取决于自身表现，还取决于其相对于其他子种群个体的表现。这种交互构造出一种动态适应度景观，在该景观中，个体的适应度取决于其解决特定子问题的能力以及与其他子种群竞争或协作时的表现。

共享适应度与协作

CSN 引入了共享适应度（shared fitness）的概念，即个体的适应度不仅由其自身表现决定，还受到同一小生境内其他个体表现的影响。这种机制鼓励同一小生境中的个体之间形成协作，因为个体的成功在一定程度上依赖于整个小生境的整体表现。

小生境半径与拥挤控制

为了维持每个小生境内部的多样性，CSN 采用基于小生境半径（niche radius）的拥挤控制机制。小生境半径定义了判定个体是否属于同一小生境的距离阈值。当某一小生境中的个体数量超过预设上限时，拥挤控制机制会移除其中适应度较低的个体，以避免过度拥挤并维持种群多样性。

过程

数据结构

• 个体（Individual）：表示候选解的数据结构，包含：
  • 基因型（Genotype）：表示解遗传编码的数组或字符串。
  • 适应度（Fitness）：个体的适应度值。
  • 物种（Species）：个体所属的物种或类别。
• 种群（Population）：由多个个体构成的数组。
• 物种（Species）：由具有相似特征或属于同一小生境的个体构成的集合。
• 共享适应度（Shared Fitness）：个体在施加共享小生境机制之后得到的适应度值。

参数

• 种群规模（Population Size）：种群中个体的数量。
• 最大迭代代数（Maximum Number of Generations）：算法运行的最大代数。
• 交叉概率（Crossover Probability）：应用交叉算子生成后代的概率。
• 变异概率（Mutation Probability）：应用变异算子修改个体的概率。
• 小生境半径（Niche Radius）：用于判定个体之间是否进行适应度共享的距离阈值。
• 共享函数（Sharing Function）：根据个体间距离确定共享程度的函数。

步骤

1. 初始化种群
   1. 对种群中的每个个体：
      1. 随机初始化基因型。
      2. 评估该个体的适应度。
      3. 根据其特征将该个体划分到相应物种中。
2. 对每一代重复以下过程，直至达到最大迭代代数：
   1. 应用共享小生境机制
      1. 对每个物种：
         1. 计算该物种内各个体的共享适应度
            1. 对物种中的每个个体：
               1. 计算小生境计数（niche count）
                  1. 对种群中的其他每个个体：
                     1. 计算个体间距离。
                     2. 若该距离小于等于小生境半径：
                        1. 将该个体的小生境计数加一。
               2. 计算该个体的共享适应度
                  1. 用该个体的原始适应度除以其小生境计数。
   2. 创建新种群
      1. 当新种群未满时：
         1. 基于共享适应度采用某种选择方法（如锦标赛选择）选取父代个体。
         2. 使用遗传算子生成后代
            1. 若随机数小于交叉概率：
               1. 对选定父代执行交叉操作，生成两个后代。
            2. 若随机数小于变异概率：
               1. 对后代执行变异操作。
         3. 评估后代个体的适应度。
         4. 根据后代特征将其划分到相应物种中。
         5. 将后代加入新种群。
   3. 用新种群替换旧种群。
   4. 执行协同进化操作
      1. 在物种之间迁移个体
         1. 从每个物种中选取一部分个体。
         2. 根据其特征将所选个体迁移到不同物种中。
      2. 根据物种表现对物种结构进行自适应调整
         1. 评估每个物种的总体适应度。
         2. 根据其表现调整物种参数（例如小生境半径）。
         3. 在必要时创建新物种或合并已有物种。
3. 返回种群中找到的最优个体。

注意事项

优点

• 通过保留多个小生境来维持种群多样性
• 通过避免单一子种群占优来防止过早收敛
• 通过协同进化与共享适应度机制促进协作与专门化
• 能够高效探索复杂且多峰的搜索空间

缺点

• 由于需要在多个子种群之间进行个体评估，计算复杂度较高
• 需要对参数进行细致调节，例如子种群数量与小生境半径
• 在具有大量小生境或子问题重叠显著的问题中，算法可能面临困难
• 算法性能高度依赖于小生境定义是否合理以及拥挤控制机制是否有效

启发式建议

子种群数量的确定

• 应结合问题域中不同子问题或小生境的数量进行设定
• 可通过实验比较不同取值对种群多样性和收敛性的影响
• 较大的子种群数量通常有利于提升多样性，但也会增加计算开销

小生境半径的设置

• 小生境半径应足够大，以允许同一小生境内部存在一定程度的变异；同时又应足够小，以维持不同小生境之间的分离
• 应结合搜索空间规模以及不同子问题之间的预期距离加以设定
• 可采用自适应小生境半径技术，根据种群特征动态调整半径大小

拥挤上限的选择

• 拥挤上限应设置为能够在每个小生境内部平衡多样性与收敛性的水平
• 较高的拥挤上限允许每个小生境中保留更多个体，但也可能带来更激烈的竞争并降低收敛速度
• 可通过实验观察不同取值对种群多样性和收敛速度的影响

遗传算子的选择

• 应选择适合具体问题领域及个体编码方式的遗传算子
• 交叉算子应能够保留并重组父代中的有效构件（building blocks）
• 变异算子应引入足够的变异，以增强对搜索空间的探索能力

终止准则的定义

• 应结合所期望的解质量水平以及可用计算资源来设定终止条件
• 可设定最大迭代代数，或根据连续若干代适应度提升幅度设定收敛阈值
• 也可加入运行时间限制，以避免过度计算

重叠小生境的处理

• 若问题域中存在重叠小生境，可考虑采用更灵活的小生境定义方式或动态小生境半径
• 可通过共享适应度评估鼓励来自重叠小生境的个体之间进行协作
• 可结合适应度共享（fitness sharing）或拥挤机制（crowding）在小生境重叠情形下维持种群多样性