如何有效地在为模拟退火1维和n维空间选择邻居 [英] How to efficiently select neighbour in 1-dimensional and n-dimensional space for Simulated Annealing

问题描述

我想用模拟退火找到当地的最低单变量多项式函数，一些pdefined $ P $区间内。我也想尝试和发现二次函数的全局最优解。

I would like to use Simulated Annealing to find local minimum of single variable Polynomial function, within some predefined interval. I would also like to try and find Global minimum of Quadratic function.

衍生无关的算法，如这不是解决问​​题的最好办法，所以这只是学习的目的。

Derivative-free algorithm such as this is not the best way to tackle the problem, so this is only for study purposes.

虽然算法本身是pretty的直线前进，我不知道如何有效地在单个或n维空间中选择邻居。

While the algorithm itself is pretty straight-forward, i am not sure how to efficiently select neighbor in single or n-dimensional space.

让我们说，我期待的功能当地最低：2 * X ^ 3 + X + 1在区间[-0.5，30]，并假设间隔减少到每一个数字，如：{十分之1.1，1.2，1.3，...，29.9，30}。

Lets say that i am looking for local minimum of function: 2*​x^​3+​x+​1 over interval [-0.5, 30], and assume that interval is reduced to tenths of each number, e.g {1.1, 1.2 ,1.3 , ..., 29.9, 30}.

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

What i would like to achieve is balance between random walk and speed of convergence from starting point to points with lower energy.

如果我现在选择每次随机数形式给定的时间间隔，那么就没有随机游走和算法可能围一圈。如果，相反的，下一个点被选择通过简单地增加或减去0.1与相等概率，则该算法可能变成穷举搜索 - 基于所述起点

If i simply select random number form the given interval every time, then there is no random walk and the algorithm might circle around. If, on the contrary, next point is selected by simply adding or subtracting 0.1 with the equal probability, then the algorithm might turn into exhaustive search - based on the starting point.

我应该如何有效地平衡模拟退火邻搜索的一维和n维空间？

推荐答案

所以，你正在努力寻找n维点P即是随机附近的另一n维点P;例如，在距离T.（由于这是模拟退火，我以为你会偶尔递减T）。

So you are trying to find an n-dimensional point P' that is "randomly" near another n-dimensional point P; for example, at distance T. (Since this is simulated annealing, I assume that you will be decrementing T once in a while).

这可以工作：

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 *原点吨。

The output is randomly distributed in all directions and centred on the origin (notice that r.nextDouble() would favour 45º angles and be centred at 0.5). You can vary the displacement by increasing t as needed; 95% of results will be within 2*t of the origin.

编辑：

要产生近一个给定的一个流离失所一点，你可以修改为

To generate a displaced point near a given one, you could modify it as

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;
}

您应该使用相同的研究所有呼叫（因为如果你创建一个新的随机（）为每你将保持一遍又一遍得到相同的位移）。

You should use the same r for all calls (because if you create a new Random() for each you will keep getting the same displacements over and over).

这篇关于如何有效地在为模拟退火1维和n维空间选择邻居的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！