E7441: Scientific computing in biology and biomedicine Short introduction to stochastic optimization Vlad Popovici, Ph.D. Fac. of Science - RECETOX Outline Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E7441: Scientific computing in biology and biomedicine 2 / 12 Introduction Let A ⊂ Rn and f : A → R a continuous function, A∗ = arg min f = {a ∈ A|f(a) ≤ f(x), ∀x ∈ A} If A is compact then A∗ ∅. Goal: find a good approximation of A∗. Metaheuristics: generate a sequence Xt : Ω → A of random n−dimensional vectors from a probability space. stochastic convergence ∀ϵ > 0, Pr(dist(Xt , A∗ ) < ϵ) → 1, as t → ∞ almost sure convergence Pr(Xt → A∗ , as t → ∞) = 1 Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E7441: Scientific computing in biology and biomedicine 3 / 12 Random search algorithms Let A = [0, 1]n ⊂ Rn and U(A) be the uniform distribution on A. Algorithm 1: Pure Random Search t ← 1; generate x0 ∼ U(A); while true do generate xt ∼ U(A); if f(xt ) < f(xt−1) then t ← t + 1; end end From Borel-Cantelli Lemma: Pr(Xt → A∗, as t → ∞) = 1 Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E7441: Scientific computing in biology and biomedicine 4 / 12 Exercise 1 - implement the PRS - see the Jupyter notebook. Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E7441: Scientific computing in biology and biomedicine 5 / 12 Accelerated Random Search in PRS the information from previous steps/attempts is not used ASR is confining the search around the current best choice when a better choice is found, the search space is reinitialized to full space let c > 0 be a shrinking factor, ρ > 0 the desired precision and let B(x, r) denote a ball of radius r centered at x Algorithm 2: Accelerated Random Search t → 1, r1 ← 1; generate x1 ∼ U(A); while true do generate yt ∼ U(B(xt , rt ) ∩ A); if f(yt ) < f(xt ) then xt+1 ← yt ; rt+1 = 1; else if rt ≥ ρ then xt+1 ← xt ; rt+1 ← rt /c; else rt+1 ← 1; t ← t + 1; Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E7441: Scientific computing in biology and biomedicine 6 / 12 Simulated Annealing inspired from physics: to reach an optimal (minimum) energy, the process of cooling (called annealing for metals) must not be too fast incorporates a stochastic process of escaping local minima the function f is now called “energy” or “cost function” and the parameter governing the escape process - “temperature” Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E7441: Scientific computing in biology and biomedicine 7 / 12 Algorithm 3: Simmulated Annealing generic algorithm initialize randomly x ∈ Rn ; x∗ ← x; // current best choice for k = 0, 1, . . . , Kmax do x′ ← nearby(x); if f(x′) < f(x) then x ← x′; else x ← x′ with probability Pr(f(x′), f(x), T); if f(x) < f(x∗) then x∗ ← x; return x∗ Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E7441: Scientific computing in biology and biomedicine 8 / 12 the acceptance of worse values for x allows exploring a space away from the current local minima a common probability function used is exp − f(x′) − f(x) T the temperature T may be constant or decreasing with time: start with T = 1 and then update T = Kmax −k Kmax Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E7441: Scientific computing in biology and biomedicine 9 / 12 Algorithm 4: Simulated annealing for continuous functions initialize randomly x ∈ Rn ; x∗ ← x; // current best choice for k = 0, 1, . . . , Kmax do x′ ← N(0, 1); T ← (Kmax − k)/Kmax; if f(x′) < f(x) or exp(−(f(x′) − f(x))/T) > rand() then x ← x′; if f(x) < f(x∗) then x∗ ← x; return x∗ Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E7441: Scientific computing in biology and biomedicine 10 / 12 Exercise 2 - implement the SA - see the Jupyter notebook. Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E7441: Scientific computing in biology and biomedicine 11 / 12 Practical stochastic optimization: In Python, PyMOO - https://pymoo.org/ stochopy - https://keurfonluu.github.io/stochopy/ Optuna - https://optuna.org/