BASIN_HOPPING

Overview

The BASIN_HOPPING function performs global optimization using the basin-hopping algorithm, a stochastic method designed to find the global minimum of functions with complex, multi-modal landscapes. Originally developed by David Wales and Jonathan Doye for molecular structure optimization, basin-hopping is particularly effective for problems with “funnel-like, but rugged” energy surfaces where many local minima are separated by large barriers.

Basin-hopping is a two-phase iterative algorithm that combines random perturbation with local minimization. Each iteration consists of three steps:

  1. Random displacement: The current position is perturbed by a random step within the specified stepsize
  2. Local minimization: A local optimizer (such as L-BFGS-B or Powell) finds the nearest local minimum
  3. Acceptance decision: The new minimum is accepted or rejected based on the Metropolis criterion

The Metropolis acceptance criterion always accepts steps that decrease the function value. Steps that increase the function value are accepted with probability:

P = \exp\left(-\frac{f(x_{\text{new}}) - f(x_{\text{old}})}{T}\right)

where T is the temperature parameter. Higher temperatures allow the algorithm to escape local minima by accepting uphill moves more frequently. For best results, T should be comparable to the typical difference in function values between local minima.

This implementation uses SciPy’s basinhopping function from the scipy.optimize module. The algorithm was originally described in Wales and Doye’s 1997 paper on Lennard-Jones cluster optimization and has since proven effective across physics, chemistry, and machine learning applications.

The stepsize parameter controls the magnitude of random perturbations—ideally it should match the typical separation between local minima. The function supports multiple local minimization methods including L-BFGS-B (default), Powell, BFGS, Nelder-Mead, and others available through scipy.optimize.minimize.

This example function is provided as-is without any representation of accuracy.

Excel Usage

=BASIN_HOPPING(func_expr, x_zero, niter, T, stepsize, bh_method)
  • func_expr (str, required): Objective function expression in terms of x (e.g., “x^2 + 10*sin(x)“).
  • x_zero (float, required): Initial guess for the global minimum.
  • niter (int, optional, default: 100): Number of basin-hopping iterations.
  • T (float, optional, default: 1): Temperature parameter controlling acceptance of higher-energy jumps.
  • stepsize (float, optional, default: 0.5): Step size for random displacement between basins.
  • bh_method (str, optional, default: “L-BFGS-B”): Local minimization method used within each basin.

Returns (list[list]): 2D list [[x, objective]], or error message string.

Example 1: Basic quadratic function x^2

Inputs:

func_expr x_zero niter
x**2 5 100

Excel formula:

=BASIN_HOPPING("x**2", 5, 100)

Expected output:

Result
1.29097e-11 1.6666e-22
Example 2: Multimodal sine function using caret notation

Inputs:

func_expr x_zero niter T stepsize
x^2 + 10*sin(x) 0 120 1.5 0.7

Excel formula:

=BASIN_HOPPING("x^2 + 10*sin(x)", 0, 120, 1.5, 0.7)

Expected output:

Result
-1.30644 -7.94582
Example 3: Exponential decay with cosine and quadratic terms

Inputs:

func_expr x_zero niter stepsize
exp(-x) * cos(2*x) + x^2/10 2 150 0.5

Excel formula:

=BASIN_HOPPING("exp(-x) * cos(2*x) + x^2/10", 2, 150, 0.5)

Expected output:

Result
1.16776 -0.0789942
Example 4: Composite trigonometric function with Powell method

Inputs:

func_expr x_zero niter T stepsize bh_method
(x2 - 4)2 + 5cos(2x) 2 200 1 0.5 Powell

Excel formula:

=BASIN_HOPPING("(x**2 - 4)**2 + 5*cos(2*x)", 2, 200, 1, 0.5, "Powell")

Expected output:

Result
1.82545 -3.91955

Python Code

Show Code 
import math
import re

import numpy as np
from scipy.optimize import basinhopping as scipy_basinhopping

