模拟退火算法求全局最优解(内含详细注释)

lsj9383 · 发表于 2013-11-27 15:24:04

好久没发帖了~~，成都今日午后放晴，心情大好~~

这里简单介绍下，

求解某一个方程fun(x)的极小值，很常见的以一种情况是当前的x不管增大还是减小，函数值fun(x)均是增大，这时x就是极值。这是一种完完全全的贪心算法。这样求出的极小值，并不一定整段函数的全局极小值，而极可能是局部极小值。

例如下图

可以看出，有三个点，均是极小值点，在这是三个点处，不管增大变量，或是减小变量，目标函数的值都会增大。而只有最左边的那个点，才是全局最优解。

从数学模型上来看，是一种全局极小值求解问题，扩展到物理意义上，举几个例子：

我们什么PID参数，才是最优秀的呢？我们什么PID参数，才能让控制达到快准狠？自己一个一个的去套吗，累死。当然也可以用计算机一个一个去套，但是这样仍然非常花时间。利用模拟退火算法，就可以很好的求出最优PID参数。

再比如我们的聚类算法，什么样的码本设计，才能使得矢量量化的误差减为最小，这仍然是一个全局最优搜索问题。

求解全局最优解，有很多方法，模拟退火法只是我们其中一个，

除此之外，还有遗传算法、禁忌搜索算法、蚁群算法、粒子群算法等等。各有优缺点。

模拟退火算法，显著的缺点是相较其他算法，其稳定速度较慢，优点是在参数合适的情况下基本上可以100%得到全局最优解。

求解一个一维输入一维输出函数的全局最小解。这个思想也可以扩展到求解任意函数，输出point时，的输入应该为多少。

例如：已知函数F(x)，我们想求输出3时的输入x为多少。我们可以将目标函数变换为

M(x) = (F(x)-3).^2 （平方或是求绝对值）

这样就转换为求解M(x)全局最小值0的问题。即当x满足F(x)=3 时，M(x)才能满足全局最小值。

我的vc代码里面是求解sin(x)+cos(0.3*x)这函数，x范围[-10 ,10]的全局极小值。

    这个函数的函数图，即上面那个函数图。

有其他问题再联系。

lsj9383 · 发表于 2013-11-27 15:26:25

关于模拟退火，有一个有趣的比喻，帮助大家学习和理解：

　　一般局部极小值算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。

　　模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。这就是模拟退火。