Basin Hopping Optimization in Python

Last Updated on October 12, 2023

Basin hopping is a world optimization algorithm.

It was developed to unravel points in chemical physics, although it is an environment friendly algorithm fitted to nonlinear purpose capabilities with a variety of optima.

In this tutorial, you will uncover the basin hopping world optimization algorithm.

After ending this tutorial, you will know:

• Basin hopping optimization is a world optimization that makes use of random perturbations to leap basins, and an space search algorithm to optimize each basin.
• How to utilize the basin hopping optimization algorithm API in python.
• Examples of using basin hopping to unravel world optimization points with a variety of optima.

Kick-start your problem with my new e-book Optimization for Machine Learning, along with step-by-step tutorials and the Python provide code recordsdata for all examples.

Let’s get started.

Basin Hopping Optimization in Python
Photo by Pedro Szekely, some rights reserved.

Tutorial Overview

This tutorial is cut up into three parts; they’re:

1. Basin Hopping Optimization
2. Basin Hopping API
3. Basin Hopping Examples
   1. Multimodal Optimization With Local Optima
   2. Multimodal Optimization With Multiple Global Optima

Basin Hopping Optimization

Basin Hopping is a world optimization algorithm developed for use inside the space of chemical physics.

Basin-Hopping (BH) or Monte-Carlo Minimization (MCM) is thus far basically essentially the most reliable algorithms in chemical physics to hunt for the lowest-energy development of atomic clusters and macromolecular applications.

— Basin Hopping With Occasional Jumping, 2004.

Local optimization refers to optimization algorithms supposed to search out an optima for a univariate purpose function or operate in a space the place an optima is believed to be present. Whereas global optimization algorithms are supposed to search out the one world optima amongst doubtlessly a variety of native (non-global) optimum.

Basin Hopping was described by David Wales and Jonathan Doye of their 1997 paper titled “Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms.”

The algorithms include biking two steps, a perturbation of superb candidate choices and the making use of of an space search to the perturbed decision.

[Basin hopping] transforms the sophisticated energy panorama right into a set of basins, and explores them by hopping, which is achieved by random Monte Carlo strikes and acceptance/rejection using the Metropolis criterion.

— Basin Hopping With Occasional Jumping, 2004.

The perturbation permits the search algorithm to leap to new areas of the search home and doubtlessly discover a model new basin leading to a definite optima, e.g. “basin hopping” inside the methods title.

The native search permits the algorithm to traverse the model new basin to the optima.

The new optima may be saved because the premise for model spanking new random perturbations, in another case, it is discarded. The decision to take care of the model new decision is managed by a stochastic decision function with a “temperature” variable, very like simulated annealing.

Temperature is adjusted as a function of the number of iterations of the algorithm. This permits arbitrary choices to be accepted early inside the run when the temperature is extreme, and a stricter protection of solely accepting greater prime quality choices later inside the search when the temperature is low.

In this way, the algorithm may be very like an iterated native search with utterly completely different (perturbed) starting components.

The algorithm runs for a specified number of iterations or function evaluations and could also be run a variety of events to increase confidence that the worldwide optima was located or {{that a}} relative good decision was located.

Now that we’re acquainted with the important hopping algorithm from a extreme stage, let’s check out the API for basin hopping in Python.

Want to Get Started With Optimization Algorithms?

Take my free 7-day e mail crash course now (with sample code).

Click to sign-up and as well as get a free PDF Ebook mannequin of the course.

Basin Hopping API

Basin hopping is in the marketplace in Python by way of the basinhopping() SciPy function.

The function takes the title of the goal function to be minimized and the preliminary place to start.

…<br /># perform the basin hopping search<br />consequence = basinhopping(purpose, pt)

1 2 3

... # perform the basin hopping search consequence = basinhopping(purpose, pt)

Another important hyperparameter is the number of iterations to run the search set by way of the “niter” argument and defaults to 100.

This could also be set to 1000’s of iterations or further.

…<br /># perform the basin hopping search<br />consequence = basinhopping(purpose, pt, niter=10000)

1 2 3

... # perform the basin hopping search consequence = basinhopping(purpose, pt, niter=10000)

