Random Search

HumpDay Implementation Documentation

Abstract

RandomSearch is a baseline, not a SOTA algorithm. It draws n_trials i.i.d. uniform samples from [0, 1]ⁿ and keeps the best. Two reasons to ship it: (1) regression check — any optimizer worth using should clearly beat RandomSearch on smooth problems; (2) contest sanity floor — ensures the benchmarking harness scores absolute performance, not just relative ranking among SOTA methods. The companion baseline is GridSearch, which enumerates a regular Cartesian grid instead.

Auto-selection metadata. Consulted by humpday.minimize() when picking a default algorithm.

Overhead tier 0: trivial (~µs/iter). Always eligible by the timing filter.
Dimensional cap: no cap — linear-in-dim or better.
Minimum trials: 10 — baseline minimum.

Algorithm Description

The Random Search algorithm generates candidate solutions by uniform random sampling from the feasible region. For a $D$-dimensional optimization problem on the unit hypercube $[0,1]^D$, the algorithm operates as follows:

Random Sampling:

$$\mathbf{x}_i \sim \mathcal{U}([0,1]^D)$$

Best Solution Tracking:

$$\mathbf{x}^* = \arg\min_{i=1,\ldots,N} f(\mathbf{x}_i)$$

where:

$\mathbf{x}_i$ is the $i$-th randomly generated candidate solution
$\mathcal{U}([0,1]^D)$ denotes uniform distribution over the unit hypercube
$N$ is the total number of function evaluations
$f(\cdot)$ is the objective function to be minimized

Implementation Details

Component	Description	Reference
Algorithm Concept	Pure random sampling from uniform distribution. Fundamental Monte Carlo method serving as optimization baseline.	Bergstra & Bengio (2012)
Python Implementation	HumpDay modular implementation in evolutionary_algorithms.py	Source Code
JavaScript Implementation	Browser-compatible implementation in modular structure	JavaScript Source
Reference Implementation	Self-validating (mathematically trivial implementation)	Wikipedia: Random Search

The Python and JS implementations are i.i.d. uniform samplers; the reference adapter in tests/test_reference_alignment.py is also a uniform sampler with a different RNG seed. The ratio on SOTA status is therefore close to 1 and not a quality signal — it's there as a sanity check that the harness is wired correctly.

Theoretical Properties

Property	Description	Convergence Rate
Global Convergence	Almost sure convergence to global optimum	O(1/N) expected improvement
Dimension Independence	No curse of dimensionality in convergence rate	Rate independent of D
Function Assumptions	No smoothness or continuity requirements	Works on any measurable function
Memory Requirements	O(D) memory for current best solution	Minimal storage overhead

Practical Applications

Random Search is particularly valuable as:

Baseline Comparison: Standard reference for evaluating more sophisticated algorithms
High-Dimensional Problems: Competitive in very high dimensions where structure-based methods fail
Robust Optimization: Effective when objective function is noisy or discontinuous
Hyperparameter Tuning: Often outperforms grid search in machine learning applications

References

Bergstra, J., & Bengio, Y. (2012). Random search for hyper-parameter optimization. Journal of machine learning research, 13(2), 281-305.
Rastrigin, L. A. (1963). The convergence of the random search method in the extremal control of a many parameter system. Automation and Remote Control, 24(10), 1337-1342.
Zhigljavsky, A., & Žilinskas, A. (2008). Stochastic global optimization. Springer Science & Business Media.
Spall, J. C. (2003). Introduction to stochastic search and optimization: estimation, simulation, and control. John Wiley & Sons.

Part of the HumpDay optimization library | Documentation | Source Code