optimization-algorithms-wiki

No Free Lunch theorem (for optimization)

The No Free Lunch (NFL) theorem (Wolpert & Macready, 1997 — primary source now paged as nfl-original-paper) states, informally, that averaged over all possible problems, no optimization algorithm outperforms any other — superior performance on one class of problems is paid for by inferior performance on another. There is no universally best optimizer; a method is only “good” relative to a problem class. Formally (Theorem 1): summed over all cost functions f, the probability of any cost-value sequence is identical for any two algorithms — see nfl-original-paper for the framework, the time-varying NFL, and the alignment/P(f) interpretation.

Why it’s the cluster’s thesis

The founding benchmark makes NFL concrete: on Dik’s MQL5 suite, the mathematically sophisticated cma-es ranked only ~38/45, the pragmatic BSA 20/45, and the elegant EMA / deterministic DOS near the bottom — reputation and sophistication did not predict rank. Hence this wiki’s standing rule: record every ranking with its benchmark context; treat “best optimizer” as benchmark-relative (see CLAUDE.md’s volatile-data caveat and synthesis).

Independent corroboration (beyond Dik)

The thesis no longer rests on one author’s suite. Authoritative, independent sources echo it:

• Wikipedia on GAs cites Steven Skiena’s skepticism that GAs are ever clearly the right tool — and that “alternative methods (simulated annealing, hill climbing) often outperform” them.
• simulated-annealing has a proven convergence-to-global guarantee that is practically useless (it “will usually exceed the time required for a complete search”) — asymptotics don’t beat NFL.
• test-functions-for-optimization exist precisely to expose where each optimizer breaks (unimodal vs. multimodal, separable vs. not) — benchmarks are designed around NFL.
• bayesian-optimization wins a different regime entirely (few, expensive evaluations), showing NFL bites across evaluation budget, not just landscape shape.

Caveat / nuance

NFL’s “averaged over all problems” premise is an idealization — real problems aren’t uniformly distributed, so structure-exploiting methods do win on realistic problem classes. NFL is a caution against universal claims, not a counsel of despair. (This also frames the open cma-es/BBOB tension: CMA-ES rates near the top on independent academic suites yet only ~38/45 on Dik’s — same algorithm, different problem distribution.)

Related

nfl-original-paper · metaheuristic-optimization · population-optimization-benchmark · exploration-vs-exploitation · test-functions-for-optimization · genetic-algorithm · simulated-annealing · bayesian-optimization · cma-es