The amount of perturbation utilized to the candidate decision could also be managed by way of the “stepsize” that defines the utmost amount of change utilized inside the context of the bounds of the difficulty space. By default, that’s set to 0.5 nevertheless should be set to 1 factor inexpensive inside the space which can allow the search to find a brand new basin.

For occasion, if the inexpensive bounds of a search home had been -100 to 100, then perhaps a step dimension of 5.0 or 10.0 fashions may very well be relevant (e.g. 2.5% or 5% of the realm).

…<br /># perform the basin hopping search<br />consequence = basinhopping(purpose, pt, stepsize=10.0)

1 2 3

... # perform the basin hopping search consequence = basinhopping(purpose, pt, stepsize=10.0)

By default, the native search algorithm used is the “L-BFGS-B” algorithm.

This could also be modified by setting the “minimizer_kwargs” argument to a list with a key of “method” and the value as a result of the title of the native search algorithm to utilize, equal to “nelder-mead.” Any of the native search algorithms provided by the SciPy library will be utilized.

…<br /># perform the basin hopping search<br />consequence = basinhopping(purpose, pt, minimizer_kwargs={‘method’:’nelder-mead’})

1 2 3

... # perform the basin hopping search consequence = basinhopping(purpose, pt, minimizer_kwargs={‘method’:‘nelder-mead’})

The outcomes of the search is a OptimizeResult object the place properties could also be accessed like a dictionary. The success (or not) of the search could also be accessed by way of the ‘success‘ or ‘message‘ key.

The full number of function evaluations could also be accessed by way of ‘nfev‘ and the optimum enter found for the search is accessible by way of the ‘x‘ key.

Now that we’re acquainted with the basin hopping API in Python, let’s check out some labored examples.

Basin Hopping Examples

In this half, we’re going to try some examples of using the basin hopping algorithm on multi-modal purpose capabilities.

Multimodal purpose capabilities are individuals who have a variety of optima, equal to a world optima and loads of native optima, or a variety of world optima with the similar purpose function output.

We will check out examples of basin hopping on every capabilities.

Multimodal Optimization With Local Optima

The Ackley function is an occasion of an purpose function that has a single world optima and a variety of native optima by way of which an space search might get caught.

As such, a world optimization technique is required. It is a two-dimensional purpose function that has a world optima at [0,0], which evaluates to 0.0.

The occasion beneath implements the Ackley and creates a three-dimensional flooring plot exhibiting the worldwide optima and a variety of native optima.

# ackley multimodal function<br />from numpy import arange<br />from numpy import exp<br />from numpy import sqrt<br />from numpy import cos<br />from numpy import e<br />from numpy import pi<br />from numpy import meshgrid<br />from matplotlib import pyplot<br />from mpl_toolkits.mplot3d import Axes3D</p><p># purpose function<br />def purpose(x, y):<br /> return -20.0 * exp(-0.2 * sqrt(0.5 * (x**2 + y**2))) – exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20</p><p># define fluctuate for enter<br />r_min, r_max = -5.0, 5.0<br /># sample enter fluctuate uniformly at 0.1 increments<br />xaxis = arange(r_min, r_max, 0.1)<br />yaxis = arange(r_min, r_max, 0.1)<br /># create a mesh from the axis<br />x, y = meshgrid(xaxis, yaxis)<br /># compute targets<br />outcomes = purpose(x, y)<br /># create a flooring plot with the jet coloration scheme<br />decide = pyplot.decide()<br />axis = decide.gca(projection=’3d’)<br />axis.plot_surface(x, y, outcomes, cmap=’jet’)<br /># current the plot<br />pyplot.current()

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

# ackley multimodal function from numpy import arange from numpy import exp from numpy import sqrt from numpy import cos from numpy import e from numpy import pi from numpy import meshgrid from matplotlib import pyplot from mpl_toolkits.mplot3d import Axes3D   # purpose function def purpose(x, y): return –20.0 * exp(–0.2 * sqrt(0.5 * (x**2 + y**2))) – exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20   # define fluctuate for enter r_min, r_max = –5.0, 5.0 # sample enter fluctuate uniformly at 0.1 increments xaxis = arange(r_min, r_max, 0.1) yaxis = arange(r_min, r_max, 0.1) # create a mesh from the axis x, y = meshgrid(xaxis, yaxis) # compute targets outcomes = purpose(x, y) # create a flooring plot with the jet coloration scheme decide = pyplot.decide() axis = decide.gca(projection=‘3d’) axis.plot_surface(x, y, outcomes, cmap=‘jet’) # current the plot pyplot.current()

