Expected Approximation Error Analysis Of Randomized Search Heuristics

At present,Randomized Search Heuristics（RSH）has been widely used in scientific research and engineering calculations,but its performance in solving different optimization problems is quite different,so it is necessary for us to carry out theoretical analysis on it,and guide the design and application of the algorithm according to the research results.However,theoretical research on randomized search heuristics is mainly to evaluate the performance of the algorithm by analyzing the first hitting time or running time of the algorithm to solve the optimization problem and the theoretical analysis results are difficult to apply to the accurate estimation of the approximation error in the process of algorithm design and application.In view of this,this thesis uses the expected approximation error as an index to evaluate the performance of the algorithm to conduct theoretical research on the randomized search heuristics.First,this thesis proposes a general framework for the analysis of the expected approximate error.By establishing a homogeneous Markov chain model of the randomized search heuristics,combined with the transition probability matrix,the initial probability distribution and the approximate error distribution,we deduce the expression of the expected approximate error corresponding to the algorithm at any time.When the transition probability matrix is a bidiagonal matrix,we can obtain the exact expression of the expected approximate error by the method of matrix diagonalization.For the elitist randomized search heuristics,we construct auxiliary bidiagonal transition probability matrix to replace its upper triangular transition probability matrix to estimate its expected approximate error.Secondly,this thesis takes Random Local Search（RLS）and（1+1）EA as the research objects,and analyzes their expected approximate errors in solving the One Max problem,the deception problem and the knapsack problem.We define the states and transition probability matrices of algorithms to solve these optimization problems,and use mathematical tools such as matrix block and diagonalization,and finally derive the expected approximate error estimation results of the algorithm to solve these optimization problems.The results show that the expected approximate error analysis can be applied to unimodal or multimodal optimization problems,and even can be analyzed with constraints conditional knapsack problem,thus illustrating the feasibility of the expected approximate error analysis framework.Finally,in order to explore the influence of the binomial crossover operator on the performance of evolutionary algorithms,this thesis uses（1+1）EA and its two variant algorithms with binomial crossover operators（1+1）EA_Cand（1+1）EA_CMis the research object.Based on the analysis of transition probability,expected approximate error and tail probability,the results show that（1+1）EA_Cand（1+1）EA_CMwith binomial crossover operator have stronger global search ability than（1+1）EA,but their local development ability is weaker than（1+1）EA.In addition,according to the monotonicity analysis of transition probability,we propose the parameter adaptive strategy for these three algorithms to solve the deception problem,and through numerical simulations,it is shown that the algorithm performance is improved after adding the parameter adaptive strategy.