模拟退火收敛到错误的全局最小值

Question

我实现了模拟退火以使用

找到给定函数的全局最小值

https://perso.crans.org/besson/publis/notebooks/Simulated_annealing_in_Python.html

虽然温度一开始很高然后慢慢降低（步骤的原因），但有时会给我错误的答案。（局部最小值）

我必须补充一点，我尝试使用随机开始爬山来解决问题，下面是给定时间间隔内的局部最小值列表：

x = 0.55 0.75 0.95 1.15 1.35 1.54 1.74 1.94 2.14 2.34 2.5

y = -0.23 -0.37 -0.47 -0.57 -0.66 -0.68 -0.55 -0.16 0.65 2.10 5.06

和optimize.basinhopping()证明全局最小值是(1.54, -.68)

代码如下：

import math
import numpy as np
import numpy.random as rn
import matplotlib.pyplot as plt  # to plot
from scipy import optimize       # to compare
import seaborn as sns

def annealing(random_start, func, func_interval, random_neighbour, acceptance, temperature, maxsteps=1000, debug=True):
    """ Optimize the black-box function 'func' with the simulated annealing algorithm."""
    x = random_start(func_interval)
    y = func(x)
    x_list, y_list = [x], [y]
    for step in range(maxsteps):
        fraction = step / float(maxsteps)
        T = temperature(fraction)
        new_x = random_neighbour(x, func_interval, fraction)
        new_y = func(new_x)
        if debug: print("Step #{:>2}/{:>2} : T = {:>4.3g}, x = {:>4.3g}, y = {:>4.3g}, new_x = {:>4.3g}, new_y = {:>4.3g} ...".format(step, maxsteps, T, x, y, new_x, new_y))
        if acceptance_probability(y, new_y, T) > rn.random():
            x, y = new_x, new_y
            x_list.append(x)
            y_list.append(y)
            # print("  ==> Accept it!")
        # else:
        #    print("  ==> Reject it...")
    return x, func(x), x_list, y_list

def clip(x, func_interval):
    """ Force x to be in the interval."""
    a, b = func_interval
    return max(min(x, b), a)

def random_start(func_interval):
    """ Random point in the interval."""
    a, b = func_interval
    return a + (b - a) * rn.random_sample()


def random_neighbour(x, func_interval, fraction=1):
    """Move a little bit x, from the left or the right."""
    amplitude = (max(func_interval) - min(func_interval)) * fraction / 10
    delta = (-amplitude/2.) + amplitude * rn.random_sample()
    return clip(x + delta, func_interval)

def acceptance_probability(y, new_y, temperature):
    if new_y < y:
        # print("    - Acceptance probabilty = 1 as new_y = {} < y = {}...".format(new_y, y))
        return 1
    else:
        p = np.exp(- (new_y - y) / temperature)
        # print("    - Acceptance probabilty = {:.3g}...".format(p))
        return p

def temperature(fraction):
    """ Example of temperature dicreasing as the process goes on."""
    return max(0.01, min(1, 1 - fraction))

def see_annealing(x, y, x_list, y_list):
    sns.set(context="talk", style="darkgrid", palette="hls", font="sans-serif", font_scale=1.05)
    xs = np.linspace(func_interval[0], func_interval[1], 1000)  # Get 1000 evenly spaced numbers between .5 and 2.5
    plt.plot(xs, np.vectorize(func)(xs))
    plt.scatter(x_list, y_list, c="b")
    plt.scatter(x, y, c="r")
    plt.title("Simulated annealing")
    plt.show()

if __name__ == '__main__':
    func = lambda x: math.sin(10 * math.pi * x) / 2 * x + (x - 1) ** 4
    func_interval = (.5, 2.5)
    x, y, x_list, y_list = annealing(random_start, func, func_interval, random_neighbour, acceptance_probability, temperature, maxsteps=1000, debug=False)
    see_annealing(x, y, x_list, y_list)
    print(x, y)

    print(optimize.basinhopping(lambda x: math.sin(10*math.pi*x)/2*x + (x-1)**4, [random_start(func_interval)]))

但是怎么了？

编辑：

@user3184950 你是对的，算法现在运行得更好了，但这里是 AIMA 第三版的伪代码

next is just a random selected successor of current.

此外，我在我的 AI 课程中写了一条笔记，如果我们从高 T 开始并足够缓慢地降低它，模拟退火保证收敛到全局最大值。（我的意思是我的教授没有说任何关于 "next point" 或者我不知何故错过了它，或者这无关紧要）。

顺便说一句，我在想问题是取"next point"的机会，如果y和new_y都是负数，那么即使T是，取下一个点的概率也很高足够小。例如

如您在步骤 891 中所见，y 和 new_y 均为负数，我们取 new_y，但 T 为 0.109

同样的问题是，伪代码中给出的概率公式与我在代码中使用的概率公式相同

Answer 1

看来邻居不是最优的

def random_neighbour(x, func_interval, fraction=1):
"""Move a little bit x, from the left or the right."""
amplitude = (max(func_interval) - min(func_interval)) * 1 / (fraction + 0.1) 
delta = 1 * amplitude * (.5 - rn.random_sample()) 
print(delta)

return clip(x + delta, func_interval)

你需要一些东西，它会以相同的概率移动到 left/right，但可能在退火开始时更随机地移动，而在接近结束时移动得更少。

以上只是一个似乎效果更好的提议。

模拟退火收敛到错误的全局最小值

Simulated annealing converges to wrong global minima

python

artificial-intelligence

simulated-annealing

mathematical-optimization