Coverage for /usr/lib/python3/dist-packages/scipy/optimize/_basinhopping.py: 17%
210 statements
« prev ^ index » next coverage.py v7.9.1, created at 2025-06-14 15:55 +0200
1"""
2basinhopping: The basinhopping global optimization algorithm
3"""
4import numpy as np
5import math
6import inspect
7import scipy.optimize
8from scipy._lib._util import check_random_state
10__all__ = ['basinhopping']
13_params = (inspect.Parameter('res_new', kind=inspect.Parameter.KEYWORD_ONLY),
14 inspect.Parameter('res_old', kind=inspect.Parameter.KEYWORD_ONLY))
15_new_accept_test_signature = inspect.Signature(parameters=_params)
18class Storage:
19 """
20 Class used to store the lowest energy structure
21 """
22 def __init__(self, minres):
23 self._add(minres)
25 def _add(self, minres):
26 self.minres = minres
27 self.minres.x = np.copy(minres.x)
29 def update(self, minres):
30 if minres.success and (minres.fun < self.minres.fun
31 or not self.minres.success):
32 self._add(minres)
33 return True
34 else:
35 return False
37 def get_lowest(self):
38 return self.minres
41class BasinHoppingRunner:
42 """This class implements the core of the basinhopping algorithm.
44 x0 : ndarray
45 The starting coordinates.
46 minimizer : callable
47 The local minimizer, with signature ``result = minimizer(x)``.
48 The return value is an `optimize.OptimizeResult` object.
49 step_taking : callable
50 This function displaces the coordinates randomly. Signature should
51 be ``x_new = step_taking(x)``. Note that `x` may be modified in-place.
52 accept_tests : list of callables
53 Each test is passed the kwargs `f_new`, `x_new`, `f_old` and
54 `x_old`. These tests will be used to judge whether or not to accept
55 the step. The acceptable return values are True, False, or ``"force
56 accept"``. If any of the tests return False then the step is rejected.
57 If ``"force accept"``, then this will override any other tests in
58 order to accept the step. This can be used, for example, to forcefully
59 escape from a local minimum that ``basinhopping`` is trapped in.
60 disp : bool, optional
61 Display status messages.
63 """
64 def __init__(self, x0, minimizer, step_taking, accept_tests, disp=False):
65 self.x = np.copy(x0)
66 self.minimizer = minimizer
67 self.step_taking = step_taking
68 self.accept_tests = accept_tests
69 self.disp = disp
71 self.nstep = 0
73 # initialize return object
74 self.res = scipy.optimize.OptimizeResult()
75 self.res.minimization_failures = 0
77 # do initial minimization
78 minres = minimizer(self.x)
79 if not minres.success:
80 self.res.minimization_failures += 1
81 if self.disp:
82 print("warning: basinhopping: local minimization failure")
83 self.x = np.copy(minres.x)
84 self.energy = minres.fun
85 self.incumbent_minres = minres # best minimize result found so far
86 if self.disp:
87 print("basinhopping step %d: f %g" % (self.nstep, self.energy))
89 # initialize storage class
90 self.storage = Storage(minres)
92 if hasattr(minres, "nfev"):
93 self.res.nfev = minres.nfev
94 if hasattr(minres, "njev"):
95 self.res.njev = minres.njev
96 if hasattr(minres, "nhev"):
97 self.res.nhev = minres.nhev
99 def _monte_carlo_step(self):
100 """Do one Monte Carlo iteration
102 Randomly displace the coordinates, minimize, and decide whether
103 or not to accept the new coordinates.
104 """
105 # Take a random step. Make a copy of x because the step_taking
106 # algorithm might change x in place
107 x_after_step = np.copy(self.x)
108 x_after_step = self.step_taking(x_after_step)
110 # do a local minimization
111 minres = self.minimizer(x_after_step)
112 x_after_quench = minres.x
113 energy_after_quench = minres.fun
114 if not minres.success:
115 self.res.minimization_failures += 1
116 if self.disp:
117 print("warning: basinhopping: local minimization failure")
118 if hasattr(minres, "nfev"):
119 self.res.nfev += minres.nfev
120 if hasattr(minres, "njev"):
121 self.res.njev += minres.njev
122 if hasattr(minres, "nhev"):
123 self.res.nhev += minres.nhev
125 # accept the move based on self.accept_tests. If any test is False,
126 # then reject the step. If any test returns the special string
127 # 'force accept', then accept the step regardless. This can be used
128 # to forcefully escape from a local minimum if normal basin hopping
129 # steps are not sufficient.
130 accept = True
131 for test in self.accept_tests:
132 if inspect.signature(test) == _new_accept_test_signature:
133 testres = test(res_new=minres, res_old=self.incumbent_minres)
134 else:
135 testres = test(f_new=energy_after_quench, x_new=x_after_quench,
136 f_old=self.energy, x_old=self.x)
138 if testres == 'force accept':
139 accept = True
140 break
141 elif testres is None:
142 raise ValueError("accept_tests must return True, False, or "
143 "'force accept'")
144 elif not testres:
145 accept = False
147 # Report the result of the acceptance test to the take step class.
148 # This is for adaptive step taking
149 if hasattr(self.step_taking, "report"):
150 self.step_taking.report(accept, f_new=energy_after_quench,
151 x_new=x_after_quench, f_old=self.energy,
152 x_old=self.x)
154 return accept, minres
156 def one_cycle(self):
157 """Do one cycle of the basinhopping algorithm
158 """
159 self.nstep += 1
160 new_global_min = False
162 accept, minres = self._monte_carlo_step()
164 if accept:
165 self.energy = minres.fun
166 self.x = np.copy(minres.x)
167 self.incumbent_minres = minres # best minimize result found so far
168 new_global_min = self.storage.update(minres)
170 # print some information
171 if self.disp:
172 self.print_report(minres.fun, accept)
173 if new_global_min:
174 print("found new global minimum on step %d with function"
175 " value %g" % (self.nstep, self.energy))
177 # save some variables as BasinHoppingRunner attributes
178 self.xtrial = minres.x
179 self.energy_trial = minres.fun
180 self.accept = accept
182 return new_global_min
184 def print_report(self, energy_trial, accept):
185 """print a status update"""
186 minres = self.storage.get_lowest()
187 print("basinhopping step %d: f %g trial_f %g accepted %d "
188 " lowest_f %g" % (self.nstep, self.energy, energy_trial,
189 accept, minres.fun))
192class AdaptiveStepsize:
193 """
194 Class to implement adaptive stepsize.
196 This class wraps the step taking class and modifies the stepsize to
197 ensure the true acceptance rate is as close as possible to the target.
199 Parameters
200 ----------
201 takestep : callable
202 The step taking routine. Must contain modifiable attribute
203 takestep.stepsize
204 accept_rate : float, optional
205 The target step acceptance rate
206 interval : int, optional
207 Interval for how often to update the stepsize
208 factor : float, optional
209 The step size is multiplied or divided by this factor upon each
210 update.
211 verbose : bool, optional
212 Print information about each update
214 """
215 def __init__(self, takestep, accept_rate=0.5, interval=50, factor=0.9,
216 verbose=True):
217 self.takestep = takestep
218 self.target_accept_rate = accept_rate
219 self.interval = interval
220 self.factor = factor
221 self.verbose = verbose
223 self.nstep = 0
224 self.nstep_tot = 0
225 self.naccept = 0
227 def __call__(self, x):
228 return self.take_step(x)
230 def _adjust_step_size(self):
231 old_stepsize = self.takestep.stepsize
232 accept_rate = float(self.naccept) / self.nstep
233 if accept_rate > self.target_accept_rate:
234 # We're accepting too many steps. This generally means we're
235 # trapped in a basin. Take bigger steps.
236 self.takestep.stepsize /= self.factor
237 else:
238 # We're not accepting enough steps. Take smaller steps.
239 self.takestep.stepsize *= self.factor
240 if self.verbose:
241 print("adaptive stepsize: acceptance rate {:f} target {:f} new "
242 "stepsize {:g} old stepsize {:g}".format(accept_rate,
243 self.target_accept_rate, self.takestep.stepsize,
244 old_stepsize))
246 def take_step(self, x):
247 self.nstep += 1
248 self.nstep_tot += 1
249 if self.nstep % self.interval == 0:
250 self._adjust_step_size()
251 return self.takestep(x)
253 def report(self, accept, **kwargs):
254 "called by basinhopping to report the result of the step"
255 if accept:
256 self.naccept += 1
259class RandomDisplacement:
260 """Add a random displacement of maximum size `stepsize` to each coordinate.
262 Calling this updates `x` in-place.
264 Parameters
265 ----------
266 stepsize : float, optional
267 Maximum stepsize in any dimension
268 random_gen : {None, int, `numpy.random.Generator`,
269 `numpy.random.RandomState`}, optional
271 If `seed` is None (or `np.random`), the `numpy.random.RandomState`
272 singleton is used.
273 If `seed` is an int, a new ``RandomState`` instance is used,
274 seeded with `seed`.
275 If `seed` is already a ``Generator`` or ``RandomState`` instance then
276 that instance is used.
278 """
280 def __init__(self, stepsize=0.5, random_gen=None):
281 self.stepsize = stepsize
282 self.random_gen = check_random_state(random_gen)
284 def __call__(self, x):
285 x += self.random_gen.uniform(-self.stepsize, self.stepsize,
286 np.shape(x))
287 return x
290class MinimizerWrapper:
291 """
292 wrap a minimizer function as a minimizer class
293 """
294 def __init__(self, minimizer, func=None, **kwargs):
295 self.minimizer = minimizer
296 self.func = func
297 self.kwargs = kwargs
299 def __call__(self, x0):
300 if self.func is None:
301 return self.minimizer(x0, **self.kwargs)
302 else:
303 return self.minimizer(self.func, x0, **self.kwargs)
306class Metropolis:
307 """Metropolis acceptance criterion.
309 Parameters
310 ----------
311 T : float
312 The "temperature" parameter for the accept or reject criterion.
313 random_gen : {None, int, `numpy.random.Generator`,
314 `numpy.random.RandomState`}, optional
316 If `seed` is None (or `np.random`), the `numpy.random.RandomState`
317 singleton is used.
318 If `seed` is an int, a new ``RandomState`` instance is used,
319 seeded with `seed`.
320 If `seed` is already a ``Generator`` or ``RandomState`` instance then
321 that instance is used.
322 Random number generator used for acceptance test.
324 """
326 def __init__(self, T, random_gen=None):
327 # Avoid ZeroDivisionError since "MBH can be regarded as a special case
328 # of the BH framework with the Metropolis criterion, where temperature
329 # T = 0." (Reject all steps that increase energy.)
330 self.beta = 1.0 / T if T != 0 else float('inf')
331 self.random_gen = check_random_state(random_gen)
333 def accept_reject(self, res_new, res_old):
334 """
335 Assuming the local search underlying res_new was successful:
336 If new energy is lower than old, it will always be accepted.
337 If new is higher than old, there is a chance it will be accepted,
338 less likely for larger differences.
339 """
340 with np.errstate(invalid='ignore'):
341 # The energy values being fed to Metropolis are 1-length arrays, and if
342 # they are equal, their difference is 0, which gets multiplied by beta,
343 # which is inf, and array([0]) * float('inf') causes
344 #
345 # RuntimeWarning: invalid value encountered in multiply
346 #
347 # Ignore this warning so when the algorithm is on a flat plane, it always
348 # accepts the step, to try to move off the plane.
349 prod = -(res_new.fun - res_old.fun) * self.beta
350 w = math.exp(min(0, prod))
352 rand = self.random_gen.uniform()
353 return w >= rand and (res_new.success or not res_old.success)
355 def __call__(self, *, res_new, res_old):
356 """
357 f_new and f_old are mandatory in kwargs
358 """
359 return bool(self.accept_reject(res_new, res_old))
362def basinhopping(func, x0, niter=100, T=1.0, stepsize=0.5,
363 minimizer_kwargs=None, take_step=None, accept_test=None,
364 callback=None, interval=50, disp=False, niter_success=None,
365 seed=None, *, target_accept_rate=0.5, stepwise_factor=0.9):
366 """Find the global minimum of a function using the basin-hopping algorithm.
368 Basin-hopping is a two-phase method that combines a global stepping
369 algorithm with local minimization at each step. Designed to mimic
370 the natural process of energy minimization of clusters of atoms, it works
371 well for similar problems with "funnel-like, but rugged" energy landscapes
372 [5]_.
374 As the step-taking, step acceptance, and minimization methods are all
375 customizable, this function can also be used to implement other two-phase
376 methods.
378 Parameters
379 ----------
380 func : callable ``f(x, *args)``
381 Function to be optimized. ``args`` can be passed as an optional item
382 in the dict `minimizer_kwargs`
383 x0 : array_like
384 Initial guess.
385 niter : integer, optional
386 The number of basin-hopping iterations. There will be a total of
387 ``niter + 1`` runs of the local minimizer.
388 T : float, optional
389 The "temperature" parameter for the acceptance or rejection criterion.
390 Higher "temperatures" mean that larger jumps in function value will be
391 accepted. For best results `T` should be comparable to the
392 separation (in function value) between local minima.
393 stepsize : float, optional
394 Maximum step size for use in the random displacement.
395 minimizer_kwargs : dict, optional
396 Extra keyword arguments to be passed to the local minimizer
397 `scipy.optimize.minimize` Some important options could be:
399 method : str
400 The minimization method (e.g. ``"L-BFGS-B"``)
401 args : tuple
402 Extra arguments passed to the objective function (`func`) and
403 its derivatives (Jacobian, Hessian).
405 take_step : callable ``take_step(x)``, optional
406 Replace the default step-taking routine with this routine. The default
407 step-taking routine is a random displacement of the coordinates, but
408 other step-taking algorithms may be better for some systems.
409 `take_step` can optionally have the attribute ``take_step.stepsize``.
410 If this attribute exists, then `basinhopping` will adjust
411 ``take_step.stepsize`` in order to try to optimize the global minimum
412 search.
413 accept_test : callable, ``accept_test(f_new=f_new, x_new=x_new, f_old=fold, x_old=x_old)``, optional
414 Define a test which will be used to judge whether to accept the
415 step. This will be used in addition to the Metropolis test based on
416 "temperature" `T`. The acceptable return values are True,
417 False, or ``"force accept"``. If any of the tests return False
418 then the step is rejected. If the latter, then this will override any
419 other tests in order to accept the step. This can be used, for example,
420 to forcefully escape from a local minimum that `basinhopping` is
421 trapped in.
422 callback : callable, ``callback(x, f, accept)``, optional
423 A callback function which will be called for all minima found. ``x``
424 and ``f`` are the coordinates and function value of the trial minimum,
425 and ``accept`` is whether that minimum was accepted. This can
426 be used, for example, to save the lowest N minima found. Also,
427 `callback` can be used to specify a user defined stop criterion by
428 optionally returning True to stop the `basinhopping` routine.
429 interval : integer, optional
430 interval for how often to update the `stepsize`
431 disp : bool, optional
432 Set to True to print status messages
433 niter_success : integer, optional
434 Stop the run if the global minimum candidate remains the same for this
435 number of iterations.
436 seed : {None, int, `numpy.random.Generator`, `numpy.random.RandomState`}, optional
438 If `seed` is None (or `np.random`), the `numpy.random.RandomState`
439 singleton is used.
440 If `seed` is an int, a new ``RandomState`` instance is used,
441 seeded with `seed`.
442 If `seed` is already a ``Generator`` or ``RandomState`` instance then
443 that instance is used.
444 Specify `seed` for repeatable minimizations. The random numbers
445 generated with this seed only affect the default Metropolis
446 `accept_test` and the default `take_step`. If you supply your own
447 `take_step` and `accept_test`, and these functions use random
448 number generation, then those functions are responsible for the state
449 of their random number generator.
450 target_accept_rate : float, optional
451 The target acceptance rate that is used to adjust the `stepsize`.
452 If the current acceptance rate is greater than the target,
453 then the `stepsize` is increased. Otherwise, it is decreased.
454 Range is (0, 1). Default is 0.5.
456 .. versionadded:: 1.8.0
458 stepwise_factor : float, optional
459 The `stepsize` is multiplied or divided by this stepwise factor upon
460 each update. Range is (0, 1). Default is 0.9.
462 .. versionadded:: 1.8.0
464 Returns
465 -------
466 res : OptimizeResult
467 The optimization result represented as a `OptimizeResult` object.
468 Important attributes are: ``x`` the solution array, ``fun`` the value
469 of the function at the solution, and ``message`` which describes the
470 cause of the termination. The ``OptimizeResult`` object returned by the
471 selected minimizer at the lowest minimum is also contained within this
472 object and can be accessed through the ``lowest_optimization_result``
473 attribute. See `OptimizeResult` for a description of other attributes.
475 See Also
476 --------
477 minimize :
478 The local minimization function called once for each basinhopping step.
479 `minimizer_kwargs` is passed to this routine.
481 Notes
482 -----
483 Basin-hopping is a stochastic algorithm which attempts to find the global
484 minimum of a smooth scalar function of one or more variables [1]_ [2]_ [3]_
485 [4]_. The algorithm in its current form was described by David Wales and
486 Jonathan Doye [2]_ http://www-wales.ch.cam.ac.uk/.
488 The algorithm is iterative with each cycle composed of the following
489 features
491 1) random perturbation of the coordinates
493 2) local minimization
495 3) accept or reject the new coordinates based on the minimized function
496 value
498 The acceptance test used here is the Metropolis criterion of standard Monte
499 Carlo algorithms, although there are many other possibilities [3]_.
501 This global minimization method has been shown to be extremely efficient
502 for a wide variety of problems in physics and chemistry. It is
503 particularly useful when the function has many minima separated by large
504 barriers. See the `Cambridge Cluster Database
505 <https://www-wales.ch.cam.ac.uk/CCD.html>`_ for databases of molecular
506 systems that have been optimized primarily using basin-hopping. This
507 database includes minimization problems exceeding 300 degrees of freedom.
509 See the free software program `GMIN <https://www-wales.ch.cam.ac.uk/GMIN>`_
510 for a Fortran implementation of basin-hopping. This implementation has many
511 variations of the procedure described above, including more
512 advanced step taking algorithms and alternate acceptance criterion.
514 For stochastic global optimization there is no way to determine if the true
515 global minimum has actually been found. Instead, as a consistency check,
516 the algorithm can be run from a number of different random starting points
517 to ensure the lowest minimum found in each example has converged to the
518 global minimum. For this reason, `basinhopping` will by default simply
519 run for the number of iterations `niter` and return the lowest minimum
520 found. It is left to the user to ensure that this is in fact the global
521 minimum.
523 Choosing `stepsize`: This is a crucial parameter in `basinhopping` and
524 depends on the problem being solved. The step is chosen uniformly in the
525 region from x0-stepsize to x0+stepsize, in each dimension. Ideally, it
526 should be comparable to the typical separation (in argument values) between
527 local minima of the function being optimized. `basinhopping` will, by
528 default, adjust `stepsize` to find an optimal value, but this may take
529 many iterations. You will get quicker results if you set a sensible
530 initial value for ``stepsize``.
532 Choosing `T`: The parameter `T` is the "temperature" used in the
533 Metropolis criterion. Basinhopping steps are always accepted if
534 ``func(xnew) < func(xold)``. Otherwise, they are accepted with
535 probability::
537 exp( -(func(xnew) - func(xold)) / T )
539 So, for best results, `T` should to be comparable to the typical
540 difference (in function values) between local minima. (The height of
541 "walls" between local minima is irrelevant.)
543 If `T` is 0, the algorithm becomes Monotonic Basin-Hopping, in which all
544 steps that increase energy are rejected.
546 .. versionadded:: 0.12.0
548 References
549 ----------
550 .. [1] Wales, David J. 2003, Energy Landscapes, Cambridge University Press,
551 Cambridge, UK.
552 .. [2] Wales, D J, and Doye J P K, Global Optimization by Basin-Hopping and
553 the Lowest Energy Structures of Lennard-Jones Clusters Containing up to
554 110 Atoms. Journal of Physical Chemistry A, 1997, 101, 5111.
555 .. [3] Li, Z. and Scheraga, H. A., Monte Carlo-minimization approach to the
556 multiple-minima problem in protein folding, Proc. Natl. Acad. Sci. USA,
557 1987, 84, 6611.
558 .. [4] Wales, D. J. and Scheraga, H. A., Global optimization of clusters,
559 crystals, and biomolecules, Science, 1999, 285, 1368.
560 .. [5] Olson, B., Hashmi, I., Molloy, K., and Shehu1, A., Basin Hopping as
561 a General and Versatile Optimization Framework for the Characterization
562 of Biological Macromolecules, Advances in Artificial Intelligence,
563 Volume 2012 (2012), Article ID 674832, :doi:`10.1155/2012/674832`
565 Examples
566 --------
567 The following example is a 1-D minimization problem, with many
568 local minima superimposed on a parabola.
570 >>> import numpy as np
571 >>> from scipy.optimize import basinhopping
572 >>> func = lambda x: np.cos(14.5 * x - 0.3) + (x + 0.2) * x
573 >>> x0 = [1.]
575 Basinhopping, internally, uses a local minimization algorithm. We will use
576 the parameter `minimizer_kwargs` to tell basinhopping which algorithm to
577 use and how to set up that minimizer. This parameter will be passed to
578 `scipy.optimize.minimize`.
580 >>> minimizer_kwargs = {"method": "BFGS"}
581 >>> ret = basinhopping(func, x0, minimizer_kwargs=minimizer_kwargs,
582 ... niter=200)
583 >>> print("global minimum: x = %.4f, f(x) = %.4f" % (ret.x, ret.fun))
584 global minimum: x = -0.1951, f(x) = -1.0009
586 Next consider a 2-D minimization problem. Also, this time, we
587 will use gradient information to significantly speed up the search.
589 >>> def func2d(x):
590 ... f = np.cos(14.5 * x[0] - 0.3) + (x[1] + 0.2) * x[1] + (x[0] +
591 ... 0.2) * x[0]
592 ... df = np.zeros(2)
593 ... df[0] = -14.5 * np.sin(14.5 * x[0] - 0.3) + 2. * x[0] + 0.2
594 ... df[1] = 2. * x[1] + 0.2
595 ... return f, df
597 We'll also use a different local minimization algorithm. Also, we must tell
598 the minimizer that our function returns both energy and gradient (Jacobian).
600 >>> minimizer_kwargs = {"method":"L-BFGS-B", "jac":True}
601 >>> x0 = [1.0, 1.0]
602 >>> ret = basinhopping(func2d, x0, minimizer_kwargs=minimizer_kwargs,
603 ... niter=200)
604 >>> print("global minimum: x = [%.4f, %.4f], f(x) = %.4f" % (ret.x[0],
605 ... ret.x[1],
606 ... ret.fun))
607 global minimum: x = [-0.1951, -0.1000], f(x) = -1.0109
609 Here is an example using a custom step-taking routine. Imagine you want
610 the first coordinate to take larger steps than the rest of the coordinates.
611 This can be implemented like so:
613 >>> class MyTakeStep:
614 ... def __init__(self, stepsize=0.5):
615 ... self.stepsize = stepsize
616 ... self.rng = np.random.default_rng()
617 ... def __call__(self, x):
618 ... s = self.stepsize
619 ... x[0] += self.rng.uniform(-2.*s, 2.*s)
620 ... x[1:] += self.rng.uniform(-s, s, x[1:].shape)
621 ... return x
623 Since ``MyTakeStep.stepsize`` exists basinhopping will adjust the magnitude
624 of `stepsize` to optimize the search. We'll use the same 2-D function as
625 before
627 >>> mytakestep = MyTakeStep()
628 >>> ret = basinhopping(func2d, x0, minimizer_kwargs=minimizer_kwargs,
629 ... niter=200, take_step=mytakestep)
630 >>> print("global minimum: x = [%.4f, %.4f], f(x) = %.4f" % (ret.x[0],
631 ... ret.x[1],
632 ... ret.fun))
633 global minimum: x = [-0.1951, -0.1000], f(x) = -1.0109
635 Now, let's do an example using a custom callback function which prints the
636 value of every minimum found
638 >>> def print_fun(x, f, accepted):
639 ... print("at minimum %.4f accepted %d" % (f, int(accepted)))
641 We'll run it for only 10 basinhopping steps this time.
643 >>> rng = np.random.default_rng()
644 >>> ret = basinhopping(func2d, x0, minimizer_kwargs=minimizer_kwargs,
645 ... niter=10, callback=print_fun, seed=rng)
646 at minimum 0.4159 accepted 1
647 at minimum -0.4317 accepted 1
648 at minimum -1.0109 accepted 1
649 at minimum -0.9073 accepted 1
650 at minimum -0.4317 accepted 0
651 at minimum -0.1021 accepted 1
652 at minimum -0.7425 accepted 1
653 at minimum -0.9073 accepted 1
654 at minimum -0.4317 accepted 0
655 at minimum -0.7425 accepted 1
656 at minimum -0.9073 accepted 1
658 The minimum at -1.0109 is actually the global minimum, found already on the
659 8th iteration.
661 """
662 if target_accept_rate <= 0. or target_accept_rate >= 1.:
663 raise ValueError('target_accept_rate has to be in range (0, 1)')
664 if stepwise_factor <= 0. or stepwise_factor >= 1.:
665 raise ValueError('stepwise_factor has to be in range (0, 1)')
667 x0 = np.array(x0)
669 # set up the np.random generator
670 rng = check_random_state(seed)
672 # set up minimizer
673 if minimizer_kwargs is None:
674 minimizer_kwargs = dict()
675 wrapped_minimizer = MinimizerWrapper(scipy.optimize.minimize, func,
676 **minimizer_kwargs)
678 # set up step-taking algorithm
679 if take_step is not None:
680 if not callable(take_step):
681 raise TypeError("take_step must be callable")
682 # if take_step.stepsize exists then use AdaptiveStepsize to control
683 # take_step.stepsize
684 if hasattr(take_step, "stepsize"):
685 take_step_wrapped = AdaptiveStepsize(
686 take_step, interval=interval,
687 accept_rate=target_accept_rate,
688 factor=stepwise_factor,
689 verbose=disp)
690 else:
691 take_step_wrapped = take_step
692 else:
693 # use default
694 displace = RandomDisplacement(stepsize=stepsize, random_gen=rng)
695 take_step_wrapped = AdaptiveStepsize(displace, interval=interval,
696 accept_rate=target_accept_rate,
697 factor=stepwise_factor,
698 verbose=disp)
700 # set up accept tests
701 accept_tests = []
702 if accept_test is not None:
703 if not callable(accept_test):
704 raise TypeError("accept_test must be callable")
705 accept_tests = [accept_test]
707 # use default
708 metropolis = Metropolis(T, random_gen=rng)
709 accept_tests.append(metropolis)
711 if niter_success is None:
712 niter_success = niter + 2
714 bh = BasinHoppingRunner(x0, wrapped_minimizer, take_step_wrapped,
715 accept_tests, disp=disp)
717 # The wrapped minimizer is called once during construction of
718 # BasinHoppingRunner, so run the callback
719 if callable(callback):
720 callback(bh.storage.minres.x, bh.storage.minres.fun, True)
722 # start main iteration loop
723 count, i = 0, 0
724 message = ["requested number of basinhopping iterations completed"
725 " successfully"]
726 for i in range(niter):
727 new_global_min = bh.one_cycle()
729 if callable(callback):
730 # should we pass a copy of x?
731 val = callback(bh.xtrial, bh.energy_trial, bh.accept)
732 if val is not None:
733 if val:
734 message = ["callback function requested stop early by"
735 "returning True"]
736 break
738 count += 1
739 if new_global_min:
740 count = 0
741 elif count > niter_success:
742 message = ["success condition satisfied"]
743 break
745 # prepare return object
746 res = bh.res
747 res.lowest_optimization_result = bh.storage.get_lowest()
748 res.x = np.copy(res.lowest_optimization_result.x)
749 res.fun = res.lowest_optimization_result.fun
750 res.message = message
751 res.nit = i + 1
752 res.success = res.lowest_optimization_result.success
753 return res