和声搜索（HS）

名称

和声搜索（Harmony Search, HS）

分类

查看分类思维导图

和声搜索是一种受音乐家即兴演奏过程启发的元启发式优化算法。它属于进化算法家族，并与其他基于种群的元启发式方法密切相关，如遗传算法和粒子群优化。

• 计算智能
  • 生物启发计算
    • 进化算法
      • 遗传算法
      • 差分进化
      • 和声搜索
  • 群体智能
    • 粒子群优化
    • 蚁群优化
• 随机优化
  • 元启发式
    • 单解式元启发式
    • 基于种群的元启发式
      • 进化算法
        • 和声搜索

策略

和声搜索模拟爵士乐队中音乐家的即兴演奏过程。其中，每位音乐家对应一个决策变量，而即兴演奏过程则对应在问题空间中搜索更优解的过程。算法维护一个称为和声记忆库（Harmony Memory, HM）的记忆结构，用于存储一组较优解。新解通过三种规则生成：记忆考虑、音高调整和随机选择。

在记忆考虑阶段，算法以称为和声记忆考虑率（Harmony Memory Considering Rate, HMCR）的概率，从和声记忆库中为每个决策变量选取一个值；若该变量的值未从记忆库中选取，则在该变量的可行取值范围内随机生成。

音高调整阶段作用于从记忆库中选取的变量值。算法以称为音高调整率（Pitch Adjusting Rate, PAR）的概率，对所选取的变量值施加一个小幅度调整，从而实现对解的局部精细搜索。

随机选择阶段则通过以 $(1 - HMCR)$ 的概率为某一决策变量赋予随机值，引入搜索多样性。

新生成的解将通过目标函数进行评估。若该解优于和声记忆库中的最差解，则用其替换最差解。上述过程不断重复，直到满足某个终止准则，例如达到最大迭代次数或获得满意解。

过程

数据结构

• 和声记忆库（Harmony Memory, HM）：用于存储一组较优解的矩阵，其中每一行表示一个解，每一列对应一个决策变量。
• 和声记忆考虑率（Harmony Memory Considering Rate, HMCR）：从和声记忆库中选取变量值的概率。
• 音高调整率（Pitch Adjusting Rate, PAR）：对从和声记忆库中选取的决策变量值进行调整的概率。
• 带宽（Bandwidth, bw）：在音高调整阶段中，决策变量允许调整的最大幅度。

参数

• 和声记忆库规模（Harmony Memory Size, HMS）：和声记忆库中存储的解的数量。
• 最大迭代次数（Maximum Iterations, MaxIter）：算法允许执行的最大迭代次数或即兴生成次数。
• 和声记忆考虑率（HMCR）
• 音高调整率（PAR）
• 带宽（bw）

步骤

1. 使用随机解初始化和声记忆库（HM）。
2. 利用目标函数评估 HM 中每个解的适应度。
3. 即兴生成一个新解：
   1. 对每个决策变量：
      1. 以 HMCR 的概率从 HM 对应列中选取一个值。
      2. 若未从 HM 中选取值，则在可行范围内随机生成一个值。
      3. 若该值来自 HM，则以 PAR 的概率对其进行音高调整，即在 bw 限制范围内加上或减去一个小的随机扰动量。
   2. 用新生成或调整后的值更新各决策变量。
4. 利用目标函数评估新解的适应度。
5. 若新解优于 HM 中的最差解，则用新解替换最差解。
6. 重复步骤 3–5，直到达到最大迭代次数（MaxIter）或找到满意解。
7. 返回和声记忆库中找到的最优解。

注意事项

优点

• 结构简单，易于实现
• 相较于其他进化算法，需要调节的参数较少
• 既能处理离散优化问题，也能处理连续优化问题
• 能够较好地平衡搜索空间中的探索与开发

缺点

• 若参数设置不当，可能会过早收敛或陷入局部最优
• 算法性能依赖于参数（HMCR、PAR、bw）的合理选取
• 为获得高质量解，可能需要较多的函数评估次数

启发式建议

参数选择

• 和声记忆考虑率（HMCR）：
  • 通常设置在 0.7 到 0.95 之间
  • 较高的取值更强调对和声记忆库中已有优良解的利用
  • 较低的取值更有利于扩大搜索空间探索范围
• 音高调整率（PAR）：
  • 通常设置在 0.1 到 0.5 之间
  • 较高的取值有助于对解进行更精细的局部调整
  • 较低的取值有助于保持解的多样性
• 带宽（bw）：
  • 取值依赖于具体问题及决策变量的范围
  • 较小的取值适合进行局部精细搜索
  • 较大的取值有助于探索搜索空间中更远的区域

和声记忆库规模

• 较大的和声记忆库规模（HMS）能够存储更多样化的解，但可能减缓收敛速度
• 较小的 HMS 可能导致早熟收敛，但在计算上更高效
• 常见取值范围为 10 到 50，具体取决于问题复杂度

终止准则

• 应根据问题复杂度和可用计算资源设置最大迭代次数（MaxIter）
• 可监测最优解在若干次迭代中的改进情况，若未观察到显著提升，则终止算法
• 若已知目标函数值的合理阈值，也可将其作为终止准则

混合化

• 和声搜索可以与其他优化技术（如局部搜索方法）进行混合，以提升算法性能
• 将问题相关知识或特定启发式规则融入算法中，有助于增强搜索过程并提升解的质量