Random SearchRandom Search, RS, Blind Random Search, Blind Search, Pure Random Search, PRS TaxonomyRandom search belongs to the fields of Stochastic Optimization and Global Optimization. Random search is a direct search method as it does not require derivatives to search a continuous domain. This base approach is related to techniques that provide small improvements such as Directed Random Search, and Adaptive Random Search. StrategyThe strategy of Random Search is to sample solutions from across the entire search space using a uniform probability distribution. Each future sample is independent of the samples that come before it. ProcedureAlgorithm (below) provides a pseudocode listing of the Random Search Algorithm for minimizing a cost function. Input :
NumIterations , ProblemSize , SearchSpace
Output :
Best
Best $\leftarrow \emptyset$For ($iter_i \in$ NumIterations )$candidate_i$ $\leftarrow$ RandomSolution (ProblemSize , SearchSpace )If (Cost ($candidate_i$) < Cost (Best ))Best $\leftarrow$ $candidate_i$End End Return (Best )Heuristics
Code ListingListing (below) provides an example of the Random Search Algorithm implemented in the Ruby Programming Language. In the example, the algorithm runs for a fixed number of iterations and returns the best candidate solution discovered. The example problem is an instance of a continuous function optimization that seeks $\min f(x)$ where $f=\sum_{i=1}^n x_{i}^2$, $5.0\leq x_i \leq 5.0$ and $n=2$. The optimal solution for this basin function is $(v_0,\ldots,v_{n1})=0.0$. def objective_function(vector) return vector.inject(0) {sum, x sum + (x ** 2.0)} end def random_vector(minmax) return Array.new(minmax.size) do i minmax[i][0] + ((minmax[i][1]  minmax[i][0]) * rand()) end end def search(search_space, max_iter) best = nil max_iter.times do iter candidate = {} candidate[:vector] = random_vector(search_space) candidate[:cost] = objective_function(candidate[:vector]) best = candidate if best.nil? or candidate[:cost] < best[:cost] puts " > iteration=#{(iter+1)}, best=#{best[:cost]}" end return best end if __FILE__ == $0 # problem configuration problem_size = 2 search_space = Array.new(problem_size) {i [5, +5]} # algorithm configuration max_iter = 100 # execute the algorithm best = search(search_space, max_iter) puts "Done. Best Solution: c=#{best[:cost]}, v=#{best[:vector].inspect}" end Download: random_search.rb.
ReferencesPrimary SourcesThere is no seminal specification of the Random Search algorithm, rather there are discussions of the general approach and related random search methods from the 1950s through to the 1970s. This was around the time that pattern and direct search methods were actively researched. Brooks is credited with the socalled 'pure random search' [Brooks1958]. Two seminal reviews of 'random search methods' of the time include: Karnopp [Karnopp1963] and perhaps Kul'chitskii [Kulchitskii1976]. Learn MoreFor overviews of Random Search Methods see Zhigljavsky [Zhigljavsky1991], Solis and Wets [Solis1981], and also White [White1971] who provide an insightful review article. Spall provides a detailed overview of the field of Stochastic Optimization, including the Random Search method [Spall2003] (for example, see Chapter 2). For a shorter introduction by Spall, see [Spall2004] (specifically Section 6.2). Also see Zabinsky for another detailed review of the broader field [Zabinsky2003]. Bibliography 
Free CourseGet one algorithm per week...
Own A CopyThis 438page ebook has...

Please Note: This content was automatically generated from the book content and may contain minor differences. 

Do you like Clever Algorithms? Buy the book now. 