优化二——启发式演算法
启发式演算法：这类演算法算是演算法在实际应用过程中的技术性演算法，因为在实际计算过程中，很有可能第一：无确定的目标函数；第二：无法找到真实的最优解；第三：计算代价非常大，现有的计算机技术都无法解决此类问题。所以人们就找到另一种情况，使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。 通熟点讲就是求出来的解可能不是最好的，只能说是相对较好的，但是这个相对程度就不敢保证了。虽然是这样，但是在工程应用上来说已经非常好了。
后面讲的时候可能会让你怀疑人生，这是演算法吗？不过它们在工程上来讲确实就是。第一个要讲的是模拟退火演算法，这个当年是俺对它进行了几次改造的，结合（SPSA）随机扰动演算法，来在一定程度上解决此山最优的局限(测试过几次，解决低维问题还行，还有一定的局限，就是初值的选取非常重要，必须在初值选取的时候就要接近真实值，这其实是很扯淡的，在自动历史拟合中，很多时候我们都是要进行初值的筛选的，不过这个时候初值的筛选过程就一定得有一定的依据，什么灰色关联啊什么的都出来了，反正非常大的系统知识)——扯远了。
模拟退火是什么意思呢？它不管你什么梯度啊什么步长，给定一个最低温度Tmin（这个值无限小）他只管其中一个事情，就是我们在求解的过程中，新迭代出来的函数结果与旧的函数的差值结果f(x_new)-f(x)>0时就无条件接受这个值，但是如果f(x_new)-f(x)<0，则以一定的概率（exp((f(xnew)-f(x))/k*T)）来接受这个值，然后对温度T进行一次更新，这个降温方法为T= a*T (0<a<1)，一般a取接近1的值。最后如果当前温度<Tmin时就退出循环了。 看根本就和什么梯度什么步长没关系。那么为什么要这样呢？我用通熟的方法给你们解释一下：
对于这样的一个函数，当前我们的内函数优化演算法都只能求解极值，如果极值是最值，那还好说，如果极值不是最值，那么就很尴尬了，模拟退火就是干嘛呢？假设求解最大值，就像图里面看到的X0是初值点，不论你用梯度什么方向，什么步长，他最终会收敛在（X1，Y1）这个点，整个过程叫做绝对上山过程，这个叫做局部最优，而模拟退火就是说你选择了X0作为初值点，假设下一个迭代的点X1带入目标函数F（X1）的值小于F（X0）的的值，也就是说下山了，咱也以一定的概率接受。这样就在一定概率上可以解决局部最优的情况。不知道这个说法合不合适。当然模拟退火它所谓的全局最优也只是人们在心里面的一个理想状态，实际在求解过程中，真的很少能够达到。
接下来讲另一种演算法：信赖域演算法。这个演算法更简单粗暴，它的主要修正是步长，也就是说，我们先在当前初始值附近构建一个近似原目标函数的近似模型。假设一个比较大的步长（试探步长），从初值迭代到新的值，对比两个模型的结果之间的比值γ，如果这个值接近1，说明近似函数与原函数的近似程度很好，此时应该增大一下原来的试探步长，如果这个值大于0但是不接近1，那么就保持原步长，如果这个值接近于0，则此时要缩小步长。通俗点来说我以某个图像来说吧，还是图像比较实在：
就是说你选了一个试探步长，结果呢算出来的值太小，（红色圈内的黑色圈就是表示算的太小），那就加大这个步长，如果这个黑色圈太大，那就缩小这个试探步长，直到合适为止。这玩意说来说去它还是只能在一定程度上来进行局部最优，如果说最优解的点根本不是这个红色圈，红色圈只是一个极值点，那么它还是不能说是最优解。这个时候，只能说在约束范围内尽量求解最优。至于怎么编程，网上都有好多呢，我只是讲讲这个概念。【图文】信赖域方法_百度文库
到后面的发展，人类根据动物的一些行为，出现了遗传演算法、粒子群演算法、神经网路演算法、禁忌搜索等等，太多了，反正挺有意思
我看别人讲了关于启发式演算法的一些小故事挺有道理，启发式演算法总结 - E_ROAD_BY_U的博客 - CSDN博客如下：
启发式演算法蕴含著许多人生哲学，它虽不是数学方法，其思想更类似于人类解决问题的思想和一些人生中总结的道理，值得好好体会。最后用网上一段描述局部搜索的例子来作为总结：
为了找出地球上最高的山，一群有志气的兔子们开始想办法。
· 兔子朝著比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是Iterative Improvement，它不能保证局部最优值就是全局最优值。
·兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝最高方向跳去。这就是模拟退火。
·兔子们知道一个兔的力量是渺小的。他们互相转告著，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。
兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传演算法。
太累了，以后再来慢慢讲这几个演算法的通俗理解吧。 然后最后会讲讲我读书的时候学习的两个用的最多的演算法——SPSA演算法和鲁棒优化演算法。
推荐阅读：
