Running Time Analysis Of Evolutionary Algorithm On Continuous Domain

Evolutionary algorithms(EAs)has attracted the attention of researchers continu-ously since it was brought out and has been widely applied in engineering fields.As population-based stochastic optimization algorithms,EAs can not only overcome the shortcomings of traditional optimization algorithms,such as dependence on the gradi-ent or Hessien matrix,bad performance on multi-modal objective functions,sensitive-ness to the selection of the initial points,but also show excellent performance in solving real-life problems.The randomness of the evolving process,however,makes it hard to analysis its time complexity and becomes a bottleneck of the development of EAs.During the past two decades,running time analysis of EAs has been a hot topic among the evolution community.Lots of theoretical works have sprung out,ranging from qualitative analysis in the beginning to recent quantitative analysis.However,most of the works focus on discrete evolutionary algorithms.Continuous optimization problems are more generally met in real-world applications,but few theoretical works are about them.Thus,we mainly concern about the continuous domain.The main contributions of this thesis could be summarized as follows,1.Summarizing the theoretical works in the domain of continuous evlotionary al-gorithms.We introduce the local performance analysis and asymptotic analysis,respectively.Literature concerned with asymtotic analysis is divided into two classes:individual-based and population-based.2.Improving the lower bound of the ES using uniform mutation operator inside a hypersphere.Mutation operator is one of the most important parts of EAs which controls the searching behavior of the algorithm,and affects the running time directly.In this thesis,we consider one of the most common mutation operators-uniform mutation,and improve the state-of-the-art bound ?(n)to ?(ecn),i.e.,from polynomial to exponential.3.Analyzing the utility of the 1/5-rule on ES using uniform mutation inside a hy-persphere.1/5-rule is a frequently-used adaptive strategy which adjusts the co-efficients of mutation operator for the continuous EAs.In this thesis,we proof that for the ES with uniform mutation operator solving the sphere function,using 1/5-rule can reduce the time complexity from ?(ecn)to ?(n),i.e.,exponential to polynomial.