Cong Wang

Cong Wang, Jun He, Yu Chen et al.

Although differential evolution (DE) algorithms perform well on a large variety of complicated optimization problems, only a few theoretical studies are focused on the working principle of DE algorithms. To make the first attempt to reveal the function of binomial crossover, this paper aims to answer whether it can reduce the approximation error of evolutionary algorithms. By investigating the expected approximation error and the probability of not finding the optimum, we conduct a case study comparing two evolutionary algorithms with and without binomial crossover on two classical benchmark problems: OneMax and Deceptive. It is proven that using binomial crossover leads to the dominance of transition matrices. As a result, the algorithm with binomial crossover asymptotically outperforms that without crossover on both OneMax and Deceptive, and outperforms on OneMax, however, not on Deceptive. Furthermore, an adaptive parameter strategy is proposed which can strengthen the superiority of binomial crossover on Deceptive.

Cong Wang, Yu Chen, Jun He et al.

When globally optimal solutions of complicated optimization problems cannot be located by evolutionary algorithms (EAs) in polynomial expected running time, the hitting time/running time analysis is not flexible enough to accommodate the requirement of theoretical study, because sometimes we have no idea on what approximation ratio is available in polynomial expected running time. Thus, it is necessary to propose an alternative routine for the theoretical analysis of EAs. To bridge the gap between theoretical analysis and algorithm implementation, in this paper we perform an error analysis where expected approximation error is estimated to evaluate performances of randomized search heuristics (RSHs). Based on the Markov chain model of RSHs, the multi-step transition matrix can be computed by diagonalizing the one-step transition matrix, and a general framework for estimation of expected approximation errors is proposed. Case studies indicate that the error analysis works well for both uni- and multi-modal benchmark problems. It leads to precise estimations of approximation error instead of asymptotic results on fitness values, which demonstrates its competitiveness to fixed budget analysis.