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