随机搜索

简介

随机搜索 (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年将随机搜索用于超参数优化中。

主要事件

年份事件相关论文
1981Solis, F. J., & Wets, R. J. B.对随机优化进行reviewSolis, F. J., & Wets, R. J. B. (1981). Minimization by random search techniques. Mathematics of operations research, 6(1), 19-30.
2005Spall, J. C.对随机优化进行详细概述Spall, J. C. (2005). Introduction to stochastic search and optimization: estimation, simulation, and control (Vol. 65). John Wiley & Sons.
2012Bergstra, J., & Bengio, Y.在2012年将随机搜索用于超参数优化中。Bergstra, J., & Bengio, Y. (2012). Random search for hyper-parameter optimization. Journal of Machine Learning Research, 13(Feb), 281-305.

发展分析

瓶颈

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

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

【来源:paper, URL: Random Search Algorithms - University of Washington

未来发展方向

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

【来源:paper, URL: Random Search Algorithms - University of Washington

Contributor: Ruiying Cai

相关人物
詹姆斯·伯格斯特拉
詹姆斯·伯格斯特拉
蒙特利尔大学博士,师从Yoshua Bengio,曾在哈佛大学和滑铁卢大学进行博士后研究。现任Kindred.ai联合创始人,负责AI研究。
James C. Spall
James C. Spall
Rastrigin, L.A.
Rastrigin, L.A.
简介
相关人物