自适应随机搜索（ARS）

名称

自适应随机搜索（Adaptive Random Search, ARS）

分类

查看分类思维导图

自适应随机搜索是一种随机优化算法，隶属于更广义的计算智能领域。它与其他随机搜索技术密切相关，例如纯随机搜索（Pure Random Search）和自适应步长随机搜索（Adaptive Step Size Random Search）。

• 计算智能
  • 随机优化
    • 随机搜索
      • 纯随机搜索
      • 自适应步长随机搜索
      • 自适应随机搜索

策略

自适应随机搜索是一种全局优化算法，采用一种简单而有效的策略在搜索空间中寻找最优解。算法首先随机生成一个初始解并评估其适应度。在每次迭代中，通过对当前最优解施加随机扰动来生成新解。扰动的步长会根据前若干次迭代的成功率进行自适应调整。

探索与开发

该算法通过调节扰动步长来平衡探索（exploration）与开发（exploitation）。若新解优于当前最优解，则增大步长以鼓励进一步探索；若新解较差，则减小步长，使搜索集中在当前最优解附近，从而增强开发能力。

步长自适应

步长自适应机制是自适应随机搜索的核心特征。它使算法能够高效探索搜索空间，并逐步收敛至最优解。该自适应过程基于先前迭代的成功率，从而保证算法能够在有前景的区域投入更多搜索，同时快速远离低效区域。

过程

1. 初始化：
   1. 随机生成初始解 x_best
   2. 计算 x_best 的适应度 f(x_best)
   3. 设定初始步长 step_size
   4. 设定成功率阈值 success_threshold
   5. 设定步长调整因子 step_factor
   6. 设定迭代计数器 iter = 0
2. 当停止条件未满足时：
   1. 通过对 x_best 添加随机扰动生成新解 x_new：
   • x_new = x_best + step_size * random_vector()
   2. 计算 x_new 的适应度 f(x_new)
   3. 若 f(x_new) 优于 f(x_best)：
   • 更新 x_best = x_new
   • 更新 f(x_best) = f(x_new)
   • 增加成功计数器 success_count
   4. 更新迭代计数器 iter += 1
   5. 若 iter % adaptation_interval == 0：
   • 计算成功率 success_rate = success_count / adaptation_interval
   • 若 success_rate > success_threshold：
     • 增大步长 step_size *= step_factor
   • 否则：
     • 减小步长 step_size /= step_factor
   • 重置成功计数器 success_count = 0
3. 返回找到的最优解 x_best 及其适应度 f(x_best)

数据结构

• 当前最优解（x_best）：当前最优解
• 当前最优解适应度（f(x_best)）：当前最优解的适应度
• 新解（x_new）：通过对 x_best 添加扰动生成的新解
• 新解适应度（f(x_new)）：新解的适应度
• 步长（step_size）：当前扰动步长
• 成功次数（success_count）：成功迭代次数
• 迭代计数器（iter）：迭代计数器

参数

• 成功阈值（success_threshold）：触发步长自适应的成功率阈值
• 步长调整因子（step_factor）：步长调整因子
• 自适应间隔（adaptation_interval）：两次步长自适应之间的迭代次数

注意事项

优点

• 简单性：自适应随机搜索易于理解和实现，适合广泛用户使用。
• 灵活性：该算法可应用于多种优化问题，而无需问题特定知识或额外修改。
• 高效性：步长自适应机制使算法能够较快收敛至最优解，在函数评估次数方面具有较高效率。

缺点

• 缺乏保证：作为一种随机优化算法，自适应随机搜索并不能保证找到全局最优解。
• 参数敏感性：算法性能可能对参数选择较为敏感，例如成功率阈值和步长调整因子。
• 可扩展性有限：对于高维问题或具有复杂景观的问题，该算法可能表现欠佳，因为随机扰动在搜索中的有效性会下降。

启发式建议

步长初始化

• 可将步长初始化为搜索空间范围的一定比例，例如各维上下界之差的 10%。
• 若问题在不同维度上尺度差异较大，可考虑对搜索空间进行归一化，或采用维度相关的步长设置。

成功率阈值

• 成功率阈值的典型取值为 0.2，即若某一自适应区间内超过 20% 的迭代是成功的，则增大步长。
• 可根据所需的探索与开发平衡调整该阈值。较高阈值会增强开发倾向，较低阈值则会鼓励更多探索。

步长调整因子

• 步长调整因子的常见取值为 2，即当成功率高于阈值时步长加倍，低于阈值时步长减半。
• 较大的调整因子会导致更激进的步长变化，而较小的因子则带来更平缓的自适应过程。

自适应区间

• 自适应区间决定了算法依据成功率调整步长的频率。
• 典型取值为 10 次迭代，即每 10 次迭代进行一次步长调整。
• 较长的区间会带来更稳定的自适应效果，而较短的区间则有助于算法更快响应搜索景观的变化。

停止准则

• 可根据可用计算预算设定最大迭代次数或最大函数评估次数。
• 也可以在步长减小到某个阈值以下时停止算法，这通常表明搜索已收敛到某个局部最优附近。
• 还可考虑引入停滞检测机制，即当最优解在指定次数迭代内不再改进时停止算法。