Running the occasion creates the ground plot of the Ackley function exhibiting the large number of native optima.

3D Surface Plot of the Ackley Multimodal Function

We can apply the basin hopping algorithm to the Ackley purpose function.

In this case, we’re going to start the search using a random stage drawn from the enter space between -5 and 5.

We will use a step dimension of 0.5, 200 iterations, and the default native search algorithm. This configuration was chosen after just a bit trial and error.

…<br /># perform the basin hopping search<br />consequence = basinhopping(purpose, pt, stepsize=0.5, niter=200)

1 2 3

... # perform the basin hopping search consequence = basinhopping(purpose, pt, stepsize=0.5, niter=200)

After the search is full, it could possibly report the standing of the search and the number of iterations carried out along with the easiest consequence found with its evaluation.

…<br /># summarize the consequence<br />print(‘Status : %s’ % consequence[‘message’])<br />print(‘Total Evaluations: %d’ % consequence[‘nfev’])<br /># contemplate decision<br />decision = consequence[‘x’]<br />evaluation = purpose(decision)<br />print(‘Solution: f(%s) = %.5f’ % (decision, evaluation))

1 2 3 4 5 6 7 8

... # summarize the consequence print(‘Status : %s’ % consequence[‘message’]) print(‘Total Evaluations: %d’ % consequence[‘nfev’]) # contemplate decision decision = consequence[‘x’] evaluation = purpose(decision) print(‘Solution: f(%s) = %.5f’ % (decision, evaluation))

Tying this collectively, the entire occasion of constructing use of basin hopping to the Ackley purpose function is listed beneath.

# basin hopping world optimization for the ackley multimodal purpose function<br />from scipy.optimize import basinhopping<br />from numpy.random import rand<br />from numpy import exp<br />from numpy import sqrt<br />from numpy import cos<br />from numpy import e<br />from numpy import pi</p><p># purpose function<br />def purpose(v):<br /> x, y = v<br /> return -20.0 * exp(-0.2 * sqrt(0.5 * (x**2 + y**2))) – exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20</p><p># define fluctuate for enter<br />r_min, r_max = -5.0, 5.0<br /># define the place to start as a random sample from the realm<br />pt = r_min + rand(2) * (r_max – r_min)<br /># perform the basin hopping search<br />consequence = basinhopping(purpose, pt, stepsize=0.5, niter=200)<br /># summarize the consequence<br />print(‘Status : %s’ % consequence[‘message’])<br />print(‘Total Evaluations: %d’ % consequence[‘nfev’])<br /># contemplate decision<br />decision = consequence[‘x’]<br />evaluation = purpose(decision)<br />print(‘Solution: f(%s) = %.5f’ % (decision, evaluation))

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

# basin hopping world optimization for the ackley multimodal purpose function from scipy.optimize import basinhopping from numpy.random import rand from numpy import exp from numpy import sqrt from numpy import cos from numpy import e from numpy import pi   # purpose function def purpose(v): x, y = v return –20.0 * exp(–0.2 * sqrt(0.5 * (x**2 + y**2))) – exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20   # define fluctuate for enter r_min, r_max = –5.0, 5.0 # define the place to start as a random sample from the realm pt = r_min + rand(2) * (r_max – r_min) # perform the basin hopping search consequence = basinhopping(purpose, pt, stepsize=0.5, niter=200) # summarize the consequence print(‘Status : %s’ % consequence[‘message’]) print(‘Total Evaluations: %d’ % consequence[‘nfev’]) # contemplate decision decision = consequence[‘x’] evaluation = purpose(decision) print(‘Solution: f(%s) = %.5f’ % (decision, evaluation))

Running the occasion executes the optimization, then research the outcomes.

