[[407724]]

 Python中文社區(qū)(ID:python-china)

盆地跳躍是一種全局優(yōu)化算法。它是為解決化學(xué)物理學(xué)中的問題而開發(fā)的，盡管它是一種適用于具有多個(gè)最優(yōu)條件的非線性目標(biāo)函數(shù)的有效算法。

在本教程中，您將發(fā)現(xiàn)盆地跳躍全局優(yōu)化算法。完成本教程后，您將知道：

•  盆地跳躍優(yōu)化是一種全局優(yōu)化，它使用隨機(jī)擾動(dòng)來跳躍盆地，并使用局部搜索算法來優(yōu)化每個(gè)盆地。
•  如何在python中使用盆地跳躍優(yōu)化算法API。
•  使用流域跳躍來解決具有多個(gè)最優(yōu)解的全局優(yōu)化問題的示例。

教程概述

本教程分為三個(gè)部分：他們是：

•  盆地跳躍優(yōu)化
•  盆地跳躍API
•  盆地跳躍的例子 局部最優(yōu)的多峰優(yōu)化 具有多個(gè)全局最優(yōu)的多峰優(yōu)化

盆地跳躍優(yōu)化

Basin Hopping是為化學(xué)物理領(lǐng)域開發(fā)的一種全局優(yōu)化算法。局部優(yōu)化是指旨在為單變量目標(biāo)函數(shù)定位最優(yōu)值或在認(rèn)為存在最優(yōu)值的區(qū)域中運(yùn)行的優(yōu)化算法。而全局優(yōu)化算法旨在將單個(gè)全局最優(yōu)定位在潛在的多個(gè)局部（非全局）最優(yōu)之中。David Wales和Jonathan Doye在1997年的論文中描述了“盆地跳躍”，題目是“通過盆地跳躍進(jìn)行的全局優(yōu)化和包含110個(gè)原子的Lennard-Jones團(tuán)簇的最低能級結(jié)構(gòu)”。

該算法包括循環(huán)兩個(gè)步驟，一個(gè)是好的候選解的擾動(dòng)，另一個(gè)是將本地搜索應(yīng)用于被擾動(dòng)的解。

擾動(dòng)允許搜索算法跳到搜索空間的新區(qū)域，并可能找到導(dǎo)致不同最優(yōu)值的新盆地，例如技術(shù)名稱中的“跳槽”。局部搜索使算法可以遍歷新盆地達(dá)到最佳狀態(tài)。新的最優(yōu)值可以作為新的隨機(jī)擾動(dòng)的基礎(chǔ)，否則將被丟棄。保留新解決方案的決策是由具有“溫度”變量的隨機(jī)決策函數(shù)控制的，這與模擬退火非常相似。溫度根據(jù)算法的迭代次數(shù)進(jìn)行調(diào)整。這樣可以在高溫時(shí)在運(yùn)行的早期就接受任意解決方案，而更嚴(yán)格的策略是在低溫時(shí)在搜索的后期僅接受質(zhì)量更好的解決方案。這樣，該算法非常類似于具有不同（擾動(dòng)）起始點(diǎn)的迭代局部搜索。該算法運(yùn)行指定的迭代次數(shù)或函數(shù)求值，并且可以多次運(yùn)行以提高對找到全局最優(yōu)值或找到相對好的解決方案的信心。

現(xiàn)在，我們已經(jīng)從較高的層次熟悉了基本的跳變算法，下面讓我們看一下Python中用于盆地跳變的API。

盆地跳躍API

在Python中，可以通過Basinhopping（）SciPy函數(shù)來進(jìn)行盆地跳躍。   

# perform the basin hopping search  
result = basinhopping(objective, pt)  

另一個(gè)重要的超參數(shù)是通過“ niter”參數(shù)運(yùn)行搜索集的迭代次數(shù)，默認(rèn)為100。可以將其設(shè)置為數(shù)千次迭代或更多次迭代。 

# perform the basin hopping search  
result = basinhopping(objective, pt, niter=10000) 

可以通過“步長”控制應(yīng)用于候選解的擾動(dòng)量，該“步長”定義了在問題域的邊界范圍內(nèi)施加的最大變化量。默認(rèn)情況下，將其設(shè)置為0.5，但應(yīng)在域中將其設(shè)置為合理的值，以允許搜索找到新的盆地。例如，如果搜索空間的合理范圍是-100到100，則步長為5.0或10.0個(gè)單位可能是合適的（例如，域的2.5％或5％）。 

