Premium
Techniques for bounding the convergence rate of genetic algorithms
Author(s) -
Rabinovich Yuri,
Wigderson Avi
Publication year - 1999
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199903)14:2<111::aid-rsa1>3.0.co;2-6
Subject(s) - sort , bounding overwatch , computer science , convergence (economics) , simple (philosophy) , algorithm , nonlinear system , term (time) , rate of convergence , range (aeronautics) , mathematical optimization , quality control and genetic algorithms , optimization problem , mathematics , key (lock) , artificial intelligence , meta optimization , engineering , philosophy , physics , computer security , epistemology , quantum mechanics , aerospace engineering , economics , information retrieval , economic growth
The main purpose of the present paper is the study of computational aspects, and primarily the convergence rate, of genetic algorithms (GAs). Despite the fact that such algorithms are widely used in practice, little is known so far about their theoretical properties, and in particular about their long‐term behavior. This situation is perhaps not too surprising, given the inherent hardness of analyzing nonlinear dynamical systems, and the complexity of the problems to which GAs are usually applied. In the present paper we concentrate on a number of very simple and natural systems of this sort, and show that at least for these systems the analysis can be properly carried out. Various properties and tight quantitative bounds on the long‐term behavior of such systems are established. It is our hope that the techniques developed for analyzing these simple systems prove to be applicable to a wider range of genetic algorithms, and contribute to the development of the mathematical foundations of this promising optimization method. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 111–138, 1999