Note: Your outcomes may fluctuate given the stochastic nature of the algorithm or evaluation course of, or variations in numerical precision. Consider working the occasion a variety of events and consider the everyday last end result.

In this case, we’re capable of see that the algorithm located the optima with inputs very close to zero and an purpose function evaluation that is just about zero.

We can see that 200 iterations of the algorithm resulted in 86,020 function evaluations.

Status: [‘requested number of basinhopping iterations completed successfully’]<br />Total Evaluations: 86020<br />Solution: f([ 5.29778873e-10 -2.29022817e-10]) = 0.00000

1 2 3

Status: [‘requested number of basinhopping iterations completed successfully’] Total Evaluations: 86020 Solution: f([ 5.29778873e-10 -2.29022817e-10]) = 0.00000

Multimodal Optimization With Multiple Global Optima

The Himmelblau function is an occasion of an purpose function that has a variety of world optima.

Specifically, it has 4 optima and each has the similar purpose function evaluation. It is a two-dimensional purpose function that has a world optima at [3.0, 2.0], [-2.805118, 3.131312], [-3.779310, -3.283186], [3.584428, -1.848126].

This means each run of a world optimization algorithm may uncover a totally completely different world optima.

The occasion beneath implements the Himmelblau and creates a three-dimensional flooring plot to offer an intuition for the goal function.

# himmelblau multimodal check out function<br />from numpy import arange<br />from numpy import meshgrid<br />from matplotlib import pyplot<br />from mpl_toolkits.mplot3d import Axes3D</p><p># purpose function<br />def purpose(x, y):<br /> return (x**2 + y – 11)**2 + (x + y**2 -7)**2</p><p># define fluctuate for enter<br />r_min, r_max = -5.0, 5.0<br /># sample enter fluctuate uniformly at 0.1 increments<br />xaxis = arange(r_min, r_max, 0.1)<br />yaxis = arange(r_min, r_max, 0.1)<br /># create a mesh from the axis<br />x, y = meshgrid(xaxis, yaxis)<br /># compute targets<br />outcomes = purpose(x, y)<br /># create a flooring plot with the jet coloration scheme<br />decide = pyplot.decide()<br />axis = decide.gca(projection=’3d’)<br />axis.plot_surface(x, y, outcomes, cmap=’jet’)<br /># current the plot<br />pyplot.current()

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

# himmelblau multimodal check out function from numpy import arange from numpy import meshgrid from matplotlib import pyplot from mpl_toolkits.mplot3d import Axes3D   # purpose function def purpose(x, y): return (x**2 + y – 11)**2 + (x + y**2 –7)**2   # define fluctuate for enter r_min, r_max = –5.0, 5.0 # sample enter fluctuate uniformly at 0.1 increments xaxis = arange(r_min, r_max, 0.1) yaxis = arange(r_min, r_max, 0.1) # create a mesh from the axis x, y = meshgrid(xaxis, yaxis) # compute targets outcomes = purpose(x, y) # create a flooring plot with the jet coloration scheme decide = pyplot.decide() axis = decide.gca(projection=‘3d’) axis.plot_surface(x, y, outcomes, cmap=‘jet’) # current the plot pyplot.current()

Running the occasion creates the ground plot of the Himmelblau function exhibiting the 4 world optima as darkish blue basins.

3D Surface Plot of the Himmelblau Multimodal Function

We can apply the basin hopping algorithm to the Himmelblau purpose function.

As inside the earlier occasion, we’re going to start the search using a random stage drawn from the enter space between -5 and 5.

We will use a step dimension of 0.5, 200 iterations, and the default native search algorithm. At the highest of the search, we’re going to report the enter for the easiest located optima,

# basin hopping world optimization for the himmelblau multimodal purpose function<br />from scipy.optimize import basinhopping<br />from numpy.random import rand</p><p># purpose function<br />def purpose(v):<br /> x, y = v<br /> return (x**2 + y – 11)**2 + (x + y**2 -7)**2</p><p># define fluctuate for enter<br />r_min, r_max = -5.0, 5.0<br /># define the place to start as a random sample from the realm<br />pt = r_min + rand(2) * (r_max – r_min)<br /># perform the basin hopping search<br />consequence = basinhopping(purpose, pt, stepsize=0.5, niter=200)<br /># summarize the consequence<br />print(‘Status : %s’ % consequence[‘message’])<br />print(‘Total Evaluations: %d’ % consequence[‘nfev’])<br /># contemplate decision<br />decision = consequence[‘x’]<br />evaluation = purpose(decision)<br />print(‘Solution: f(%s) = %.5f’ % (decision, evaluation))

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

