[关闭]
@chanvee 2015-09-10T05:36:21.000000Z 字数 1590 阅读 4183

常见优化算法

数据挖掘 算法


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

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


随机搜索法

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

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


梯度下降法(爬山法)

爬山法

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


模拟退火法

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

p=e((highcostlowcot)/temprature)

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


遗传算法

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

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注