随机搜索

随机搜索 (Random Search) 是一组不需要优化问题梯度的数值优化方法，因此RS可以被用于非连续或可微的函数。这种优化方法也被称为直接搜索、无派生或黑盒方法。

随机搜索这个名字是由于 Rastrigin 在1963年的《The convergence of the random search method in the extremal control of a many parameter system》首次出现，他对RS进行了早期的介绍，并进行了基本的数学分析。RS的工作方式是迭代地移动到搜索空间中更好的位置，这些位置是从环绕当前位置的超球体中取样的。

算法

使得 f: ℝn→ℝ 为适应度或成本函数，目标就是最小化f。让 x∈ℝn 指候选解的搜索空间。基本的随机搜索算法可以描述为:

1. 在搜索空间中随机初始化x。
2. 直到满足终止标准(例如执行的迭代次数，或达到适当的适应度)，重复以下步骤:

• 从给定半径的超球面上取一个新的位置，围绕当前位置x (参见:一个超球面取样 Marsaglia's technique )。
• 如果f(y) < f(x)然后通过设置x = y移动到新位置。

步骤

NumIterations 是迭代次数，ProblemSize 问题的大小，SearchSpace 搜索空间，Best是最优值。在迭代次数内的候选项，如果当前候选项的花费小于当前最优值的花费，那么更新最优值。

来源：web； URL：http://www.cleveralgorithms.com/nature-inspired/stochastic/random_search.html 

发展历史

随机搜索算法，并没有专门的定义，而是在20世纪50年代到70年代，一般方法和相关的随机搜索方法相继的出现。这也是在模式和直接搜索方法（ pattern and direct search）被积极研究的时候。布鲁克斯被认为是所谓的“纯粹随机搜索” “pure random search ”[Brooks，1958]《A Discussion of Random Methods for Seeking Maxima》。对“随机搜索方法”的两个重要的评论包括:[Karnopp，1963，Random search techniques for optimization problems]和[Kulchitskii，1976，Random-search algorithm for extrema in functional space under conditions of partial uncertainty]。

Zhigljavsky，1991年在《heory of global random search》对于随机搜索方法的概述。 Solis和Wets Minimization by Random Search Techniques，1981]，以及 [A survey of random methods for parameter optimization，White，1971]也对随机搜索算法富有洞察力的review文章。

Spall提供了一个关于随机优化领域的详细概述，包括随机搜索方法[Introduction to stochastic search and optimization: estimation, simulation, and control， 2003](参见第2章)和(具体见6. Stochastic Optimization第6.2节)。Zabinsky在2003年对随机搜索算法的更广泛领域详细回顾[Stochastic adaptive search for global optimization，Zabinsky，2003]。

演化：

• Fixed Step Size Random Search (FSSRS) 是 Rastrigin 是随机搜索最基础的算法。从固定半径的超球面取样。
• Optimum Step Size Random Search (OSSRS) 由 Schumer and Steiglitz 提出，它主要是研究如何调整超球面半径，使其能够快速收敛到最优。OSSRS的实际实现需要通过重复采样来近似这个最优半径，因此执行起来很昂贵。
• Adaptive Step Size Random Search (ASSRS) 由 Schumer and Steiglitz 提出，它试图对超球面的半径进行启发式调整:生成两个新的候选解决方案，一个是当前的步长，另一个是更大的步长。更大的步长成为新的当前步长，如果且仅当它导致更大的改进。如果在几个迭代中，两个步骤都不会导致改进，那么名义步长就会减少。
• Optimized Relative Step Size Random Search (ORSSRS) 由 Schrack 和 Choit 提出，它通过一个简单的指数衰减来近似最优步长。然而，计算衰减系数的公式有些复杂。

Bergstra, J., & Bengio, Y。在2012年将随机搜索用于超参数优化中。

主要事件

发展分析

瓶颈

在一些情况下，随机搜索的运行时间却比网络搜索显著的少，随机搜索得到的超参数组合的性能稍微差一点。

尽管随机搜索相对于很复杂的问题比较容易应用。但是这些方法缺点在于，它们目前主要通过反复试验来针对每个特定问题进行定制。

【来源：paper， URL： Random Search Algorithms - University of Washington】

未来发展方向

一种经验是，随机搜索算法表现良好并且在某种意义上是“健壮的”，是因为它们可以快速地为不良结构的全局优化问题提供有用的信息。所以随机搜索将会在模式选择，参数优化等大放异彩。

【来源：paper， URL： Random Search Algorithms - University of Washington】

Contributor: Ruiying Cai