用python模拟退火法求带噪函数的全局最小值

Question

作为模拟退火的练习，我试图从百位百元挑战题第4题中找到函数的全局最小值

作为我理解和编写代码方法的基础，我参考了在线免费提供的《全局优化算法》第3版

因此，我最初提出了以下代码：

噪音函数：

def noisy_func(x, y):
    return (math.exp(math.sin(50*x)) +
            math.sin(60*math.exp(y)) +
            math.sin(70*math.sin(x)) +
            math.sin(math.sin(80*y)) -
            math.sin(10*(x + y)) +
            0.25*(math.pow(x, 2) +
            math.pow(y, 2)))

用于改变值的函数：

def mutate(X_Value, Y_Value):

    mutationResult_X = X_Value + randomNumForInput()
    mutationResult_Y = Y_Value + randomNumForInput()

    while mutationResult_X > 4 or mutationResult_X < -4:
        mutationResult_X = X_Value + randomNumForInput()

    while mutationResult_Y > 4 or mutationResult_Y < -4:
        mutationResult_Y = Y_Value + randomNumForInput()

    mutationResults = [mutationResult_X, mutationResult_Y]
    return mutationResults

randomNumForInput只返回一个介于4和-4之间的随机数。（搜索的间隔限制）因此它相当于random.uniform(-4, 4)

这是程序的中心功能

def simulated_annealing(f):
    """Peforms simulated annealing to find a solution"""
    #Start by initializing the current state with the initial state
    #acquired by a random generation of a number and then using it
    #in the noisy func, also set solution(best_state) as current_state
    #for a start
    pCurSelect  = [randomNumForInput(),randomNumForInput()]
    current_state = f(pCurSelect[0],pCurSelect[1])
    best_state = current_state
    #Begin time monitoring, this will represent the
    #Number of steps over time
    TimeStamp = 1

    #Init current temp via the func, using such values as to get the initial temp
    initial_temp = 100
    final_temp = .1
    alpha = 0.001
    num_of_steps = 1000000
    #calculates by how much the temperature should be tweaked
    #each iteration
    #suppose the number of steps is linear, we'll send in 100
    temp_Delta = calcTempDelta(initial_temp, final_temp, num_of_steps)
    #set current_temp via initial temp
    current_temp = getTemperature(initial_temp, temp_Delta)

    #max_iterations = 100
    #initial_temp = get_Temperature_Poly(TimeStamp)

    #current_temp > final_temp
    while current_temp > final_temp:
        #get a mutated value from the current value
        #hence being a 'neighbour' value
        #with it, acquire the neighbouring state
        #to the current state
        neighbour_values = mutate(pCurSelect[0], pCurSelect[1])
        neighbour_state = f(neighbour_values[0], neighbour_values[1])

        #calculate the difference between the newly mutated
        #neighbour state and the current state
        delta_E_Of_States = neighbour_state - current_state

        # Check if neighbor_state is the best state so far

        # if the new solution is better (lower), accept it
        if delta_E_Of_States <= 0:
            pCurSelect = neighbour_values
            current_state = neighbour_state
            if current_state < best_state:
                best_state = current_state

        # if the new solution is not better, accept it with a probability of e^(-cost/temp)
        else:
            if random.uniform(0, 1) < math.exp(-(delta_E_Of_States) / current_temp):
                pCurSelect = neighbour_values
                current_state = neighbour_state
        # Here, we'd decrement the temperature or increase the timestamp, normally
        """current_temp -= alpha"""

        #print("Run number: " + str(TimeStamp) + " current_state = " + str(current_state) )
        #increment TimeStamp
        TimeStamp = TimeStamp + 1

        # calc temp for next iteration
        current_temp = getTemperature(current_temp, temp_Delta)

    #print("Iteration Count: " + str(TimeStamp))
    return best_state

alpha不用于此实现，但使用以下函数线性调节温度：

def calcTempDelta(T_Initial, T_Final, N):
    return((T_Initial-T_Final)/N)

def getTemperature(T_old, T_new):
    return (T_old - T_new)

这就是我如何实现本书第245页中描述的解决方案。然而，这个实现并没有向我返回噪声函数的全局最小值，而是它的一个近似局部最小值

我以这种方式实施解决方案的原因有两个：

1. 它是作为线性温度调节的工作示例提供给我的，因此是一个工作模板

