2010 · 54 citations · 10 references
ComputingComputer ScienceAlgorithmsEvolutionary TheoryOptimizationAlgorithm AnalysisEvolutionary ComputationEvolutionary OptimizationGenetic AlgorithmsPopulation-based SearchBoolean Function RepresentationComplexity Of Boolean Functions
We regard the classical problem how the (1+1) Evolutionary Algorithm optimizes an arbitrary linear pseudo-Boolean function. We show that any such function is optimized in time (1 + o(1)) 1.39en ln (n), where n is the length of the bit string. We also prove a lower bound of (1 -o(1))en ln(n), which in fact holds for all functions with a unique global optimum. This shows that for linear functions, even though the optimization behavior might differ, the resulting runtimes are very similar. Our experimental results suggest that the true optimization times are even closer than what the theoretical guarantees promise.
10
Drift analysis and average time complexity of evolutionary algorithms
Jun He, Xin Yao · Artificial Intelligence · 2001 · 469 citations