Basin hopping<\/strong> is a global optimization algorithm.<\/p>\n It was developed to solve problems in chemical physics, although it is an effective algorithm suited for nonlinear objective functions with multiple optima.<\/p>\n In this tutorial, you will discover the basin hopping global optimization algorithm.<\/p>\n After completing this tutorial, you will know:<\/p>\n Let\u2019s get started.<\/p>\n Basin Hopping Optimization in Python This tutorial is divided into three parts; they are:<\/p>\n Basin Hopping is a global optimization algorithm developed for use in the field of chemical physics<\/a>.<\/p>\n Basin-Hopping (BH) or Monte-Carlo Minimization (MCM) is so far the most reliable algorithms in chemical physics to search for the lowest-energy structure of atomic clusters and macromolecular systems.<\/p>\n<\/blockquote>\n \u2014 Basin Hopping With Occasional Jumping<\/a>, 2004.<\/p>\n Local optimization<\/a> refers to optimization algorithms intended to locate an optima for a univariate objective function or operate in a region where an optima is believed to be present. Whereas global optimization<\/a> algorithms are intended to locate the single global optima among potentially multiple local (non-global) optimal.<\/p>\n Basin Hopping was described by David Wales and Jonathan Doye in their 1997 paper titled \u201cGlobal Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms<\/a>.\u201d<\/p>\n The algorithms involve cycling two steps, a perturbation of good candidate solutions and the application of a local search to the perturbed solution.<\/p>\n [Basin hopping] transforms the complex energy landscape into a collection of basins, and explores them by hopping, which is achieved by random Monte Carlo moves and acceptance\/rejection using the Metropolis criterion.<\/p>\n<\/blockquote>\n \u2014 Basin Hopping With Occasional Jumping<\/a>, 2004.<\/p>\n The perturbation allows the search algorithm to jump to new regions of the search space and potentially locate a new basin leading to a different optima, e.g. \u201cbasin hopping<\/em>\u201d in the techniques name.<\/p>\n The local search allows the algorithm to traverse the new basin to the optima.<\/p>\n The new optima may be kept as the basis for new random perturbations, otherwise, it is discarded. The decision to keep the new solution is controlled by a stochastic decision function with a \u201ctemperature<\/em>\u201d variable, much like simulated annealing<\/a>.<\/p>\n Temperature is adjusted as a function of the number of iterations of the algorithm. This allows arbitrary solutions to be accepted early in the run when the temperature is high, and a stricter policy of only accepting better quality solutions later in the search when the temperature is low.<\/p>\n In this way, the algorithm is much like an iterated local search with different (perturbed) starting points.<\/p>\n The algorithm runs for a specified number of iterations or function evaluations and can be run multiple times to increase confidence that the global optima was located or that a relative good solution was located.<\/p>\n Now that we are familiar with the basic hopping algorithm from a high level, let\u2019s look at the API for basin hopping in Python.<\/p>\n Basin hopping is available in Python via the basinhopping() SciPy function<\/a>.<\/p>\n The function takes the name of the objective function to be minimized and the initial starting point.<\/p>\n Another important hyperparameter is the number of iterations to run the search set via the \u201cniter<\/em>\u201d argument and defaults to 100.<\/p>\n This can be set to thousands of iterations or more.<\/p>\n The amount of perturbation applied to the candidate solution can be controlled via the \u201cstepsize<\/em>\u201d that defines the maximum amount of change applied in the context of the bounds of the problem domain. By default, this is set to 0.5 but should be set to something reasonable in the domain that might allow the search to find a new basin.<\/p>\n For example, if the reasonable bounds of a search space were -100 to 100, then perhaps a step size of 5.0 or 10.0 units would be appropriate (e.g. 2.5% or 5% of the domain).<\/p>\n By default, the local search algorithm used is the \u201cL-BFGS-B<\/em>\u201d algorithm.<\/p>\n This can be changed by setting the \u201cminimizer_kwargs<\/em>\u201d argument to a directory with a key of \u201cmethod<\/em>\u201d and the value as the name of the local search algorithm to use, such as \u201cnelder-mead<\/em>.\u201d Any of the local search algorithms provided by the SciPy library can be used.<\/p>\n The result of the search is a OptimizeResult object<\/a> where properties can be accessed like a dictionary. The success (or not) of the search can be accessed via the \u2018success<\/em>\u2018 or \u2018message<\/em>\u2018 key.<\/p>\n The total number of function evaluations can be accessed via \u2018nfev<\/em>\u2018 and the optimal input found for the search is accessible via the \u2018x<\/em>\u2018 key.<\/p>\n Now that we are familiar with the basin hopping API in Python, let\u2019s look at some worked examples.<\/p>\n In this section, we will look at some examples of using the basin hopping algorithm on multi-modal objective functions.<\/p>\n Multimodal objective functions are those that have multiple optima, such as a global optima and many local optima, or multiple global optima with the same objective function output.<\/p>\n We will look at examples of basin hopping on both functions.<\/p>\n The Ackley function<\/a> is an example of an objective function that has a single global optima and multiple local optima in which a local search might get stuck.<\/p>\n As such, a global optimization technique is required. It is a two-dimensional objective function that has a global optima at [0,0], which evaluates to 0.0.<\/p>\n The example below implements the Ackley and creates a three-dimensional surface plot showing the global optima and multiple local optima.<\/p>\n Running the example creates the surface plot of the Ackley function showing the vast number of local optima.<\/p>\n 3D Surface Plot of the Ackley Multimodal Function<\/p>\n<\/div>\n We can apply the basin hopping algorithm to the Ackley objective function.<\/p>\n In this case, we will start the search using a random point drawn from the input domain between -5 and 5.<\/p>\n We will use a step size of 0.5, 200 iterations, and the default local search algorithm. This configuration was chosen after a little trial and error.<\/p>\n After the search is complete, it will report the status of the search and the number of iterations performed as well as the best result found with its evaluation.<\/p>\n Tying this together, the complete example of applying basin hopping to the Ackley objective function is listed below.<\/p>\n Running the example executes the optimization, then reports the results.<\/p>\n Note<\/strong>: Your results may vary<\/a> given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.<\/p>\n In this case, we can see that the algorithm located the optima with inputs very close to zero and an objective function evaluation that is practically zero.<\/p>\n We can see that 200 iterations of the algorithm resulted in 86,020 function evaluations.<\/p>\n\n
![\"Basin](\"https:\/\/machinelearningmastery.com\/wp-content\/uploads\/2021\/01\/Basin-Hopping-Optimization-in-Python.jpg\")
<\/p>\n
Photo by Pedro Szekely<\/a>, some rights reserved.<\/p>\n<\/div>\nTutorial Overview<\/h2>\n
\n
\n
Basin Hopping Optimization<\/h2>\n
\n
\n
Basin Hopping API<\/h2>\n
...\r\n# perform the basin hopping search\r\nresult = basinhopping(objective, pt)<\/pre>\n
...\r\n# perform the basin hopping search\r\nresult = basinhopping(objective, pt, niter=10000)<\/pre>\n
...\r\n# perform the basin hopping search\r\nresult = basinhopping(objective, pt, stepsize=10.0)<\/pre>\n
...\r\n# perform the basin hopping search\r\nresult = basinhopping(objective, pt, minimizer_kwargs={'method':'nelder-mead'})<\/pre>\nBasin Hopping Examples<\/h2>\n
Multimodal Optimization With Local Optima<\/h3>\n
# ackley multimodal function\r\nfrom numpy import arange\r\nfrom numpy import exp\r\nfrom numpy import sqrt\r\nfrom numpy import cos\r\nfrom numpy import e\r\nfrom numpy import pi\r\nfrom numpy import meshgrid\r\nfrom matplotlib import pyplot\r\nfrom mpl_toolkits.mplot3d import Axes3D\r\n\r\n# objective function\r\ndef objective(x, y):\r\n\treturn -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\r\n\r\n# define range for input\r\nr_min, r_max = -5.0, 5.0\r\n# sample input range uniformly at 0.1 increments\r\nxaxis = arange(r_min, r_max, 0.1)\r\nyaxis = arange(r_min, r_max, 0.1)\r\n# create a mesh from the axis\r\nx, y = meshgrid(xaxis, yaxis)\r\n# compute targets\r\nresults = objective(x, y)\r\n# create a surface plot with the jet color scheme\r\nfigure = pyplot.figure()\r\naxis = figure.gca(projection='3d')\r\naxis.plot_surface(x, y, results, cmap='jet')\r\n# show the plot\r\npyplot.show()<\/pre>\n
![\"3D](\"https:\/\/machinelearningmastery.com\/wp-content\/uploads\/2020\/09\/3D-Surface-Plot-of-the-Ackley-Multimodal-Function-1.png\")
<\/p>\n...\r\n# define the starting point as a random sample from the domain\r\npt = r_min + rand(2) * (r_max - r_min)<\/pre>\n
...\r\n# perform the basin hopping search\r\nresult = basinhopping(objective, pt, stepsize=0.5, niter=200)<\/pre>\n
...\r\n# summarize the result\r\nprint('Status : %s' % result['message'])\r\nprint('Total Evaluations: %d' % result['nfev'])\r\n# evaluate solution\r\nsolution = result['x']\r\nevaluation = objective(solution)\r\nprint('Solution: f(%s) = %.5f' % (solution, evaluation))<\/pre>\n# basin hopping global optimization for the ackley multimodal objective function\r\nfrom scipy.optimize import basinhopping\r\nfrom numpy.random import rand\r\nfrom numpy import exp\r\nfrom numpy import sqrt\r\nfrom numpy import cos\r\nfrom numpy import e\r\nfrom numpy import pi\r\n\r\n# objective function\r\ndef objective(v):\r\n\tx, y = v\r\n\treturn -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\r\n\r\n# define range for input\r\nr_min, r_max = -5.0, 5.0\r\n# define the starting point as a random sample from the domain\r\npt = r_min + rand(2) * (r_max - r_min)\r\n# perform the basin hopping search\r\nresult = basinhopping(objective, pt, stepsize=0.5, niter=200)\r\n# summarize the result\r\nprint('Status : %s' % result['message'])\r\nprint('Total Evaluations: %d' % result['nfev'])\r\n# evaluate solution\r\nsolution = result['x']\r\nevaluation = objective(solution)\r\nprint('Solution: f(%s) = %.5f' % (solution, evaluation))<\/pre>\nStatus: ['requested number of basinhopping iterations completed successfully']\r\nTotal Evaluations: 86020\r\nSolution: f([ 5.29778873e-10 -2.29022817e-10]) = 0.00000<\/pre>\n<\/p>\n
Multimodal Optimization With Multiple Global Optima<\/h3>\n
![\"3D](\"https:\/\/machinelearningmastery.com\/wp-content\/uploads\/2020\/09\/3D-Surface-Plot-of-the-Himmelblau-Multimodal-Function.png\")
<\/p>\n