如何在一维和n维space中有效地select邻域进行模拟退火

Question

我想使用模拟退火在某个预定义的区间内找到单变量多项式函数的局部最小值。我也想尝试找到二次函数的全局最小值。

像这样的无导数算法不是解决问题的最佳方法，因此仅供学习。

虽然算法本身非常简单，但我不确定如何在单维或 n 维 space 中有效地 select 邻居。

假设我正在寻找函数的局部最小值：2* x^ 3+ x+ 1 在区间 [-0.5, 30] 上，并假设区间减少到每个数字的十分之一，例如 {1.1, 1.2 ,1.3 , ..., 29.9, 30}.

我想要实现的是随机游走和从起点到能量较低的点的收敛速度之间的平衡。

如果我每次都只是select随机数形成给定的区间，那么就没有随机游走，算法可能会循环。相反，如果下一个点是 select 以等概率简单地加减 0.1，那么算法可能会变成穷举搜索——基于起点。

我应该如何有效地平衡单维和 n 维中的模拟退火邻居搜索space？

Answer 1

所以你试图找到一个n维点P'，它在另一个n维点P附近"randomly"；例如，在距离 T 处。（因为这是模拟退火，我假设您会偶尔递减 T）。

这可行：

double[] displacement(double t, int dimension, Random r) {
      double[] d = new double[dimension];
      for (int i=0; i<dimension; i++) d[i] = r.nextGaussian()*t;
      return d;
}

输出随机分布在所有方向并以原点为中心（注意 r.nextDouble() 倾向于 45º 角并以 0.5 为中心）。您可以根据需要通过增加 t 来改变位移； 95% 的结果将在原点的 2*t 范围内。

编辑：

要在给定点附近生成位移点，您可以将其修改为

double[] displaced(double t, double[] p, Random r) {
      double[] d = new double[p.length];
      for (int i=0; i<p.length; i++) d[i] = p[i] + r.nextGaussian()*t;
      return d;
}

您应该对所有调用使用相同的 r（因为如果您为每个调用创建一个新的 Random()，您将不断获得相同的位移）。

Answer 2

在"Numerical Recepies in C++"中有一章标题为"Continuous Minimization by Simulated Annealing"。里面有

A generator of random changes is inefficient if, when local downhill moves exist, it nevertheless almost always proposes an uphill move. A good generator, we think, should not become inefficient in narrow valleys; nor should it become more and more inefficient as convergence to a minimum is approached.

然后他们开始讨论"downhill simplex method"。

如何在一维和n维space中有效地select邻域进行模拟退火

How to efficiently select neighbour in 1-dimensional and n-dimensional space for Simulated Annealing

java

algorithm

search

optimization

simulated-annealing