General Approaches to Running Time Analysis of Evolutionary Optimization

Modified: 2016/02/16 17:06 by admin - Uncategorized
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 proved to be reducible to switch analysis in the TEC'15 (PDF) paper, and the convergence-based approach is also reducible to switch analysis proved in the CEC'15 (PDF) paper.

  • 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.

The end