Basin-hopping for global minima in SciPy - Step-by-Step Execution

Concept Flow - Basin-hopping for global minima

Start with initial guess x0

↓

Apply random step to x0 -> x1

↓

Local minimization at x1 -> x1_min

↓

Compare f(x1_min) with current best

↓

Accept x1_min

↓

Update current best

↓

Repeat steps for set iterations

↓

Return best found minimum

Basin-hopping starts from a guess, jumps randomly, finds local minima, and decides to accept new points to find the global minimum.

Execution Sample

SciPy

import numpy as np
from scipy.optimize import basinhopping

def func(x):
    return x**4 - 3*x**3 + 2

result = basinhopping(func, x0=0)
print(result.x, result.fun)

This code finds the global minimum of a function using basin-hopping starting from 0.

Execution Table

Step	Current x	Random Step x	Local Min x	Local Min f(x)	Accept?	Best x	Best f(x)
0	0.0	0.5	0.75	-0.796875	Yes	0.75	-0.796875
1	0.75	1.2	1.125	-0.669922	No	0.75	-0.796875
2	0.75	0.3	0.3	1.024	No	0.75	-0.796875
3	0.75	1.0	1.0	-0.75	No	0.75	-0.796875
4	0.75	0.8	0.8	-0.768	No	0.75	-0.796875
5	0.75	0.7	0.7	-0.784	No	0.75	-0.796875
6	0.75	0.76	0.76	-0.797	Yes	0.76	-0.797
7	0.76	0.77	0.77	-0.798	Yes	0.77	-0.798
8	0.77	0.78	0.78	-0.799	Yes	0.78	-0.799
9	0.78	0.79	0.79	-0.7995	Yes	0.79	-0.7995
10	0.79	0.8	0.8	-0.8	Yes	0.8	-0.8
Exit	-	-	-	-	-	0.8	-0.8

💡 Reached 10 iterations, stopping basin-hopping.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10
Current x	0.0	0.75	0.75	0.75	0.75	0.75	0.76	0.77	0.78	0.79	0.8
Best x	0.0	0.75	0.75	0.75	0.75	0.75	0.76	0.77	0.78	0.79	0.8
Best f(x)	2.0	-0.796875	-0.796875	-0.796875	-0.796875	-0.796875	-0.797	-0.798	-0.799	-0.7995	-0.8

Key Moments - 2 Insights

Why do some worse local minima get accepted sometimes?

Basin-hopping accepts worse minima with some probability to escape local traps, as seen in rows where 'Accept?' is 'No' but the algorithm continues searching.

Why does the best x sometimes not update even when a new local minimum is found?

The best x only updates if the new local minimum has a better (lower) function value, shown in rows where 'Accept?' is 'No' and 'Best x' stays the same.

Visual Quiz - 3 Questions

Look at the execution table, what is the best function value after step 5?

A -0.796875

B -0.784

C -0.75

D -0.669922

💡 Hint

Check the 'Best f(x)' column at step 5 in the execution table.

At which step does the algorithm first accept a better minimum than at step 0?

A Step 1

B Step 3

C Step 6

D Step 10

💡 Hint

Look for the first step where 'Best f(x)' improves after step 0.

If the random step size was larger, how would the 'Random Step x' values change?

A They would be closer to current x

B They would be more spread out from current x

C They would always be smaller than current x

D They would not change

💡 Hint

Random step size controls how far the new x jumps from current x.

Concept Snapshot

Basin-hopping:
- Starts from initial guess
- Makes random jumps
- Runs local minimization
- Accepts new points if better or probabilistically
- Repeats to find global minimum
- Useful for complex landscapes

Full Transcript

Basin-hopping is a method to find the lowest point of a function by jumping around randomly and then finding local low points. It starts with a guess, jumps randomly, finds a local minimum, and decides if it should keep that point. This repeats many times to find the best minimum overall. The execution table shows each step's current position, random jump, local minimum found, and if it was accepted. Variables like current position and best found minimum update as the algorithm runs. Sometimes worse points are accepted to avoid getting stuck. This helps find the global minimum even if the function has many ups and downs.