# perform the basin hopping search  
result = basinhopping(objective, pt, stepsize=10.0) 

默認(rèn)情況下，使用的本地搜索算法是“ L-BFGS-B”算法?？梢酝ㄟ^將“ minimizer_kwargs”參數(shù)設(shè)置為關(guān)鍵字為“ method”且值作為要使用的本地搜索算法的名稱（例如“ nelder-mead”）的目錄來更改此設(shè)置?？梢允褂肧ciPy庫提供的任何本地搜索算法。 

# perform the basin hopping search  
result = basinhopping(objective, pt, minimizer_kwargs={'method':'nelder-mead'})  

搜索的結(jié)果是一個(gè)OptimizeResult對象，可以在其中像字典一樣訪問屬性?？梢酝ㄟ^“成功”或“消息”鍵來訪問搜索的成功與否。

可以通過“ nfev”訪問功能評估的總數(shù)，并且可以通過“ x”鍵訪問為搜索找到的最佳輸入。

現(xiàn)在，我們已經(jīng)熟悉了Python中的盆地跳躍API，下面我們來看一些可行的示例。

盆地跳躍的例子

在本節(jié)中，我們將研究在多模態(tài)目標(biāo)函數(shù)上使用盆地跳躍算法的一些示例。多峰目標(biāo)函數(shù)是具有多個(gè)最優(yōu)值的函數(shù)，例如全局最優(yōu)值和許多局部最優(yōu)值，或者具有相同目標(biāo)函數(shù)輸出的多個(gè)全局最優(yōu)值。我們將在這兩個(gè)函數(shù)上查看流域跳躍的示例。

局部最優(yōu)的多峰優(yōu)化

Ackley函數(shù)是目標(biāo)函數(shù)的一個(gè)示例，該目標(biāo)函數(shù)具有單個(gè)全局最優(yōu)值和多個(gè)局部最優(yōu)值，可能會(huì)在其中陷入局部搜索。因此，需要全局優(yōu)化技術(shù)。這是一個(gè)二維目標(biāo)函數(shù)，其全局最佳值為[0,0]，其值為0.0。下面的示例實(shí)現(xiàn)了Ackley，并創(chuàng)建了一個(gè)三維表面圖，顯示了全局最優(yōu)值和多個(gè)局部最優(yōu)值。 

