Convergences of stochastic optimization algorithms
Abstract of thesis entitled
?onvergences of Stochastic Optimization Algorithms?submitted by
Lee Kwok Shing
for the degree of Master of Philosophy
at the University of Hong Kong
in August, 1997
A stochastic algorithm is one of the approaches to solve the optimization problem. With the inspiration from the nature, researchers invent different stochastic algorithms for optimization. These include the Genetic Algorithm which analogies to the genetics from the biology, the Evolution Strategies which borrows the concept of evolution as well as the Simulated Annealing which simulates the annealing process from solid state physics.
Even though these algorithms originate from different area, they share many similarities. In this thesis, a general model of the stochastic algorithm for optimization is proposed. Usually, the stochastic optimization algorithm composes the candidate generation a well as the selection procedures. However, unlike the deterministic algorithm, the randomness is added to the procedures. Mathematical model of the general stochastic optimization algorithm is given based on the probability distribution of the candidate in the population.
Convergence is an important property of the stochastic optimization process which guarantees the algorithm is able to find the optimum. However, not all the instances of the general stochastic algorithm converge. Therefore to ensure the convergence of an stochastic algorithm, certain conditions are added to the general framework. Moreover, in practice, the optimum is not know a priori so that the convergence measure is required.
A very simple stochastic algorithm for optimization is used to illustrate the uses of the general framework. Unlike other well-known stochastic algorithms, this simple algorithm requires neither the sophisticated candidate generation procedure nor complicated parameters changing schedule. However, this algorithm converges though its performance is not guaranteed.
School:The University of Hong Kong
School Location:China - Hong Kong SAR
Source Type:Master's Thesis
Keywords:stochastic processes mathmatical optimization algorithms
Date of Publication:01/01/1999