Python跳盆算法，来自物质结构的优化算法

简介

basinhopping可用于搜索全局最优解，采用的是盆地跳跃(即BH)算法。BH算法是1997年，Jonathan Doye博士和他的导师David Wales为了优化原子团簇结构而提出的，其核心概念当然是Basin，也就是盆地，或者坑。

所谓盆地，就是一群局部极小值组成的集合，所以算法的第一步，就是得到这个盆地。具体表现是随机生成一个初始位置$\vec{x}$，并计算这个位置的适应度$f=f(\vec{x})$，然后经过一些随机扰动，得到$\vec{x}$附近的一些值${\vec{x}}_i$，并计算这些值的适应度$f_i=f({\vec{x}}_i)$，并得到其极小值。在$f_i$极小值所在位置的$x_i$便称为候选解。

如果此时的$f_i$小于$f$，也就意味着$f_i$无可争议地称为候选解；否则的话，为了避免陷入局部最优，也有一定的几率成为为候选解。

这样反复迭代之后，就得到了由一群极小值组成的盆地，在这块盆地里，除了初始化时的值之外，每一个极小值，都是从另一个极小值或准极小值跳跃而来，故为盆地跳跃算法。

scipy封装

在scipy.optimize中，封装了这种全局寻优算法，定义为

basinhopping(func, x0, niter=100, T=1.0, stepsize=0.5, minimizer_kwargs=None, take_step=None, accept_test=None, callback=None, interval=50, disp=False, niter_success=None, seed=None, *, target_accept_rate=0.5, stepwise_factor=0.9)
1

其中，func为待拟合函数，x0为初始值，此二者为必填参数，剩下的为可选参数

• niter：迭代次数
• T：表示温度，这就表现出了这个算法的物理背景，即温度越高，原子振动得越厉害，也就是说随机搜索步长越长
• stepsize：为随机位移的最大步长
• interval：表示更新stepsize的周期
• target_accept_rate, stepwise_factor：用于调整stepsize
• disp：设为True时，打印状态信息
• seed：用于设置随机数种子，以保证算法的可复现性
• take_step：自定义的迭代函数
• accept_test：自定义的判据函数
• callback：当找到最优值后的回调函数

minimizer_kwargs为最小化方法的字典，一般用于调用优化方法，例如{'method':'BFGS'}，表示调用BFGS作为局部寻优方案。

测试

接下来找一个函数对basinhopping进行测试，下面这个例程是官方文档中的

import numpy as np
from scipy.optimize import basinhopping
func = lambda x: np.cos(14.5 * x - 0.3) + (x + 0.2) * x
x0=[1.]
minimizer_kwargs = {"method": "BFGS"}
ret = basinhopping(func, x0, niter=200,
    minimizer_kwargs=minimizer_kwargs)
print(f"全局最小值 x = {ret.x[0]:.4f}, f(x) = {ret.fun:.4f}")
# 输出为 全局最小值 x = -0.1951, f(x) = -1.0009
1
2
3
4
5
6
7
8
9

上面这个只是对单值函数进行了测试，属于牛刀小试，接下来搞一个变态一点的多元函数

def test(xs):
    _sum = 0.0
    for i in range(len(xs)):
        _sum = _sum + np.cos((xs[i]*i)/5)*(i+1)
    return _sum

xs = [0,0,0,0,0]
mKwargs = {"method": "BFGS"}
ret = basinhopping(test, xs, niter=200,  
    minimizer_kwargs=mKwargs)
msg = f"全局最小值" + ", ".join([f"{x:.4f}" for x in ret.x])
msg += f"\nf(x)={ret.fun:.4f}"
print(msg)
'''
print(msg)
全局最小值-1.5466, -15.7080, -7.8540, 5.2360, -11.7810
f(x)=-13.0000
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

可以说效果相当霸道了。