Model Establishments And Performance Analyses Of Evolutionary Algorithms

In recent years, evolutionary algorithms (EAs) are successfully applied to industrialdesign, economic management, transportation and other domains, and solve manyvaluable optimization problems. Although EAs have received much success in manypractical applications, there exist some shortcomings and defects in theoreticalfoundations. Especially, EAs are lack of systematic and standard theoretical analysismodels and tools, which becomes a bottleneck for further development of algorithms.The purpose of this dissertation is to build new mathematical models and analyticaltools to study evolution mechanisms of algorithms, analyze the problems of parametersetting, and theoretically compare their optimization performance, based onperformance differences of EAs. The main works are as following:Firstly, equivalences and differences of EAs are analyzed and compared. Becauseof novel EAs emerging, this dissertation combines the academic thoughts of variousEAs, and takes five popular EAs as examples, including genetic algorithms (GA),evolution strategies (ES), particle swarm optimization algorithm (PSO), differentialevolution (DE) and biogeography-based optimization (BBO), to conceptually discusstheir equivalences and the corresponding conditions. It finds that BBO, DE, ES andPSO are equal to the GA with global uniform recombination under certain conditions.Then the differences of EAs are discussed based on biological motivations, and itpoints out that based on the different evolution mechanisms and tuning parameters,various EAs are used to different application domains. To further study theoptimization ability of these algorithms, their basic versions and advanced versionsare compared on a set of benchmark functions. Empirical results confirm that it isnecessary that various EAs exist in real-world applications and their theories arefurther studied.Secondly, standard Markov chain models of EAs are built, and their performancesare analyzed. Now standard Markov chain models are still the preferred analysis tools to study EAs. This dissertation derives standard Markov chain models for GA andBBO, and it finds that when the immigration rate is set to1, BBO is equal to the GAwith global uniform recombination. Then according to various migration strategies,the new three variations of BBO are proposed, and their corresponding standardMarkov chain models are also derived. The numerical simulations are performed toverify the correctness of the proposed models, and the results show that for somerepresentative problems, the optimization performances of GA, BBO and itsvariations are apparently different. Furthermore, this dissertation analyzes theconvergence of GA and BBO based on the previously-derived Markov chain models.It points out that these two algorithms do not converge with probability1to any of theglobal optima, but in the case of elitism, they converge to one or more of the globaloptima. In addition, the convergence rate estimate theorem of GA and BBO withelitism is obtained, which is confirmed by numerical simulations.Thirdly, interactive Markov models of EAs are built, and their performances areanalyzed. Because the standard Markov models have the difficulty on modeling andcalculation, this dissertation first introduces the concepts and definitions of interactiveMarkov models, which is based on ideas of interaction among population individualsto study the evolution of EAs. This new interactive Markov models has the potentialto provide tractable models for optimization problems. Then two new simple EAswith population-proportion-based selection are proposed, which are called strategy Aand strategy B. Furthermore, their interactive Markov models are exactly modeled,the convergences and the steady state probabilities are discussed, and the convergencetheorem of interactive Markov models is obtained. Meanwhile, the selection pressuresof these two new EAs, and the equivalences between them and other EAs are alsoanalyzed and discussed. The numerical simulations are performed to verify thecorrectness of the interactive Markov models.Fourthly, statistical mechanics approximation models of EAs are built, and theirperformances are analyzed. Because the dynamic system study of EAs is still lack ofthe general and powerful analysis models, and Markov models are hard to show theevolution process of EAs, this dissertation introduces the concepts and definitions of statistical mechanism approximation method from physics. Then the particular case ofthe one-max problem is used to derive the statistical mechanics approximation modelsof GA and BBO, which reveals the effect of selection, mutation, and crossover on thepopulation dynamics of GA, and the effect of migration and mutation on thepopulation dynamics of BBO. The numerical simulations are performed to verify thecorrectness of the statistical mechanics approximation models. Furthermore, themodels of these two algorithms are compared, and it finds that although there have thequantitative differences between them, the evolutionary tendencies are very similar. Inaddition, the statistical mechanics approximation model of BBO is also derived for theseparable functions, and the results show the model is same as that for the one-maxproblem, which further verifies the feasibility and correctness of the statisticalmechanics approximation model.