.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "api/gallery/optimization/annealing/plot_01_simulated_annealing.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` to download the full example code or to run this example in your browser via JupyterLite. .. rst-class:: sphx-glr-example-title .. _sphx_glr_api_gallery_optimization_annealing_plot_01_simulated_annealing.py: Kirkpatrick, Gelatt and Vecchi's simulated annealing ==================================================== Gradient methods slide into the nearest valley. Kirkpatrick, Gelatt and Vecchi (1983) borrowed the Metropolis rule from statistical physics: accept any downhill move, and an uphill move of size :math:`\Delta f` with probability :math:`e^{-\Delta f/T}`, while the temperature :math:`T` is lowered slowly, as in annealing a metal. Rastrigin's function :math:`f(x) = 10n + \sum_i (x_i^2 - 10\cos 2\pi x_i)` has a local minimum near every integer point and its global minimum :math:`f = 0` at the origin. .. GENERATED FROM PYTHON SOURCE LINES 17-33 .. code-block:: Python import matplotlib.pyplot as plt import numpy as np from scipy import optimize from mathematicskit.optimization import GradientDescentLineSearch, simulated_annealing def rastrigin(x): x = np.asarray(x) return 10 * x.shape[0] + np.sum(x**2 - 10 * np.cos(2 * np.pi * x), axis=0) def rastrigin_grad(x): return 2 * x + 20 * np.pi * np.sin(2 * np.pi * x) .. GENERATED FROM PYTHON SOURCE LINES 34-36 In two dimensions: descent gets trapped, annealing does not ------------------------------------------------------------- .. GENERATED FROM PYTHON SOURCE LINES 36-64 .. code-block:: Python x0 = np.array([4.4, -3.6]) descent = GradientDescentLineSearch(tol=1e-8).minimize(rastrigin, rastrigin_grad, x0) annealed = simulated_annealing(lambda x: float(rastrigin(x)), x0, step_size=0.4, t0=20.0, cooling=0.9995, n_iter=15000, seed=3) reference = optimize.dual_annealing(lambda x: float(rastrigin(x)), bounds=[(-5.12, 5.12)] * 2, seed=0) print(f"gradient descent : x = {descent.x.round(3)}, f = {descent.fun:.3f} (a local minimum)") print(f"simulated annealing : x = {annealed.x.round(3)}, f = {annealed.fun:.4f}") print(f"scipy dual_annealing : x = {reference.x.round(3)}, f = {reference.fun:.4f}") grid = np.linspace(-5.12, 5.12, 300) gx, gy = np.meshgrid(grid, grid) fig, (ax0, ax1) = plt.subplots(1, 2, figsize=(13, 5.2)) ax0.contourf(gx, gy, rastrigin(np.array([gx, gy])), levels=30, cmap="Greys") ax0.plot(*annealed.path[::10].T, "-", color="tab:orange", lw=0.6, alpha=0.8, label="simulated annealing") ax0.plot(*descent.path.T, "o-", color="tab:blue", ms=3, label="gradient descent") ax0.plot(*x0, "k^", ms=10, label="start") ax0.plot(0, 0, "r*", ms=14, label="global minimum") ax0.set_aspect("equal") ax0.legend(loc="lower left", fontsize=8) ax0.set_title("Rastrigin's function in 2D") ax1.semilogy(annealed.extra["energies"] + 1e-3, lw=0.7, color="tab:orange", label="f(current state) + 0.001") ax1.semilogy(annealed.extra["temperatures"], "k--", lw=1, label="temperature T") ax1.set_xlabel("step") ax1.set_title("The energy follows the temperature down") ax1.legend(fontsize=8) fig.tight_layout() .. image-sg:: /api/gallery/optimization/annealing/images/sphx_glr_plot_01_simulated_annealing_001.png :alt: Rastrigin's function in 2D, The energy follows the temperature down :srcset: /api/gallery/optimization/annealing/images/sphx_glr_plot_01_simulated_annealing_001.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none gradient descent : x = [-2.985 0.995], f = 9.950 (a local minimum) simulated annealing : x = [0.002 0.006], f = 0.0083 scipy dual_annealing : x = [-0. -0.], f = 0.0000 .. GENERATED FROM PYTHON SOURCE LINES 65-72 In eight dimensions: the cooling schedule matters --------------------------------------------------- With :math:`T = 0` (a "quench") the method only accepts downhill moves and stops in a high local minimum. Cooling more slowly lets the walk cross more barriers before it freezes, and ends lower. Each schedule is run from the same start with eight different random seeds. .. GENERATED FROM PYTHON SOURCE LINES 72-90 .. code-block:: Python x0_8d = np.full(8, 3.5) schedules = {"quench (T = 0)": lambda k: 0.0, "fast, 0.99^k": 0.99, "medium, 0.999^k": 0.999, "slow, 0.9997^k": 0.9997} finals = {} for name, cooling in schedules.items(): runs = [simulated_annealing(lambda x: float(rastrigin(x)), x0_8d, step_size=0.3, t0=30.0, cooling=cooling, n_iter=20000, seed=s) for s in range(8)] finals[name] = [r.fun for r in runs] print(f"{name:16s}: best f over 8 runs = {min(finals[name]):6.2f}, median {np.median(finals[name]):6.2f}") fig, ax = plt.subplots(figsize=(7, 4)) for k, values in enumerate(finals.values()): ax.plot(np.full(len(values), k) + np.linspace(-0.1, 0.1, len(values)), values, "o", alpha=0.7) ax.set_xticks(range(len(finals)), list(finals)) ax.set_ylabel("final f (global minimum 0)") ax.set_title("8-D Rastrigin: slower cooling finds deeper minima") fig.tight_layout() plt.show() .. image-sg:: /api/gallery/optimization/annealing/images/sphx_glr_plot_01_simulated_annealing_002.png :alt: 8-D Rastrigin: slower cooling finds deeper minima :srcset: /api/gallery/optimization/annealing/images/sphx_glr_plot_01_simulated_annealing_002.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none quench (T = 0) : best f over 8 runs = 50.97, median 72.18 fast, 0.99^k : best f over 8 runs = 25.24, median 40.65 medium, 0.999^k : best f over 8 runs = 24.73, median 37.07 slow, 0.9997^k : best f over 8 runs = 11.91, median 23.14 .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 3.009 seconds) .. _sphx_glr_download_api_gallery_optimization_annealing_plot_01_simulated_annealing.py: .. only:: html .. container:: sphx-glr-footer sphx-glr-footer-example .. container:: lite-badge .. image:: images/jupyterlite_badge_logo.svg :target: ../../../../lite/lab/index.html?path=api/gallery/optimization/annealing/plot_01_simulated_annealing.ipynb :alt: Launch JupyterLite :width: 150 px .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_01_simulated_annealing.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_01_simulated_annealing.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: plot_01_simulated_annealing.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_