Controlled Random Search (CRS)
CRS, originally suggested by W.L. Price in 1978, is a 'direct search' technique and purely heuristic.It is a kind of contraction process where an inital sample S of N points in A, part of Rn, is iteratively contacted by replacing the worst point with a better point until they all are close enough.
The replacement point is either determined by a global or local technique. The global technique is an iterative process in which a trial point, the 'new' point is defined in terms of n+1 points selected from the whole current sample of N points until a replacement point is found. Some newer CRS algorithms also apply a local technique where the replacement point is searched for, near a subset of best points in the current sample.
Based on which global and local technique that is used the CRS algorithms are classified as CRS(G,L) wher G and L stands for the global and local technique respectively. Price's original algorithm CRS(Nelder and Mead simplex, .) did not use any local technique. A recent algorithm by Ali, Törn, Viitanen, CRS(q,ß), applies a quadratic approximation as global and sampling from a beta distribution as local technique. CRS(q,ß) has performed well in numerical comparisons.
CRS(q,ß): The global part consists of choosing three points from S instead of n+1, i.e., the best point, call it r1 =(r11..r1n), and two other points at random, call them r2 and r3. For each coordinate i the algorithm determines the minimum point p.i of the quadratic through the points r1i, r2i, r3i giving the new trial point p=(p.1..p.n). If this point is better than the worst point in S it replaces the worst point. If it is a new best point then M local steps using an appropriate beta distribution are made otherwise a new point p is determined. This is then repeated until the stopping condition is fulfilled.
M.M. Ali, A. Törn, S. Viitanen: A Numerical Comparison of Some Modified Controlled Random Search Algorithms, Journal of Global Optimization 11: 377-385, 1997.