具有多个变量的 python 中的模拟退火

Question

我发现这篇旧的 Whosebug 文章基本上正是我想要的。

Algorithm to optimize multiple variables more efficiently than trial-and-error

不幸的是，我的高级数学有点欠缺，我对 ElKamina 的回答有一些疑问，如果有人可以看一看并提出一些这些基本数学概念的建议，希望它能帮助我。

我参考的答案如下：

def simAnneal( w, seed_x, numSteps=100000, sigma=0.01 ):
    optimal_x = [i for i in seed_x]
    optimal_w = w(optimal_x)

    cur_w = w(seed_x)

    for i in range(numSteps):
        new_x = [i+random.gauss(0, sigma) for i in seed_x]
        new_w = w(new_x)

        if (new_w > cur_w) or (random.random() > new_w / cur_w) :
            cur_x = new_x
            cur_w = new_w
            if cur_w > optimal_w:
                optimal_w = cur_w
                optimal_x = cur_x
    return optimal_x

我不熟悉 seed_x、sigma 和高斯分布，所以我不确定他们是如何得出 new_x。

我正在尝试根据许多变量（>10）求解一个值，并且我正在尝试比随机猜测更好地进行优化，因为它需要永远。

谢谢！

Answer 1

模拟退火 TLDR：我们试图找到一组参数，通过向参数添加随机噪声来最大化函数。如果改变导致改进，则接受改变；偶尔我们会接受负面的变化，但随着时间的推移，这种可能性会降低，而且变化有多糟糕。

在上面的代码片段中，该函数实际上使用了多个参数，但将它们作为列表接受：

w是参数优化的函数
seed_x 是参数的初始猜测 - 可以随机选择，但有根据的猜测会更好
高斯只是噪声的“形状”，因此小值更常见。 random.random()*sigma（所有值的可能性均等）在那里也可以正常工作。
sigma 是要注入的噪声量级。它不应超过典型参数值的百分之几。如果参数值的大小差异很大，请考虑使用每个参数特定的 sigmas 列表。
缺少：温度的概念，这实际上会使它模拟退火

用温度、更具描述性的名称和更明确的方式重写它：

def simAnneal(utility_func, initial_params, numSteps=100000,
              noise_magnitude=0.01, cooling_rate=0.999):
    optimal_params = initial_params
    params = initial_params.copy()  # lists are mutable, so .copy()
    best_utility = utility = utility_func(*initial_params)
    temperature = 1.0
    
    for i in range(numSteps):
        temperature *= cooling_rate
        # consider using numpy/scipy for params and noise
        new_params = [param+random.gauss(0, noise_magnitude) 
                      for param in params]
        # explicitly passing multiple parameters
        new_utility = utility_func(*new_params)

        if (new_utility > best_utility 
            or random.random()*temperature > new_utility / best_utility):
            params, utility = new_params, new_utility
            if new_utility > best_utility:
                optimal_params, best_utility = params, utility
    return optimal_params

最后但并非最不重要的一点 - 除非问题非常非凸，否则我敢打赌 SGD 会表现得更好。

具有多个变量的 python 中的模拟退火

simulated annealing in python with multiple variables

python

algorithm

math

multivariate-testing