python 中多变量的模拟退火

Question

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

比试错更有效地优化多个变量的算法

不幸的是，我的更高级的数学有点缺乏，我对 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是要注入的噪声的大小。它不应超过典型参数值的几个百分点。如果参数值的大小差异很大，请考虑使用特定于每个参数的西格玛列表。
• 缺失：温度的概念，这实际上会使其成为模拟退火

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

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会表现得更好。