使用 Python 进行双重退火优化

女爷i 2022-10-17 00:50 101阅读 0赞

【翻译自 ： [Dual Annealing Optimization With Python][]】

【说明：*Jason Brownlee* PhD大神的文章个人很喜欢，所以闲暇时间里会做一点翻译和学习实践的工作，这里是相应工作的实践记录，希望能帮到有需要的人！】

Dual Annealing 是一种随机全局优化算法。它是广义模拟退火算法的一种实现，是模拟退火算法的扩展。 此外，它还与在模拟退火过程结束时自动执行的局部搜索算法配对。这种有效的全局和局部搜索程序的组合为挑战非线性优化问题提供了一种强大的算法。

在本教程中，您将发现双重退火全局优化算法。完成本教程后，您将了解：

双退火优化是一种全局优化，它是模拟退火的修改版本，它也利用了局部搜索算法。
    如何在python中使用双重退火优化算法API。
    使用双重退火解决具有多重最优解的全局优化问题的示例。

# 教程概述 #

本教程分为三个部分；他们是：

什么是双重退火
    双退火API
    双退火示例

## 什么是双重退火 ##

Dual Annealing 是一种全局优化算法。因此，它是为具有非线性响应面的目标函数而设计的。它是一种随机优化算法，这意味着它在搜索过程中利用随机性，每次搜索运行可能会找到不同的解决方案。

Dual Annealing 基于模拟退火优化算法。

模拟退火是一种随机爬山，其中以随机方式修改候选解，并且接受修改后的解以概率性地替换当前候选解。这意味着更糟糕的解决方案可能会取代当前的候选解决方案。这种替换的概率在搜索开始时很高，并且随着每次迭代而降低，由“温度”超参数控制。

双重退火是经典模拟退火 (CSA) 算法的一种实现。它基于 1997 年论文“广义模拟退火算法及其在 Thomson 模型中的应用”中描述的广义模拟退火 (GSA) 算法。它结合了“快速模拟退火”（FSA）中的退火程序（温度在算法迭代中降低的速率）和为作者指定的替代统计程序“ Tsallis statistics”的概率接受度。实验结果发现，这种广义模拟退火算法的性能似乎比与之比较的算法的经典或快速版本更好。

除了模拟退火的这些修改外，局部搜索算法可以应用于模拟退火搜索找到的解决方案。这是可取的，因为全局搜索算法通常擅长为最佳解决方案定位盆地（搜索空间中的区域），但往往在寻找盆地中的最佳解决方案方面表现不佳。 而局部搜索算法擅长寻找盆地的最优值。

将局部搜索与模拟退火程序配对可确保搜索充分利用所定位的候选解决方案。现在我们从高层次上熟悉了双重退火算法，让我们看一下 Python 中双重退火的 API。

## 双退火API ##

通过Python中的dual\_annealing（）SciPy函数可以使用Dual Annealing全局优化算法。该函数将目标函数的名称和每个输入变量的边界作为搜索的最小参数。

# perform the dual annealing search
    result = dual_annealing(objective, bounds)

有许多用于搜索的附加超参数具有默认值，但您可以对其进行配置以自定义搜索。“maxiter”参数指定算法的总迭代次数（不是函数评估的总数），默认为 1,000 次迭代。如果需要限制函数评估的总数，可以指定“maxfun”，默认值为 1000 万。搜索的初始温度由“initial\_temp”参数指定，默认为 5,230。一旦温度达到等于或小于（initial\_temp \* restart\_temp\_ratio）的值，将重新开始退火过程。该比率默认为非常小的数字 2e-05（即 0.00002），因此重新退火的默认触发器是 (5230 \* 0.00002) 或 0.1046 的温度。该算法还提供对特定于它所基于的广义模拟退火的超参数的控制。这包括在搜索过程中可以通过“访问”参数进行多远跳转，默认为 2.62（小于 3 的值是首选），以及控制接受新解决方案的可能性的“接受”参数，默认为 - 5.使用默认超参数进行局部搜索调用 minimum() 函数。可以通过向“local\_search\_options”参数提供超参数名称和值的字典来配置本地搜索。

可以通过将“no\_local\_search”参数设置为 True 来禁用搜索的本地搜索组件。搜索的结果是一个 OptimizeResult 对象，其中的属性可以像字典一样访问。可以通过“成功”或“消息”键访问搜索是否成功。可以通过“nfev”访问函数评估的总数，并且可以通过“x”键访问为搜索找到的最佳输入。

现在我们熟悉了 Python 中的双重退火 API，让我们看一些工作示例。

## 双退火示例 ##

在本节中，我们将看一个在多模态目标函数上使用双重退火算法的示例。Ackley 函数是多模态目标函数的一个示例，它具有单个全局最优解和多个局部最优解，其中局部搜索可能会卡住。

因此，需要全局优化技术。它是一个二维目标函数，在 \[0,0\] 处具有全局最优值，其计算结果为 0.0。下面的示例实现了 Ackley 并创建了一个显示全局最优和多个局部最优的三维曲面图。

# 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()

运行该示例会创建显示大量局部最优值的 Ackley 函数的曲面图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvZ2V0aGVyX0Na_size_16_color_FFFFFF_t_70][]

我们可以将双重退火算法应用于 Ackley 目标函数。首先，我们可以将搜索空间的边界定义为函数在每个维度上的限制。

# define the bounds on the search
    bounds = [[r_min, r_max], [r_min, r_max]]

然后我们可以通过指定目标函数的名称和搜索范围来应用搜索。在这种情况下，我们将使用默认的超参数。

# perform the simulated annealing search
    result = dual_annealing(objective, bounds)

搜索完成后，它将报告搜索状态和执行的迭代次数，以及通过评估找到的最佳结果。

# 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))

结合在一起，下面列出了将双重退火应用于Ackley目标函数的完整示例。

# dual annealing global optimization for the ackley multimodal objective function
    from scipy.optimize import dual_annealing
    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 bounds on the search
    bounds = [[r_min, r_max], [r_min, r_max]]
    # perform the dual annealing search
    result = dual_annealing(objective, bounds)
    # 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))

运行示例执行优化，然后报告结果。

注意：由于算法或评估程序的随机性或数值精度的差异，您的结果可能会有所不同。 考虑多次运行该示例并比较平均结果。

在这种情况下，我们可以看到算法找到了输入非常接近于零且目标函数评估实际上为零的最优值。

我们可以看到总共执行了 4,136 次函数评估。

Status : ['Maximum number of iteration reached']
    Total Evaluations: 4136
    Solution: f([-2.26474440e-09 -8.28465933e-09]) = 0.00000

[Dual Annealing Optimization With Python]: https://machinelearningmastery.com/dual-annealing-optimization-with-python/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvZ2V0aGVyX0Na_size_16_color_FFFFFF_t_70]: /images/20221014/2de6e6d8cd7b4d45a87848939de34ddc.png