# basin hopping world optimization for the himmelblau multimodal purpose function from scipy.optimize import basinhopping from numpy.random import rand   # purpose function def purpose(v): x, y = v return (x**2 + y – 11)**2 + (x + y**2 –7)**2   # define fluctuate for enter r_min, r_max = –5.0, 5.0 # define the place to start as a random sample from the realm pt = r_min + rand(2) * (r_max – r_min) # perform the basin hopping search consequence = basinhopping(purpose, pt, stepsize=0.5, niter=200) # summarize the consequence print(‘Status : %s’ % consequence[‘message’]) print(‘Total Evaluations: %d’ % consequence[‘nfev’]) # contemplate decision decision = consequence[‘x’] evaluation = purpose(decision) print(‘Solution: f(%s) = %.5f’ % (decision, evaluation))

Running the occasion executes the optimization, then research the outcomes.

Want to Get Started With Ensemble Learning?

Take my free 7-day e mail crash course now (with sample code).

Click to sign-up and as well as get a free PDF Ebook mannequin of the course.

In this case, we’re capable of see that the algorithm located an optima at about [3.0, 2.0].

We can see that 200 iterations of the algorithm resulted in 7,660 function evaluations.

Status : [‘requested number of basinhopping iterations completed successfully’]<br />Total Evaluations: 7660<br />Solution: f([3. 1.99999999]) = 0.00000

1 2 3

Status : [‘requested number of basinhopping iterations completed successfully’] Total Evaluations: 7660 Solution: f([3. 1.99999999]) = 0.00000

If we run the search as soon as extra, we may rely on a definite world optima to be located.

For occasion, beneath, we’re capable of see an optima located at about [-2.805118, 3.131312], utterly completely different from the sooner run.

Status : [‘requested number of basinhopping iterations completed successfully’]<br />Total Evaluations: 7636<br />Solution: f([-2.80511809 3.13131252]) = 0.00000

1 2 3

Status : [‘requested number of basinhopping iterations completed successfully’] Total Evaluations: 7636 Solution: f([-2.80511809 3.13131252]) = 0.00000

Further Reading

This half provides further belongings on the topic in case you’re searching for to go deeper.

Papers

• Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms, 1997.
• Basin Hopping With Occasional Jumping, 2004.

Books

• Energy Landscapes: Applications to Clusters, Biomolecules and Glasses, 2004.

APIs

• scipy.optimize.basinhopping API.
• scipy.optimize.OptimizeResult API.

Articles

• Global optimization, Wikipedia.
• Basin-hopping, Wikipedia.

Summary

In this tutorial, you discovered the basin hopping world optimization algorithm.

Specifically, you realized:

• Basin hopping optimization is a world optimization that makes use of random perturbations to leap basins, and an space search algorithm to optimize each basin.
• How to utilize the basin hopping optimization algorithm API in python.
• Examples of using basin hopping to unravel world optimization points with a variety of optima.

Do you should have any questions?
Ask your questions inside the suggestions beneath and I’ll do my best to answer.

Get a Handle on Modern Optimization Algorithms!

Develop Your Understanding of Optimization

…with just a few traces of python code

Discover how in my new Ebook:
Optimization for Machine Learning

It provides self-study tutorials with full working code on:
Gradient Descent, Genetic Algorithms, Hill Climbing, Curve Fitting, RMSProp, Adam,
and reasonably extra…

Bring Modern Optimization Algorithms to
Your Machine Learning Projects

See What’s Inside

More On This Topic

• 

  How to Implement Bayesian Optimization from Scratch…

• 

  Local Optimization Versus Global Optimization

• 

  Convex Optimization in R

• 

  Why Optimization Is Important in Machine Learning

• 

  Function Optimization With SciPy

• 

  A Gentle Introduction to Stochastic Optimization Algorithms