Analysis and parameter selection for an Adaptive Random Search algorithm

Author

Kumar, Rajeeva ; Kabamba, Pierre T. ; Hyland, David C.

Author_Institution

Dept. of Aerosp. Eng., Michigan Univ., Ann Arbor, MI, USA

Volume

5

fYear

2004

fDate

14-17 Dec. 2004

Firstpage

5322

Abstract

This paper presents an analysis of an adaptive random search (ARS) algorithm, a global minimization method. A probability model is introduced to characterize the statistical properties of the number of iterations required to find an acceptable solution. Moreover, based on this probability model, a new stopping criterion is introduced to predict the maximum number of iterations required to find an acceptable solution with a pre-specified level of confidence. This leads to the Monte Carlo version of the algorithm. Finally, this paper presents a systematic procedure for choosing the user-specified parameters in the ARS algorithm for fastest convergence. The results, which are valid for search spaces of arbitrary dimensions, are illustrated on a simple 3-dimensional example.

Keywords

Monte Carlo methods; convergence; minimisation; probability; random processes; search problems; Monte Carlo algorithm; adaptive random search algorithm; convergence; global minimization method; iterations; parameter selection; probability model; search spaces; statistical properties; stopping criterion; Algorithm design and analysis; Convergence of numerical methods; Cost function; Economic forecasting; Minimization methods; Monte Carlo methods; Numerical simulation; Predictive models; Probability;

fLanguage

English

Publisher

ieee

Conference_Titel

Decision and Control, 2004. CDC. 43rd IEEE Conference on

ISSN

0191-2216

Print_ISBN

0-7803-8682-5

Type

conf

DOI

10.1109/CDC.2004.1429654

Filename

1429654