读书笔记《集体智慧编程》Chapter 5 : Optimization

本章概要

本章介绍了优化问题的基本概念，以及常见的优化算法（随机搜索，爬山，模拟退火，遗传算法）。读完本章后，感觉茅塞顿开，之前一直认为遗传算法高深莫测，原来这些算法都是根据生物，物理的启发而来的，顿时亲切了许多。

什么是优化（Optimization）

一个问题的解有一系列组合，在这些组合中找出最优的解的过程就是优化。最笨的方法，枚举出所有可能的结果，找出最优的解。但是，往往可能性太多，计算机根本上无法枚举出所有的解决方案。

成本函数（Cost Function）

最优的解决方案在成本函数中得到最大或最小值。成本函数是指导优化继续进行的根本。

优化算法

• 随机搜索：计算一组随机的组合方案，在这个方案中找到最优秀解，比较盲目，有可能最优解并不在这个随机的解决方案中。
• 爬山：个人理解就是贪心算法，找到相比于当前解决方案而言最优的相邻方案，如此往复，直到找不到更优的方案为止。显著的问题就是只能找到局部最优解，无法找到全局最优解。改进算法是当找到一个最优解后，随机开始另一组探寻，多尝试几次。这样，虽然可以找到全局最优解，但是不能保证每次都可以。
• 模拟退火（Simulated Annealling）:此方法受物理中锻造合金的启发，首先将合金加热到一个高的温度，然后慢慢冷却，在冷却过程中，可以找到low energy configuration。算法大体思想与爬山有点类似，首先随机选取一个相邻的解决方案，如果更优，那么选取，否则，不拒绝，也不选取，会通过一个概率计算到底是拒绝还是选取，开始时，此概率会比较大，温度比较高，但是每一次选举后，温度会降低，选择较差方案的概率会降低。当温度降到一定程度，过程结束。这个方法可以使得优化在开始时，允许出现非最优解，这样可以加大找到全局最优解的机会。
• 遗传算法（Genetic Algorithm）:遗传算法受到生物遗传的启发，主要思路是首先随机组合第一代解决方案，根据目标函数的结果排序，取出最优的一部分作为第二代（称之为精英），其他的全部淘汰掉（是不是很残忍），然后在在精英中通过突变或者杂交的方式，创建出第其他的方案，称之为第二代，然后对第二待排序，任然取出精英，如此往复，直到精英基本不变或者代数到达一定上限时结束。

优化算法的不足

上面提到的优化算法依赖一个事实，最优解通常与次优解较近，但是如果较远，如下图所示：

全局最优点在比较靠右的地方，但是由于最优点的两边是一些不好的点，所以根据上面的优化算法，找到全局最游解的概率不高。如果解空间无规律，那么可能随机搜索会比其他优化方案更好。