|
一般学习模拟退火算法的时候，都是用全排列问题作为例子讲解，所谓全排列问题，就是说解的长度（或者步骤）是确定的，只不过排列顺序不同罢了，其中任何一种排列顺序都是问题的一个解，我们通过不断尝试不同的排列顺序，找到其中最优的一个。
象TSP旅行商问题就是典型的全排列问题，所有的城市都是两两互联的，每个城市都要去一次（且只能去一次），先去那个后去那个，顺序不同只不过花费的代价不一样，但都是问题的一个解决方案。
注意：任何一种排列都是问题的一个解。这是一种很好的特性，这种情况下，可以直接应用典型的模拟退火算法。 |
模拟退火算法的核心就是对解的取舍。
第一步：首先生成一个初始解。
生成初始解的时候，你可以随机生成，也可以依照某种原则生成。无论怎样，反正就是一组排列。
当你把这组排列应用到问题域的时候， 会得到一个反馈的结果（也可以叫输出吧），比如说总花费、总路程之类的，一般我们希望这个结果越小（或者越大）越好。
这里，最优的输出值大概是多少，我们并不知道，甚至没有任何概念。
所以，应用这个初始解得到的输出，可能离目标很远，也可能离目标很近，哪怕他就在目的地门口，我们也一无所知。
第二步：变换解。
所谓变换解就是，我们把前一个解做一定的改变，具体怎么改变呢?
我要说取前一个解的领域，你可能会说我装逼（哈哈）。
其实想怎么变就怎么变，比如：将排列（即前一个解）中某两个元素的位置交换一下，再比如：将排列（即前一个解）从某个位置劈开，然后将两部分前后调换一下，再重新组合起来，等等。
发挥你的想象，只要你每次都用同样的变换就行。另外，变换最起码要遵守问题描述，比如每个城市只能去一次，你不能变的去两次。
现在我们有了一个新的解。
如果把这个新的解应用的问题域上，同样也会得到一个反馈结果（输出），同样，我们还是不知道这个输出距离最终目标有多远。
不管怎么样，我们至少可以确定一点，新解和旧解的输出肯定不同。
变换的核心思想就是：差之毫厘，谬之千里。
第三步：新解的取舍。
现在我们有两个解和两个解的输出。虽然我们不知道最终目标输出是多少，但是哪个解的输出距离目标更近一点我们应该能看出来。
比如：旧解的输出是花费100元，新解的输出是花费80元。
如果像这样，新解比旧解“看上去”更好，我们就把新解作为当前解，回到第二步，用它再做新的变换。
注意：这里我用到一个“看上去”，确实是这样，只要看上去更好就行，你不用考虑更多，也许他可能要兜圈子。
如果新解比旧解看上去要差呢？扔了它？那就成了贪心算法了。模拟退火的核心就在这里，怎么取舍这个看上去差一点的解。
要说公式有点复杂，要说白了其实很简单，就是掷骰子。
骰子出大时候，我们就接受这个看上去差一点的解作为新的当前解，用它再做新的变换。
如果骰子出了小，那只有放弃他了，当前解不发生改变，还是前面的旧解，下一次变换只能
再次用他重新来一次。当然这个骰子做了一点手脚，刚开始总是出大，后来大小出的差不多，再后来就总是出小了。具体原因大家自己看公式去吧。
这里想说一下，为什么我们要用一定的可能性来接受这个看上去差一点的解能？
因为这个解虽然差一点，但是也许只是看上去差一点， 作为下一个变换的起点，看上去差一点的解不见得比看上去好一点的解前途更差。
延安的共军和重庆的国军，你选哪个呢？身在其中，有时候骰子可能更靠谱一点。
第四步：循环。
现在，我们可能接受了变换解作为当前解；也可能放弃了变换解，当前解没发生变化，还是上一个解。
不管怎么样，回到第二步，对当前解继续使用变换，取舍，循环下去。。。。。。。。
第五步：退出。
前面我们说过，一般情况下我们不知道最终目标是多少，如果知道的话，比如花费40元，如果某一个解的输出得到了这个花费40元，那么你的算法就可以退出了。这个解就是一个最优解（因为他的输出你确定是最优的）。
但是一般情况下我们不知道最终目标说多少，怎么办呢？
前面我们分析过，虽然有时候通过骰子，我们可能会接受一些看上去差一点的解，但是经过许多次循环以后，我们获得的当前解还是越来越好的。
由于这样一个趋势，程序运行一段时间以后，我们无论再怎么变换出新解，也得不到更好的输出。
但是骰子还会让我们接受一些差解，那不就死循环了吗？
别忘了，骰子也有一个趋势，就是到后来就总是出小，即不再接受差解。
这样，找不出更好的解，也不再接受差解，如果当前解经过长时间都没发生改变，比如说100000次循环都没变，那么我们就可以认为当前解就是比较优秀的解了，可以退出了。
还有一种类似的方法是看输出。比如，初解的输出是100元，过了一会得到一个更好的值80元，再过一会又得到一个更好的值40元，然后经过长时间的运算也没找到更好的输出，那么40元输出对应的那个解就是比较优秀的解。
最后一个问题：是最优解吗？
回答：保证是比较优秀的解；很可能是最优解，但不能保证。哪怕你得到40元这个当前最好输出以后又运行了1年，没有找到更好的输出，也不能保证40元对应的解就是最优解（也许他真的就是）。
最优解有时候就像本拉登，天天在你身边，你也不一定认得出来。
//==========================================