序贯小生境法（SN）

名称

序贯小生境法（Sequential Niching）、序贯小生境方法（Sequential Niche Method，SNM）

分类

查看分类思维导图

序贯小生境法是一种属于进化计算（Evolutionary Computation）领域的技术，而进化计算是计算智能（Computational Intelligence）的一个分支。该方法与适应度共享（Fitness Sharing）、拥挤法（Crowding）等小生境方法密切相关。

• 人工智能
  • 计算智能
    • 进化计算
      • 进化算法
        • 小生境方法
          • 序贯小生境法

策略

序贯小生境法是一种用于维持种群多样性并促进进化算法搜索多个最优解的方法。其基本思想是反复对种群应用标准进化算法：每次运行定位一个最优解，然后将该最优解从搜索空间中“移除”，以便算法能够继续搜索其他最优解。

序贯小生境法的核心思想在于，在每次成功找到一个最优解后，对适应度景观进行修改。该修改的目的是使先前找到的最优解区域不再对后续搜索具有吸引力，从而迫使算法转向搜索空间中的其他区域。

适应度修改

适应度修改步骤是序贯小生境法得以发挥作用的关键。在定位到某个最优解之后，需要对该最优解邻域内的适应度函数进行调整。通常的做法是降低该区域内的适应度值，使其在后续搜索中不再具有优势。

适应度修改可以采用多种方式。例如，可以使用适应度共享（fitness sharing），即根据种群个体与已找到最优解之间的相似程度降低其适应度；另一种常见方式是直接修改适应度函数本身，在已找到最优解附近加入一个以该最优解为中心的“惩罚项”（penalty term）。

迭代与终止

序贯小生境法在“运行进化算法”与“修改适应度景观”两个步骤之间交替迭代。每一轮迭代通常期望找到一个最优解，而该最优解将在后续迭代中被排除出重点搜索范围。

当已找到的最优解数量达到预设值，或进化算法在给定迭代次数内未能找到新的最优解时，整个过程终止。此时，算法输出在整个搜索过程中所定位到的最优解集合。

过程

1. 将已定位最优解集合初始化为空集。
2. 当终止条件未满足时，重复以下步骤：
   1. 初始化一个个体种群。
   2. 在该种群上运行标准进化算法：
      1. 评估每个个体的适应度。
      2. 选择父代个体用于繁殖。
      3. 应用遗传算子（交叉与变异）生成后代。
      4. 用后代替换当前种群。
      5. 若标准进化算法的停止条件满足，则进入下一步；否则返回步骤 2.2.1。
   3. 将最终种群中的最优个体识别为一个已定位最优解。
   4. 若该最优解与先前已定位的各个最优解具有足够差异，则将其加入已定位最优解集合；否则将其丢弃。
   5. 修改适应度景观，以“移除”该已定位最优解：
      1. 在该最优解周围定义一个区域。
      2. 降低该区域内个体的适应度值，或直接修改适应度函数，在该区域中加入惩罚项。
3. 返回已定位最优解集合。

数据结构

• 种群（Population）：由多个个体构成的数组，其中每个个体表示问题的一个潜在解。
• 已定位最优解集合（Located Optima）：用于存储搜索过程中已经找到的最优解的数组。

参数

• 种群规模（Population Size）：种群中的个体数量。
• 进化算法参数（Evolutionary Algorithm Parameters）：所采用进化算法对应的参数，如选择方法、交叉概率和变异概率等。
• 适应度修改参数（Fitness Modification Parameters）：控制适应度修改过程的参数，例如每个已定位最优解周围区域的大小，以及适应度降低的幅度。
• 终止条件（Termination Criteria）：序贯小生境过程停止的判据，例如待定位最优解的最大数量，或在若干次迭代内未找到新最优解时停止。

注意事项

优点

• 能够有效定位多个最优解：序贯小生境法专门面向搜索空间中多个最优解的发现，因而适用于多峰优化问题。
• 能够维持种群多样性：通过迭代地修改适应度景观，序贯小生境法促使种群不断探索搜索空间中的不同区域，从而保持多样性。
• 适应度修改方式具有可定制性：适应度修改步骤可以根据具体问题特征及适应度景观性质进行灵活设计。

缺点

• 计算复杂度较高：相较于标准进化算法，序贯小生境法由于需要多轮迭代运行并在每轮结束后修改适应度景观，因此通常具有更高的计算开销。
• 对适应度修改参数较敏感：序贯小生境法的性能可能对适应度修改参数较为敏感，例如最优解邻域大小以及适应度降低幅度。
• 受底层进化算法性能限制：序贯小生境法的有效性最终依赖于底层进化算法本身的搜索能力。若底层进化算法难以在原始适应度景观中有效定位最优解，则序贯小生境法也可能表现不佳。

启发式建议

种群规模

• 应采用足够大的种群规模，以保持多样性并有效探索搜索空间；但也不宜过大，以免牺牲计算效率。
• 对于更复杂的问题或更高维的搜索空间，可考虑适当增大种群规模。

适应度修改

• 应根据具体问题及适应度景观特征选择合适的适应度修改方式。适应度共享和惩罚项是较常见的选择。
• 应根据搜索空间中不同最优解之间的预期距离，调整每个已定位最优解周围区域的大小。若最优解彼此间隔较远，可能需要更大的作用区域；若最优解分布较为密集，则较小区域可能已足够。
• 应调节适应度降低幅度，以在探索新最优解与利用已找到最优解之间取得平衡。若降低过强，可能会过度抑制邻近区域搜索；若降低过弱，则可能不足以有效促进新最优解的发现。

终止条件

• 可根据问题中已知或预期的最优解数量，设定待定位最优解的最大数量。
• 可设置“连续若干次迭代未找到新最优解”的上限，以避免在很可能已找到全部最优解时继续浪费计算资源。
• 还可考虑引入相对改进阈值作为附加终止条件，即当新找到最优解的质量相较于先前最优解低于某一阈值时停止搜索。

与其他技术的集成

• 序贯小生境法可与多种进化算法结合使用，例如遗传算法（Genetic Algorithms）、进化策略（Evolution Strategies）和差分进化（Differential Evolution）。应选择与具体问题匹配度较高的底层进化算法。
• 可考虑引入局部搜索技术，例如爬山算法（hill climbing）或模拟退火（simulated annealing），以进一步细化已定位最优解并提升整体解质量。
• 可尝试不同的种群初始化策略，例如拉丁超立方采样（Latin Hypercube Sampling）或对立学习（Opposition-Based Learning），以增强搜索空间的初始覆盖度和初始种群的多样性。