def basin_hopping(func_expr, x_zero, niter=100, T=1, stepsize=0.5, bh_method='L-BFGS-B'):
    """
    Minimize a single-variable expression with SciPy's basinhopping algorithm.

    See: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.basinhopping.html

    This example function is provided as-is without any representation of accuracy.

    Args:
        func_expr (str): Objective function expression in terms of x (e.g., "x^2 + 10*sin(x)").
        x_zero (float): Initial guess for the global minimum.
        niter (int, optional): Number of basin-hopping iterations. Default is 100.
        T (float, optional): Temperature parameter controlling acceptance of higher-energy jumps. Default is 1.
        stepsize (float, optional): Step size for random displacement between basins. Default is 0.5.
        bh_method (str, optional): Local minimization method used within each basin. Valid options: L-BFGS-B, Powell, BFGS, Nelder-Mead, TNC, CG, SLSQP. Default is 'L-BFGS-B'.

    Returns:
        list[list]: 2D list [[x, objective]], or error message string.
    """
    try:
        if not isinstance(func_expr, str):
            return "Error: func_expr must be a string."
        if func_expr.strip() == "":
            return "Error: func_expr must be a non-empty string."

        func_expr = re.sub(r'\^', '**', func_expr)

        if not re.search(r'\bx\b', func_expr):
            return "Error: func_expr must reference variable x (e.g., x)."

        try:
            x_zero = float(x_zero)
            if not math.isfinite(x_zero):
                return "Error: x_zero must be a finite number."
        except (TypeError, ValueError):
            return "Error: x_zero must be a numeric value."

        try:
            niter = int(niter)
            if niter <= 0:
                return "Error: niter must be a positive integer."
        except (TypeError, ValueError):
            return "Error: niter must be an integer."

        try:
            T = float(T)
            if not math.isfinite(T):
                return "Error: T must be a finite number."
            if T < 0:
                return "Error: T must be non-negative."
        except (TypeError, ValueError):
            return "Error: T must be a numeric value."

        try:
            stepsize = float(stepsize)
            if not math.isfinite(stepsize):
                return "Error: stepsize must be a finite number."
            if stepsize <= 0:
                return "Error: stepsize must be positive."
        except (TypeError, ValueError):
            return "Error: stepsize must be a numeric value."

        if not isinstance(bh_method, str) or bh_method.strip() == "":
            return "Error: bh_method must be a non-empty string."

        safe_globals = {
            "math": math,
            "np": np,
            "numpy": np,
            "__builtins__": {},
        }
        safe_globals.update({
            name: getattr(math, name)
            for name in dir(math)
            if not name.startswith("_")
        })
        safe_globals.update({
            "sin": np.sin,
            "cos": np.cos,
            "tan": np.tan,
            "asin": np.arcsin,
            "arcsin": np.arcsin,
            "acos": np.arccos,
            "arccos": np.arccos,
            "atan": np.arctan,
            "arctan": np.arctan,
            "sinh": np.sinh,
            "cosh": np.cosh,
            "tanh": np.tanh,
            "exp": np.exp,
            "log": np.log,
            "ln": np.log,
            "log10": np.log10,
            "sqrt": np.sqrt,
            "abs": np.abs,
            "pow": np.power,
            "pi": math.pi,
            "e": math.e,
        })

        try:
            initial_eval = eval(func_expr, safe_globals, {"x": x_zero})
            initial_val = float(initial_eval)
            if not math.isfinite(initial_val):
                return "Error: Expression evaluates to non-finite value at initial guess."
        except Exception as exc:
            return f"Error: Invalid expression at initial guess: {exc}"

        def objective(x_value):
            try:
                if isinstance(x_value, np.ndarray):
                    x_scalar = float(x_value.item() if x_value.size == 1 else x_value[0])
                else:
                    x_scalar = float(x_value)
                result = eval(func_expr, safe_globals, {"x": x_scalar})
                numeric_value = float(result)
            except Exception as exc:
                raise ValueError(f"Error evaluating func_expr: {exc}")
            if not math.isfinite(numeric_value):
                raise ValueError("Objective evaluation produced NaN or infinity.")
            return numeric_value

        try:
            result = scipy_basinhopping(
                objective,
                x_zero,
                niter=niter,
                T=T,
                stepsize=stepsize,
                minimizer_kwargs={"method": bh_method},
            )
            if isinstance(result.x, np.ndarray):
                x_min = float(result.x.item() if result.x.size == 1 else result.x[0])
            else:
                x_min = float(result.x)
            min_val = float(result.fun)

            if not math.isfinite(x_min) or not math.isfinite(min_val):
                return "Error: Optimization produced non-finite results."

            return [[x_min, min_val]]
        except ValueError as exc:
            return f"Error during optimization: {exc}"
        except Exception as exc:
            return f"Error during optimization: {exc}"
    except Exception as e:
        return f"Error: {str(e)}"

Online Calculator

Objective function expression in terms of x (e.g., "x^2 + 10*sin(x)").
Initial guess for the global minimum.
Number of basin-hopping iterations.
Temperature parameter controlling acceptance of higher-energy jumps.
Step size for random displacement between basins.
Local minimization method used within each basin.