Random optimization
Random optimization (RO) is a family of numerical
The name random optimization is attributed to Matyas [1] who made an early presentation of RO along with basic mathematical analysis. RO works by iteratively moving to better positions in the search-space which are sampled using e.g. a normal distribution surrounding the current position.
Algorithm
Let be the fitness or cost function which must be minimized. Let designate a position or candidate solution in the search-space. The basic RO algorithm can then be described as:
- Initialize x with a random position in the search-space.
- Until a termination criterion is met (e.g. number of iterations performed, or adequate fitness reached), repeat the following:
- Sample a new position y by adding a normally distributed random vector to the current position x
- If (f(y) < f(x)) then move to the new position by setting x = y
- Now x holds the best-found position.
This algorithm corresponds to a (1+1) evolution strategy with constant step-size.
Convergence and variants
Matyas showed the basic form of RO converges to the optimum of a simple
Mathematical analyses are also conducted by Baba [2] and Solis and Wets [3] to establish that convergence to a region surrounding the optimum is inevitable under some mild conditions for RO variants using other probability distributions for the sampling. An estimate on the number of iterations required to approach the optimum is derived by Dorea.[4] These analyses are criticized through empirical experiments by Sarma [5] who used the optimizer variants of Baba and Dorea on two real-world problems, showing the optimum to be approached very slowly and moreover that the methods were actually unable to locate a solution of adequate fitness, unless the process was started sufficiently close to the optimum to begin with.
See also
- hypersphereinstead of a normal distribution.
- uniform distributionin its sampling and a simple formula for exponentially decreasing the sampling range.
- Pattern search takes steps along the axes of the search-space using exponentially decreasing step sizes.
- Stochastic optimization
References
- ^ Matyas, J. (1965). "Random optimization". Automation and Remote Control. 26 (2): 246–253.
- ^ Baba, N. (1981). "Convergence of a random optimization method for constrained optimization problems". Journal of Optimization Theory and Applications. 33 (4): 451–461. .
- ^ Solis, Francisco J.; .
- ^ Dorea, C.C.Y. (1983). "Expected number of steps of a random optimization method". Journal of Optimization Theory and Applications. 39 (3): 165–171. .
- ^ Sarma, M.S. (1990). "On the convergence of the Baba and Dorea random optimization methods". Journal of Optimization Theory and Applications. 66 (2): 337–343. .