# 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  
  # objective function  
  def objective(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 range for input  
  r_min, r_max = -5.0, 5.0  
  # sample input range 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  
  results = objective(x, y)  
  # create a surface plot with the jet color scheme  
  figure = pyplot.figure()  
  axis = figure.gca(projection='3d')  
  axis.plot_surface(x, y, results, cmap='jet')  
  # show the plot  
  pyplot.show() 

運(yùn)行示例將創(chuàng)建Ackley函數(shù)的表面圖，以顯示大量的局部最優(yōu)值。

我們可以將盆地跳躍算法應(yīng)用于Ackley目標(biāo)函數(shù)。

在這種情況下，我們將使用從-5到5之間的輸入域繪制的隨機(jī)點(diǎn)開始搜索。 

# define the starting point as a random sample from the domain  
pt = r_min + rand(2) * (r_max - r_min) 

我們將使用0.5的步長，200次迭代和默認(rèn)的本地搜索算法。經(jīng)過一番嘗試和錯(cuò)誤后，才選擇此配置。 

# perform the basin hopping search  
result = basinhopping(objective, pt, stepsize=0.5, niter=200) 

搜索完成后，它將報(bào)告搜索狀態(tài)，執(zhí)行的迭代次數(shù)以及通過評估發(fā)現(xiàn)的最佳結(jié)果。 

# summarize the result  
 print('Status : %s' % result['message'])  
 print('Total Evaluations: %d' % result['nfev'])  
 # evaluate solution  
 solution = result['x']  
 evaluation = objective(solution)  
 print('Solution: f(%s) = %.5f' % (solution, evaluation)) 

結(jié)合在一起，下面列出了將盆地跳躍應(yīng)用于Ackley目標(biāo)函數(shù)的完整示例。   

# basin hopping global optimization for the ackley multimodal objective 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  
   # objective function  
   def objective(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 range for input  
   r_min, r_max = -5.0, 5.0  
   # define the starting point as a random sample from the domain  
   pt = r_min + rand(2) * (r_max - r_min)  
   # perform the basin hopping search  
   result = basinhopping(objective, pt, stepsize=0.5, niter=200) 
   # summarize the result  
   print('Status : %s' % result['message'])  
   print('Total Evaluations: %d' % result['nfev'])  
   # evaluate solution  
   solution = result['x']  
   evaluation = objective(solution)  
   print('Solution: f(%s) = %.5f' % (solution, evaluation)) 

運(yùn)行示例將執(zhí)行優(yōu)化，然后報(bào)告結(jié)果。

注意：由于算法或評估程序的隨機(jī)性，或者數(shù)值精度的不同，您的結(jié)果可能會(huì)有所不同?？紤]運(yùn)行該示例幾次并比較平均結(jié)果。

在這種情況下，我們可以看到該算法將最優(yōu)值定位為非常接近零的輸入，并且目標(biāo)函數(shù)的評估值實(shí)際上為零。我們可以看到，該算法的200次迭代產(chǎn)生了86,020個(gè)函數(shù)求值。 

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

具有多個(gè)全局最優(yōu)的多峰優(yōu)化

Himmelblau函數(shù)是具有多個(gè)全局最優(yōu)值的目標(biāo)函數(shù)的示例。

具體來說，它具有四個(gè)最優(yōu)值，并且每個(gè)都有相同的目標(biāo)函數(shù)評估。這是一個(gè)二維目標(biāo)函數(shù)，其全局最佳值分別為[3.0，2.0]，[-2.805118、3.113112]，[-3.779310，-3.283186]，[3.584428，-1.848126]。這意味著全局優(yōu)化算法的每次運(yùn)行都可能找到不同的全局最優(yōu)值。下面的示例實(shí)現(xiàn)了Himmelblau并創(chuàng)建了一個(gè)三維表面圖，以直觀地說明目標(biāo)函數(shù)。 

# himmelblau multimodal test function  
from numpy import arange  
from numpy import meshgrid  
from matplotlib import pyplot  
from mpl_toolkits.mplot3d import Axes3D  
# objective function  
def objective(x, y):  
    return (x**2 + y - 11)**2 + (x + y**2 -7)**2  
# define range for input  
r_min, r_max = -5.0, 5.0  
# sample input range 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  
results = objective(x, y)  
# create a surface plot with the jet color scheme  
figure = pyplot.figure()  
axis = figure.gca(projection='3d')  
axis.plot_surface(x, y, results, cmap='jet')  
# show the plot  
pyplot.show() 

運(yùn)行示例將創(chuàng)建Himmelblau函數(shù)的表面圖，該圖將四個(gè)全局最優(yōu)值顯示為深藍(lán)色盆地。

我們可以將盆地跳躍算法應(yīng)用于Himmelblau目標(biāo)函數(shù)。

與前面的示例一樣，我們將使用從-5到5之間的輸入域繪制的隨機(jī)點(diǎn)開始搜索。

我們將使用0.5的步長，200次迭代和默認(rèn)的本地搜索算法。搜索結(jié)束時(shí)，我們將報(bào)告最佳位置的最佳輸入。 

# basin hopping global optimization for the himmelblau multimodal objective function  
  from scipy.optimize import basinhopping  
  from numpy.random import rand  
  # objective function  
  def objective(v):  
      x, y = v  
      return (x**2 + y - 11)**2 + (x + y**2 -7)**2  
  # define range for input  
  r_min, r_max = -5.0, 5.0  
  # define the starting point as a random sample from the domain  
  pt = r_min + rand(2) * (r_max - r_min)  
  # perform the basin hopping search  
  result = basinhopping(objective, pt, stepsize=0.5, niter=200)  
  # summarize the result  
  print('Status : %s' % result['message'])  
  print('Total Evaluations: %d' % result['nfev'])  
  # evaluate solution  
  solution = result['x']  
  evaluation = objective(solution)  
  print('Solution: f(%s) = %.5f' % (solution, evaluation)) 

運(yùn)行示例將執(zhí)行優(yōu)化，然后報(bào)告結(jié)果。

在這種情況下，我們可以看到該算法在[3.0，2.0]處確定了一個(gè)最佳值。

我們可以看到，該算法的200次迭代產(chǎn)生了7,660個(gè)函數(shù)評估。 

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

如果我們再次運(yùn)行搜索，則可能期望找到其他全局最優(yōu)值。

例如，下面，我們可以看到一個(gè)最佳值位于[-2.805118，3.131312]處，與之前的運(yùn)行不同。 

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