我有一个与这篇文章类似的问题模拟退火 - 直觉但不满意/不理解答案。
我知道这两种算法很可能最终陷入局部最大值/最小值。不过,我不明白模拟退火对温度和探索的使用如何增加找到更接近全局最大值/最小值的解决方案的几率。接受更差的解决方案来探索解决方案空间是否与进入更好的解决方案有相同的机会进入更差的局部最小值/最大值?
同样,我知道您可以同时存储在模拟退火中找到的最佳解决方案,因此可以自由探索解决方案空间,而不必担心陷入更差解决方案的风险。但这比仅仅调用爬山算法的多个实例更好呢?这两种算法不是都会探索解空间并返回找到的最优解吗?
我认为我的误解在于模拟退火的探索过程。对我来说,这似乎是一个任意的步骤,对爬山算法没有固有的好处。
我已尽最大努力研究这些算法,但它们都说同样的事情:“接受更糟糕的解决方案可以更好地找到更好的解决方案”。如上所述,我明白找到更好的是可能的,但找到较差的不是同样可能吗?
很难感受到要优化的目标;通常,它涉及多维、尖刺的景观,以及镜子和黑洞等异常现象。
即使对于光滑的二维表面,爬山也可能会“陷入”局部最小值。在不了解目标的情况下,如何将算法“抛出”局部最小值并不明显。你可能必须:
模拟退火的优点在于,通过结合温度和验收,它可以自动解决上述问题。请注意,根据设计,如果可能的话,它总是会找到一条“便宜”的路线来走出局部最小值。
在退火过程中的某个阶段,温度和验收之间的平衡恰到好处,允许改进,而不会陷入局部最小值的太大风险。它的优点之一是您不需要知道这个阶段在哪里;您只需知道该阶段在哪里即可。您可以从高温开始,以低温结束,在冷却过程中的某个地方,平衡恰到好处。
简而言之,爬山将陷入局部最小值,并且如何将算法“修补”成一个无论问题如何都能在探索和利用之间实现适当平衡的版本并不那么明显。一旦您以某种方式解决这些问题,您可能最终会得到类似于模拟退火的想法。