常见优化算法

数据挖掘 算法

---

今天，在这里总结一下常用的几种优化算法，包括以下四种：

• 随机搜索法
• 梯度下降法（爬山法）
• 模拟退火法
• 遗传算法

在正式介绍这四种算法之前，需要引入的一个非常重要的概念叫做成本函数，它是解决优化问题的关键。任何优化算法其实就是要寻找一组能够使成本函数最小的解，也就是说对于解决问题的每一种方案，成本函数都会对应得到一个值，如果成本函数值越小，也即意味着达到相同目的所花费的“成本”越小，那么这个解（方案）也就更优。

---

随机搜索法

随机搜索法其实并不是一种非常好的优化算法，但是它却使我们很容易领会本文提到的所有算法的真正意图，并且它也是我们评估其他算法优劣的基准（baseline）。

顾名思义，随机搜索法每次都会随机得到一个解，因此其每次得到的解都可能比当前最优解更好或者更坏，当随机生成一定次数比如1000次后，把这1000次种成本函数最小也即这1000次随机猜测种最优的解作为最优解。很明显，这是一种纯靠人品的方法，科学家们可不相信这种靠人品的方法，于是就有了下面的方法。

---

梯度下降法（爬山法）

梯度下降法（爬山法）或许是最著名的优化算法之一吧，因为其是一种非常intuitive同时也很有效的优化方法。它的思想来源于，假设一个人站在山顶想要尽早下山，于是这个人下山时，他都会看看四周，看看哪里坡度最大（陡），然后就往那个方向迈出一步，每步都如此，一直到达山下。这是一种很直观的解释，更数学化的，我们怎么来刻画“哪里坡度最大（陡）”呢？数学上，我们就用梯度来刻画函数变化最快的方向，所以每次只需要计算其梯度，然后沿着梯度方向就能实现上面的策略了，因此这种方法也叫做梯度下降法。但是这种方法存在一些问题，比如最终解与初始解也有很大关系，很有可能陷入局部最优解（如上图所示），于是为了解决这个问题，就有了下面两种算法。

---

模拟退火法

模拟退火法是受物理学领域启发而来的一种优化算法。退火是指将合金加热后再慢慢冷却的过程。模拟退火也是从一个随机解开始，然后朝着某个方向变化。算法最为关键的部分在于，如果新的解成本值更低，那么新的解则会替代当前当前解，和爬山法类似，不过，如果成本只更高的话，这个解仍然有可能替代当前解。模拟退火算法之所有管用，不仅因为它总是会接受一个更优的解，而且还因为它在退火过程的开始阶段会接受表现比较差的解。随着退火过程的不断进行，算法越来越不可接受较差的解。更高成本的解，其被接受的概率由下列公式计算：

$$p = e^{(-(highcost-lowcot)/temprature)}$$
因为温度开始时非常高，p将总是接近于1，即表示有很大概率接受更高成本的解；而当温度变得越来越低时，高成本解和低成本解之间的差异会显得越来越重要，此时接受高成本解的概率就越来越低，因此该算法只倾向于稍差的解而不会是非常差的解。模拟退火算法与初始值无关，模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法，模拟退火算法具有并行性。

---

遗传算法

遗传算法也是受自然科学的启发。这类算法的运行过程是先随机生成一组解，称之为种群。在优化过程中的每一步，算法会计算整个种群的成本函数，从而得到一个有关题解的排序，在对题解排序之后，一个新的种群----称之为下一代就被创建出来了。首先，我们将当前种群中位于最顶端的题解加入其所在的新种群中，称之为精英选拔法。新种群中的余下部分是由修改最优解后形成的全新解组成。

常用的有两种修改题解的方法。其中一种称为变异，其做法是对一个既有解进行微小的、简单的、随机的改变；修改题解的另一种方法称为交叉或配对，这种方法是选取最优解种的两个解，然后将它们按某种方式进行组合。尔后，这一过程会一直重复进行，知道达到指定的迭代次数，或者连续经过数代后题解都没有改善时停止。