First passage times of genetic algorithms
Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Learning and adaptive systems in artificial intelligence (68T05) Nonnumerical algorithms (68W05) Applications of mathematical programming (90C90)
Let be given a set \(I\), finite but with extremely many elements, and a function \(f|I\rightarrow\mathbb{R}\). One possibility for searching the maximizers of \(f\) is the imitation of biological evolution, named genetic algorithm. A Markov chain \((X_n)\) with the population space \(I^p\) (\(p\) being the population size) as state space describes the evolution by means of the cyclically acting evolution mechanisms mutation, mixing, recombination and selection. Outgoing from a destination set \(S^*\) of the population and the first-entrance time \(\tau:=\inf\{n\geq 0:X_n\in S^*\}\), mainly the convergence principle \(\varlimsup_{n\rightarrow\infty}\sup_{\mu}P_{\mu}(\tau>n)=0\) (\(\mu\) being the initial distribution) has been investigated. In connection with the known algorithmic principle of simulated annealing, the transition kernel \(Q(\beta_n)\) of \((X_n)\) what can be represented as a product sum of the partial transition kernels of the separate evolution mechanisms, will be considered as dependent on a cooling schedule \((\beta_n)\). Now, by means of the Perron-Frobenius theory, the distribution of \(\tau\) and the (quasi-)stationary distribution of \((X_n)\) on dependence of the eigenvalues of \(Q(\beta_n)\) asymptotically has been investigated for the homogeneous as well as for the non-homogeneous case. The influence of the cooling schedule to the convergence of \(\tau\) and its speed is given. With the paper, the author shows great competence in theoretical biology as well as in Markov chains. The paper is written in an exact mathematical style. Often it is commented which meanings mathematical properties have for biological evolution. The present material is very rich, nevertheless many questions remain open what will be named in the final chapter. The rich list of literature (58 items) and exact references within the text may stimulate the reader to more profound studies.
- scientific article; zbMATH DE number 1471372
- A new approach to estimating the expected first hitting time of evolutionary algorithms
- Genetic algorithms in time-dependent environments
- Finite-time performance analysis for genetic algorithms
- scientific article; zbMATH DE number 5059371
- On the convergence rates of genetic algorithms
- Drift conditions for estimating the first hitting times of evolutionary algorithms
- scientific article; zbMATH DE number 1873257
- scientific article; zbMATH DE number 4206030
- scientific article; zbMATH DE number 5222298
This page was built for publication: First passage times of genetic algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2784223)
