Page History: General Approaches to Running Time Analysis of Evolutionary Optimization
Compare Page Revisions
Page Revision: 2016/02/16 16:54
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.
- Convergence-based analysis approach: In the 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.
- Switch analysis: In the 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.
- Reducibility: The drift analysis and the fitness level method are reducible to switch analysis (PDF-tec15), the convergence-based approach is also reducible to switch analysis (PDF-cec15).
- Application to class-wise analysis In the PPSN'12 (PDF) and 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.
- Application to constrained optimization: In the paper CEC'08 (PDF), we applied the convergence-based analysis approach to disclose that infeasible solutions in constrained optimization may not be useless.
- Application to analysis of crossover operators: In the PPSN'10 (PDF) paper, we applied the switch analysis to analyzing crossover operators.