Some Studies On The Convergence And Time Complexity Analysis Of Evolutionary Algorithms

Evolutionary Algorithms(EAs) are a wide class of randomized search heuristics inspired bythe idea of “natural selection and survival of the fittest” in the Theory of Evolution. Thesealgorithms are mainly applied to solve the complicated optimization problems which aredifficult for traditional computing methods to tackle. They have been applied widely inengineering optimization and achieved great success. At present, the researches onevolutionary algorithms are mostly focused on simulation experiments and practicalapplications, relatively speaking, the theoretical foundation researches of EAs are still few.The main reason for this situation lies in the essence of randomness in the running of EAs.Convergence and time complexity analyses are the hot topic and difficult point of thetheoretical foundation researches about EAs, we can get a deep insight into the runningprinciple of EAs through the research of their convergence and time complexity, thus workout more efficient EAs. Aiming at the complicated random behavior of EAs, this dissertationcarried out researches on the convergence and time complexity analysis of EAs based onstochastic process. The main innovations are listed as below:(1) Theory of discrete state markov chain has been applied widely to the convergence andtime complexity analysis of EAs, while theory of continuous state markov chain does notreceive sufficient and systematic application due to its sophistication. This dissertationintroduces the theory of continuous state markov chain, uses measure theory as a tool,deduces a key formula of transition probability with the help of axiomatic theory ofconditional mathematical expectation. We analyze the convergence of the continuous EAsrepresented by (1+1)ES, prove theoretically that a wide class of common mutationdistribution including normal distribution and Cauchy distribution can make (1+1)ESconverge in probability to the ε-vicinity of the global optimum if the constant mutationoperator is adopted; While some self-adaptive mutation operators can lead (1+1)ES topremature convergence even if use the normal distribution and Cauchy distribution asmutation distribution, these results show that self-adaptive adjustment is not always effective.The theoretical analysis is validated by numerical experiments.(2) Drift analysis is a powerful tool in the time complexity analysis of EAs, which wasintroduced by Jun He and Xin Yao in2001(see Artificial Intelligence127(1)(2001)57-85),and was applied widely later. However, the core theorem in the original paper—theorem1remained defective: the conditions were too strict, the proof contained errors and was notrigorous, etc, and these defects have not been pointed out. It is necessary to make the theorem more rigorous considering the theorem is the core and theoretical foundation of drift analysis.This dissertation points out the defects in the original theorem, uses measure theory as tool toamend and improve the theorem and presents a new and rigorous proof.(3) This dissertation introduces the stopping time theory as a mathematical tool, regard thefirst hitting time of EAs as a stopping time, proposes a novel approach for the analysis of thefirst hitting time of EAs with the help of the properties of homogeneous markov chain, underthis framework, the Level-reaching Estimation Technique is proven rigorously as a specialcase. To illustrate how the proposed method can be applied to concrete problems in analyzingthe expected first hitting time of EAs, we analyze the runtime of (1+λ)EA on LeadingOnesproblem, PEAK function and (1+λ)ES on inclined plane problem. The results show that theproposed method has generality, it is not only suitable for discrete optimization but alsosuitable for continuous optimization.(4) Analyzing the runtime of EAs on the real-world combinatorial optimization problems isa difficult point in the current research. This dissertation applies the theoretical method ininnovation point No.3to analyze the time complexity of (1+1)EA on two combinatorialoptimization instances—TSP and Assignment Problem; Aiming at constrained combinatorialoptimization problem, we analyze the runtime of (1+λ)EA on a0-1knapsack probleminstance. These work extend the scope of the time complexity analysis of EAs, enrich the timecomplexity research of EAs on real-world combinatorial optimization problems.