词条 | Random optimization |
释义 |
Random optimization (RO) is a family of numerical optimization methods that do not require the gradient of the problem to be optimized and RO can hence be used on functions that are not continuous or differentiable. Such optimization methods are also known as direct-search, derivative-free, or black-box methods. The name random optimization is attributed to Matyas 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. AlgorithmLet f: ℝn → ℝ be the fitness or cost function which must be minimized. Let x ∈ ℝn designate a position or candidate solution in the search-space. The basic RO algorithm can then be described as:
This algorithm corresponds to a (1+1) evolution strategy with constant step-size. Convergence and variantsMatyas showed the basic form of RO converges to the optimum of a simple unimodal function by using a limit-proof which shows convergence to the optimum is certain to occur if a potentially infinite number of iterations are performed. However, this proof is not useful in practice because a finite number of iterations can only be executed. In fact, such a theoretical limit-proof will also show that purely random sampling of the search-space will inevitably yield a sample arbitrarily close to the optimum. 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
References1. ^1 {{cite journal|last=Baba|first=N.|title=Convergence of a random optimization method for constrained optimization problems|journal=Journal of Optimization Theory and Applications|year=1981|volume=33|number=4|pages=451–461|doi=10.1007/bf00935752}} [1][2][3][4]2. ^1 {{cite journal|last1=Solis|first1=F.J.|last2=Wets|first2=R.J-B.|title=Minimization by random search techniques|journal=Mathematics of Operations Research|year=1981|volume=6|number=1|pages=19–30|doi=10.1287/moor.6.1.19}} 3. ^1 {{cite journal|last1=Dorea|first1=C.C.Y.|title=Expected number of steps of a random optimization method|journal=Journal of Optimization Theory and Applications|year=1983|volume=39|number=3|pages=165–171|doi=10.1007/bf00934526}} 4. ^1 {{cite journal|last1=Sarma|first1=M.S.|title=On the convergence of the Baba and Dorea random optimization methods|journal=Journal of Optimization Theory and Applications|year=1990|volume=66|number=2|pages=337–343|doi=10.1007/bf00939542}} }}{{Major subfields of optimization}}{{DEFAULTSORT:Random Optimization}} 1 : Optimization algorithms and methods |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。