我想用模拟退火在一定的区间内找到单变量多项式函数的局部极小值。我也想找出二次函数的全局极小值。
像这样的无导数算法并不是解决问题的最好方法,所以这只是为了研究目的。
虽然算法本身是非常直截了当的,但我不知道如何在单维或n维空间中有效地选择邻域。
假设我正在寻找函数的局部最小值:区间-0.5,30上的2*x^3+x+1,并假定区间被缩减到每一个数的十分之一,例如{1.1,1.2 ,1.3,…,29.9,30}。
我想要达到的是从起点到低能量点之间的随机行走和收敛速度之间的平衡。
如果我每次只从给定的间隔中选择随机数,那么就没有随机游走,算法可能会绕圈。相反,如果通过简单地以相同的概率加或减0.1来选择下一个点,那么该算法可能会变成基于起始点的穷举搜索。
如何在一维和n维空间中有效地平衡模拟退火邻域搜索?
发布于 2015-06-11 18:12:33
因此,你试图找到一个n维点P‘,它“随机”地靠近另一个n维点P;例如,在距离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(),则会不断得到相同的位移)。
发布于 2018-08-05 21:35:52
在“C++中的数值回收”中有一章题为“模拟退火的连续极小化”。我们在里面有
如果出现局部下坡移动时,随机变化的产生器效率很低,但它几乎总是提出上坡移动。我们认为,一个好的发电机不应在狭窄的山谷中变得低效;也不应随着收敛到最低限度而变得越来越低效。
然后,他们开始讨论一种“下坡单纯形法”。
https://stackoverflow.com/questions/30786439
复制相似问题