我使用了模拟退火算法来寻找给定函数的全局最小值，使用的资源是
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 mathimport numpy as npimport numpy.random as rnimport matplotlib.pyplot as plt # to plotfrom scipy import optimize # to compareimport seaborn as snsdef 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_listdef 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 pdef 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第三版的伪代码
下一个只是当前的一个随机选择的继任者。
此外，我在我的AI课程中记下了一条笔记，模拟退火算法如果从高温开始并足够缓慢地降低温度，就保证会收敛到全局最大值。（我的意思是我的教授没有提到“下一个点”或者我可能错过了，或者也许这并不重要）。
顺便说一下，我在想问题可能出在选择“下一个点”的机会上，如果y和new_y都是负数，那么即使T足够小，选择下一个点的概率也很高。例如
如你所见，在第891步，y和new_y都是负数，我们选择了new_y，然而T是0.109
再次强调，问题是，伪代码中给出的概率公式与我在代码中使用的概率公式是相同的
回答：
