Research On Theory Of Evolutionary Algorithms In Uncertain Environments

Evolutionary algorithms(EAs)are a class of randomized optimization algorithms,inspired by natural evolution.EAs have many advantages,for example,they have little requirements on the optimization problems and they are easy to implement in parallel.Thus EAs have been widely applied to solve real-world optimization problems.In these real-world optimization problems,the objectives are often subject to uncertainties,for example,the objectives are non-unique(i.e.,multi-objective optimization)and the eval-uation is non-exact(i.e.,noisy optimization).Recently,theoretical analysis,particularly running time analysis,of EAs has achieved a lot of progresses.But most existing theo-retical studies focus on exact optimization,the presence of uncertainty further increases the difficulty of analysis,and only a few results for uncertain optimizatioin have been reported.The unsubstantial theoretical foundation restricts the application of EAs for real-world optimization problems,and also restricts the development of EAs.In this thesis,we investigate the theoretical foundation of EAs solving uncertain optimization problems.The main contributions include:(1)Porposing a general approach based on switch analysis to estimate the expected running time of multi-objective EAs(MOEAs),which is then applied to diverse situations.The few theoretical analyses for MOEAs are case-specific,which cannot provide a general guidance to analyze the running time of a given MOEA solving a given problem.Meanwhile,ad hoc analysis starting from scratch is quite difficult.In this thesis,we propose a general approach based on switch analysis for estimating the running time of MOEAs,and the application of the approach shows that the approach can apply to diverse situation and derive tight bounds.(2)Proposing a general noise model,whose effects on the optimization time of EAs are investigated,and analyzing the robustness of sampling and parent popu-lations to noise.The theoretical results of EAs under noise are few and there are many fundamental theoretical issues to be addressed,such as the impact of noise on EAs and effective noise handling strategies.In this thesis,we propose a general noise model,and analyze the running time of a simple EA under the noise.We further analyze the robust-ness of sampling and parent populations to noise,and the results provide a guidance for the usage of proper noise handling strategy.