Some Researches On Asymptotic Behaviors Of Evolutionary Algorithms

Evolutionary algorithms (EAs) are a general term for a kind of stochastic opti-mization algorithms inspired by natural evolution. They solve the involved problemby converting objects to various codes, searching solutions through population strategy,generating new individuals by simulating natural rules and iteratively optimizing a fit-ness function without special conditions. EAs are especially suited for highly nonlinearcomplex problems that are difficult for traditional searching methods. With genetic al-gorithms as its early representative, new branches and variants of EAs are constantlyemerging after decades of vigorous development, eventually establishing an importantbranch of artificial intelligence called evolution computation (EC). Generally speaking,EC seams to be an experimental science, as researches mainly rely on empirical inves-tigations. Even so, the potential and advantages of EAs are far from being employed.A major reason for this fact is that some of the basic theoretical problems of EAs havenot been completely addressed. To better understand their stochastic behaviors so as toexplore more potential abilities, it is necessary to further study their theoretical foun-dations. This thesis employs theories of stochastic stability and non-negative matricesto study asymptotic behaviors of various EAs, mainly focusing on three basic issues:convergence, convergence rates and computational time complexity. Through improv-ing some existing results and depicting relations among these themes, the thesis triesto make a contribution to the general theoretical framework for EAs described by finiteMarkov chains. It concerns not only the qualitative results to provide analytical issues,but also their practical significance by supplementing case studies. Concretely, the maincontributions are summarized in the following aspects.(1) Conditions for various EAs satisfying different convergence theorems are investi-gated. Firstly, EAs are divided into several categories (such as homogeneous EAs,nonhomogeneous EAs, elitist EAs and asymptotic reducible EAs) according to theircorresponding Markov chains. Homogenous elitist EAs are shown to be completelyconvergent and converge in limited steps with probability one. Meanwhile, weakand general conditions with clear meanings are given. The conclusions are furthergeneralized to nonhomogeneous cases. For asymptotic reducible EAs, two condi-tions are proposed for convergence in probability based on nonnegative matricestheory. Furthermore, these two conditions are verified by simulated annealing ge-netic algorithms and steady state EAs with a variable deleting factor, respectively.(2) Convergence rates are depicted under two measures: the convergence speed of thepower of the probability transition matrix, and the decay rate of the probability that current population is not at an optimal state. At first, their connection is unraveledunder a special distance measure. Then, the following result is generalized intoEAs with multiple aperiodic recurrent classes: the first convergence rate dependson the revised spectral radius of the one-step transition matrix; meanwhile, the rateunder the second measure is proved to be determined by the spectral radius of asub-matrix associated with the non-optimal state sets. Furthermore, analysis onthe spectrum of the transition matrix shows that the relation between the above-mentioned eigenvalues is consistent with that of two measures. In comparison withrelated articles, our discussion here greatly refines previous ones.(3) The exact computation relationship between convergence rates and the first hittingtime (FHT) is discovered. Concretely, with the establishment of the formula ofconvergence rates, the expression of FHT and expected FHT, it is shown under thesecond rate measure that all of them are bundled by the same sub-matrix, whichis the essential deception of existing results. Based this relationship, well-definedbounds of average computation time are immediately obtained, which can be veri-fied by case studies. Moreover, our conclusions are applicable to both homogenousand non-homogenous elitist EAs.(4) Convergence properties of EAs with the elitist recording strategy are studied formulti-modal fitness functions. Either an optimization problem with multiple so-lutions or an irregular encoding scheme can lead to multi-modal fitness functions.However, researchers often assume that the fitness function is injective or has a sin-gle optimal solution. Under general assumptions and based on our results abouthomogenous elitist EAs, convergence and rates are derived by analysis on two up-grading matrices corresponding to different implementations of elitist strategies.Also, the related eigenvalue is estimated roughly and investigations about such EAsare further refined. Furthermore, we deriving two absolutely distinctive upgradingmatrices, both of which differ from the bool-valued one obtained under injectivefunction. Besides, all of these EAs have almost the same convergence proper-ties. As an application, such a kind of gene expression programming algorithmsis analyzed. For the multi-modal fitness function caused by the irregular encodingscheme, the mathematical model is reconstructed based on analysis about propertiesof operators. The convergence properties are investigated under several implemen-tations and rates are also associated with the involved parameters.