Back History
Analysis of Approximation Ability of Evolutionary Optimization

Evolutionary algorithms are most commonly used to obtain "good-enough" solutions in practice, which relates to their approximation ability.

'''Papers''':

* <b>Analysis framework.</b> In the  [http://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/aij12EAprx.pdf|AIJ'12 (PDF)] paper, we proposed a framework to characterize the approximation ability of a kind of evolutionary algorithms, leading to a general approximation guarantee. On k-set cover problem, it can achieve the currently best-achievable approximation ratio, revealing the advantage of evolutionary algorithms over the well known greedy algorithm.

* <b>Crossover is helpful:</b> In the [^{UP}papers/aij13-mocrossover.pdf|AIJ'13 (PDF)], we disclosed that crossover operator can help fulfill the Pareto front in multi-objective optimization tasks. As a consequence, on the bi-objective Minimum Spanning Tree problem, a multi-objective EA with a crossover operator is proved to improve the running time from that without the crossover for achieving a 2-approximate solution.