2. 尽管我试图理解书中248-249页所述的温度调节的其他形式，但我并不完全清楚变量“Ts”是如何计算的，即使在尝试查看了书中引用的一些来源后，对我来说仍然是个谜。因此，我想，我宁愿先尝试让这个“简单”的解决方案正确工作，然后再尝试其他温度淬火方法（对数、指数等）

从那以后，我尝试了许多方法，通过各种不同的代码迭代来获取带噪func的全局最小值，这太多了，无法一次发布到这里。我尝试了不同的代码重写：

1. 减少每次迭代中的随机滚动次数，以便每次都在较小的范围内搜索，这会导致更一致但仍然不正确的结果

2. 通过不同的增量进行变异，比如说，在-1和1之间，等等。同样的效果

3. 重写mutate as，以便通过一些步长检查当前点的相邻点，并通过从当前点的x/y值添加/减少所述步长来检查相邻点，检查新生成点和当前点之间的差异（基本上是E的增量），并返回适当的值，其中一个值与当前函数的距离最小，因此是其最接近的邻居

4. 减少搜索发生的时间间隔限制

正是在这些解决方案中，涉及步长/减少限制/通过象限检查邻居，我使用了由一些常数alpha乘以时间戳组成的运动

我尝试的这些解决方案和其他解决方案都不起作用，要么产生更不准确的结果（尽管在某些情况下更一致的结果），要么在一种情况下根本不起作用

因此，我肯定遗漏了一些东西，无论是与温度调节有关，还是与我在算法中进行下一步（变异）的精确方式（公式）有关

我知道有很多东西需要接受和研究，但如果您能给我提供任何建设性的批评/帮助/建议，我将不胜感激。 如果展示其他解决方案尝试的代码有任何帮助，我会在有人要求时发布它们

Answer 1

跟踪你正在做的事情是很重要的。 我在frigidum上提出了一些重要提示

{}冷却通常运行良好，它确保您不会快速通过有趣的最佳点，在那里大约0.1个建议被接受

确保你的建议不是太粗糙，我举了一个例子，我只改变x或y，但从来没有两者都改变。这个想法是，退火将采取最好的，或采取参观，并让该计划决定

我在algo中使用了frigidum软件包，但它与您的代码几乎相同。另外请注意，我有两个建议，一个大的改变和一个小的改变，组合通常工作得很好

最后，我注意到它跳了很多次。一个小的变化是在你进入最后5%的冷却时间之前，选择目前为止最好的

我使用/安装frigidum

!pip install frigidum

对numpy阵列的使用做了一点小小的改变

import math

def noisy_func(X):
    x, y = X
    return (math.exp(math.sin(50*x)) +
            math.sin(60*math.exp(y)) +
            math.sin(70*math.sin(x)) +
            math.sin(math.sin(80*y)) -
            math.sin(10*(x + y)) +
            0.25*(math.pow(x, 2) +
            math.pow(y, 2)))


import frigidum
import numpy as np
import random

def random_start():
    return np.random.random( 2 ) * 4

def random_small_step(x):
    if np.random.random() < .5:
        return np.clip( x + np.array( [0, 0.02 * (random.random() - .5)] ), -4,4)
    else:
        return np.clip( x + np.array( [0.02 * (random.random() - .5), 0] ), -4,4)


def random_big_step(x):
    if np.random.random() < .5:
        return np.clip( x + np.array( [0, 0.5 * (random.random() - .5)] ), -4,4)
    else:
        return np.clip( x + np.array( [0.5 * (random.random() - .5), 0] ), -4,4)

local_opt = frigidum.sa(random_start=random_start, 
                        neighbours=[random_small_step, random_big_step], 
                        objective_function=noisy_func, 
                        T_start=10**2, 
                        T_stop=0.00001, 
                        repeats=10**4, 
                        copy_state=frigidum.annealing.copy)

---

上述研究的成果如下：

 -
Neighbour Statistics: 
(proportion of proposals which got accepted *and* changed the objective function)
   random_small_step                : 0.451045
   random_big_step                  : 0.268002
 -
(Local) Minimum Objective Value Found: 
   -3.30669277

在上面的代码中，有时我会在-3以下，但我也注意到有时它会在-2附近找到一些东西，而不是在最后阶段

所以一个小小的调整就是重新退火退火的最后一个阶段，这是迄今为止发现的最好的阶段

希望有帮助，如果有任何问题，请告诉我