分散搜索（SS）

名称

分散搜索（Scatter Search, SS）

分类

查看分类思维导图

分散搜索是一种基于种群的元启发式优化算法，隶属于演化计算领域。它与其他基于种群的元启发式方法密切相关，例如遗传算法（Genetic Algorithms）和差分进化（Differential Evolution）。

• 人工智能
  • 计算智能
    • 演化计算
      • 演化算法
        • 遗传算法
        • 差分进化
        • 分散搜索

策略

多样化与强化

分散搜索维护一个由多样且高质量解构成的小规模种群，称为参考集（Reference Set）。算法通过对参考解进行组合生成新解，并结合局部搜索对其加以改进，从而在探索（多样化）与开发（强化）之间取得平衡。

子集生成与组合

参考集被划分为若干子集，通常每个子集的规模为 2，然后利用这些子集通过某种组合方法生成新解。组合方法旨在使后代解既能够继承父代解的优良特性，又能够引入一定多样性。

改进与参考集更新

新生成的解通常会经历一个改进阶段，一般通过局部搜索过程来提升其质量。随后，算法依据适应度和多样性对参考集进行更新，以改进后的后代解有选择地替换参考集中原有的部分解。

过程

数据结构：

• 参考集（Reference Set）：由多样且高质量解组成的小规模解集
• 解（Solution）：优化问题的一个候选解

参数：

• 参考集规模（Reference Set Size）：参考集中解的数量
• 子集规模（Subset Size）：从参考集中生成用于组合的子集大小
• 最大迭代次数（Maximum Iterations）：算法运行的最大迭代次数

1. 初始化：
   1. 生成初始解种群
   2. 评估每个解的适应度
   3. 从初始种群中选取一组多样且高质量的解，构成参考集
2. 当停止准则未满足时（例如尚未达到最大迭代次数）：
   1. 子集生成：
      1. 从参考集中生成若干解子集
   2. 组合：
      1. 对每个子集应用组合方法，生成新的后代解
   3. 改进：
      1. 对后代解应用局部搜索过程，以提升其质量
   4. 参考集更新：
      1. 评估改进后后代解的适应度
      2. 用高质量且具有多样性的后代解替换参考集中质量较低的解
   5. 终止检查：
      1. 检查是否满足停止准则（例如达到最大迭代次数，或找到满意解）
3. 返回参考集中找到的最优解

注意事项

优点：

• 能够有效平衡探索与开发
• 适用于具有复杂非线性搜索空间的问题
• 能够维持一组多样且高质量的解

缺点：

• 需要设计与具体问题相关的组合方法和改进方法
• 若参考集丧失多样性，可能会发生过早收敛
• 由于包含局部搜索改进阶段，计算代价可能较高

启发式建议

参考集规模

• 通常较小，一般约为 10–20 个解
• 应足够大以维持多样性，但又应足够小以控制计算成本在合理范围内

子集规模

• 通常设为 2，以进行两两组合
• 对于高维搜索空间问题，或希望产生更多样组合时，可适当增大子集规模

组合方法

• 应生成能够继承父代解优良特性的后代解
• 常见方法包括线性组合、交叉算子（如单点交叉、两点交叉、均匀交叉）以及路径重连（path relinking）

改进方法

• 通过局部搜索过程提升后代解质量
• 可以采用问题特定方法（如爬山法、模拟退火），也可以采用通用方法（如模式搜索、Nelder-Mead 单纯形法）
• 需要在计算开销与解质量提升预期之间取得平衡

多样性管理

• 应维持参考集中的多样性，以防止过早收敛
• 在更新参考集时，应同时考虑适应度与多样性
• 可采用拥挤距离、适应度共享或聚类等技术促进多样性保持

终止准则

• 应根据计算预算和问题复杂度设置最大迭代次数
• 可进一步考虑解质量改进速率或参考集多样性等附加准则
• 当找到满意解时，可允许提前终止算法