江苏龙网

  1. 首页 > 生活 > >

模拟退火为啥和起始点无关算法是向一个方向遍历的，如果起始点本身就已经过了最值点，那不还是找不到么

模拟退火是初始值不敏感，不是完全无关。算法必须能遍历整个解空间，所谓“向一个方向”是不对的。前几次概率大些，是为了避免过早陷入局部最优，这本身没有问题。
■网友
以百度百科中的“原理”部分为例（http://baike.baidu.com/view/476038.htm） 首先，如（1）中所描述T已经足够大，因此，有很大概率，最优解在T的下方。 其次，从（4）中描述可看出，（3）求得的新解S\u0026#39;有可能大于、等于或者小于原解S，只是针对不同情况，更新公式不同。收敛的过程中delta(t)会逐渐变小，直至趋于“零”。 此外，注意SA的全局收敛性只在概率意义下成立，但在实际问题中不能绝对保证，因此T和初值的选择对结果会有影响。
■网友
我也刚刚有这个疑问，一搜，竟然zhihu上也有人问。。。如果一开始就是最值，一开始又有很大几率往坏的路一路不返...
■网友
结合前面的两个答案，以及模拟退火算法解决TSP问题，考虑了一下，我倾向于认同“并非朝一个方向遍历”这个说法。其实本质上TSP问题就是一个排序问题，比如有3个城市供选择，编号123，则有6种遍历方法（1→2→3→1，1→3→2→1，2→1→3→2，2→3→1→2，3→1→2→3，3→2→1→3）。如果想要随机产生一种遍历路径，我们可以对一个数组CityNum=｛1，2，3｝执行一种类似于“洗牌”的工作，用随机数发生器产生两个3以内的随机数（0，1或2），然后以产生的随机数为索引来交换对应位置的元素。比如产生了随机数1，2，则CityNum变成｛1，3，2｝，那么旅行商人的路径1→3→2→1了。如此这般多洗几次就相当于获取不同的路径图。用模拟退火算法解决TSP问题的步骤如下：（1）随机打乱城市先后次序，产生一个遍历路径1，然后记下全距离D1;（2）再次打乱城市先后次序，产生遍历路径2，然后记下全距离D2；（3）比较D1和D2，如果说D2更小，则D2替代D1；如果D1更小，则D2有概率P(dE)会替代D1。（4）再次打乱城市先后次序，产生遍历路径3，然后记下全距离D3……等等，停！就是这里，看出来了没有？每一次打乱城市先后次序完全是随机的，它不代表初始路径是什么，接下来就不允许再出现这个路径了。举一个更加形象的例子，洗牌也完全可能洗出跟上上一次相同的情况来。因此关于是否真的“无法回去了”，这样应该能回答这个问题了吧。2016.3.22
■网友
【模拟退火为啥和起始点无关算法是向一个方向遍历的，如果起始点本身就已经过了最值点，那不还是找不到么】 类似的算法很多，粒子群，遗传算法，天牛须搜索（https://zhuanlan.zhihu.com/p/30742461），如果你看下相应的全局收敛性的证明分析，你会发现，最后都是通过一个马尔科夫场，或者马尔科夫链来解决，而全局收敛点就是这里的吸收态。

■网友
在给定温度下, SA就是态空间的random walker. 由微观态等几率假设可知此随机行走必然是各态历经(ergodic). 所以一定能找到最低能态作为系统的平衡态. 而温度只是平衡态下刻画平均能量的一个参数, 所以绝热降温一定能够保证系统始终处于平衡态, 即最低能态.这就是SA的物理意义.
■网友
我想问问，降温处理，除了乘以一个小于1的概率，还有其他方法降温么？？


    推荐阅读


    上一篇：学习美国亚马逊有哪些比较有用的论坛，求推荐。谢谢

    下一篇：如果完全断网了，怎样访问Stackoverflow?