Back
History
General Approaches to Running Time Analysis of Evolutionary Optimization
The running time, or the computational complexity, of evolutionary algorithms and other metaheuristic algorithms is one of the most important theoretical issues for understanding these algorithms. We develop tools analyze the complexity. '''Papers''': * <b>Convergence-based analysis approach:</b> In the [^http://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/aij08.pdf|AIJ'08 (PDF)] paper, we proposed the ''convergence-based approach'' that can be applied to obtain running time bounds of a large range of metaheuristic algorithms. * <b>Switch analysis:</b> In the [^{UP}papers/tec15-switch.pdf|TEC'15 (PDF)] paper, we developed the ''switch analysis'' method for running time analysis of evolutionary algorithms. It compares two algorithm processes (i.e., two Markov chains), leading to the relationship of the expected running time of the two processes. ** <b>Reducibility:</b> The ''drift analysis'' and the ''fitness level method'' are proved to be reducible to ''switch analysis'' in the [^{UP}papers/tec15-switch.pdf|TEC'15 (PDF)] paper, and the ''convergence-based approach'' is also reducible to ''switch analysis'' proved in the [^{UP}papers/cec15-sa-ca.pdf|CEC'15 (PDF)] paper. * <b>Application to class-wise analysis</b> In the [^{UP}papers/ppsn12-boundary.pdf|PPSN'12 (PDF)] and [^{UP}papers/tec15-switch.pdf|TEC'15 (PDF)] papers, using ''switch analysis'' to compare problem instances, we identified the hardest and the easiest problem instances for an evolutionary algorithm in a large problem class. * <b>Application to constrained optimization</b>: In the paper [^http://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/cec08.pdf|CEC'08 (PDF)], we applied the convergence-based analysis approach to disclose that infeasible solutions in constrained optimization may not be useless. * <b>Application to analysis of crossover operators</b>: In the [^http://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/ppsn10crossover.pdf|PPSN'10 (PDF)] paper, we applied the switch analysis to analyzing crossover operators.
The end