How to Treat Evolutionary Algorithms as Ordinary Randomized Algorithms

on YouTube ↗52m

" summary

Drift analysis turns one-step expected progress into global runtime bounds, using the multiplicative drift theorem to prove the 1+1 EA finds OneMax and every linear function in about e n ln n steps (up to lower-order terms), shows a mutation probability 1/n is optimal across linear functions, identifies a phase transition around p ≈ log n / n, proves 1+1 EA is optimal among mutation/selection variants for these problems, and extends to tail bounds giving strong concentration of runtimes.

AI-written summary · about

" chapters (19)

1. 0:00Intro
2. 0:23Context
3. 4:27Drift Analysis: Idea
4. 7:43A Simple Scenario: Additive Drift
5. 15:39A Warm-up Example Using Multiplicative Drift
6. 19:20Further Applications of Drift Analysis
7. 20:23Linear Functions Generalized One Max
8. 21:22The Setting
9. 25:21What Makes Analysis of (1+1) EA Difficult
10. 28:42Discussion of Distance Function
11. 31:01Finding the Right Potential Function
12. 33:00New Potential Function Proves Upper Bound
13. 34:57Recent Developments
14. 35:20Why Expected Time is Not Enough
15. 36:52Sharp Concentration of Measure
16. 40:03Sharp Concentration of Running Times
17. 43:00Drift Analysis and Probabilistic Recurrences
18. 49:07Sharp Tail Bound on No. of Cycles
19. 50:12Summary