不同于之前的分类和聚类算法,优化的目的是尝试找到一个使成本函数输出最小化的值。这里主要包括两个算法:模拟退火算法和遗传算法。

成本函数:
接受一个经推测的题解,并返回一个数值结果,该值越大代表成本越高(题解表现越差),该值越小就表示题解越好。

模拟退火算法:

优化算法的目标可以看为寻找x使函数f(x)最小。

但是严格的最小值往往是很难达到的,我们不得不把眼光投入到寻找一个尽可能好的次优解去。

最简单的方法被称为随机法,即成千上万次的对x进行猜测,然后把这些x中使f(x)最小的一个作为答案。虽然这样很简单,但是效果很差。于是出现了爬山法。

爬山法从一个随机解出发,然后不断向该解附近的使f(x)的值更小的x移动,直到当前x附近的解都比x差为止。为了使效果更好,我们可以从多个随机解出发重复着一个过程,将最好的一个作为答案。很容易就能认识到,这样找到的解是一个极值点,是一个局部最小值。

爬山法虽然好,但是在其寻找最优解的过程中,前进的方向是固定的(使f(x)更小的方向),但是有时向其他方法前进也是必要的,因为f(x)可能先增大在变小成为最优的。

于是就有了模拟退火法。

该算法这源于固体的退火过程,即先将温度加到很高(大量原子被激发),再缓慢降温(即退火),则能使达到能量最低点。如果急速降温(即为淬火)则不能达到最低点。

模拟退火法同样是从一个随机解出发。但是它在寻找最优解时并不一定是向更好的x移动,也有一定的概率向更差的x移动,这个概率开始较大,但是会随时间而渐渐变小,直到稳定。一般该概率可以定义为:p=e ^ (-  (highcost – lowcost ) / temperature ),其中temperature是随时间增大而变小的温度,开始温度很高时p -> 1,后来会渐渐变小使p->0。

遗传算法:

遗传算法的思想来自生物的遗传和变异,算法以种群为单位(一个种群为一组既多个解),其算法的运行过程如下:

  1. 随机生成一组初始解(初始种群)。
  2. 计算种群中各个解的成本,然后进行排序。
  3. 我们将种群中靠前(成本低)的解保留下来,删除其他解,这一过程称为精英选拔。
  4. 对已有解进行微小的改变,将改变后的结果作为新的元素加入种群,这一过程称为变异。
  5. 选择一些优秀的解两两组合,然后将他们按某种方式进行结合(如求平均),将得到的结果作为新的元素加入种群,这一过程称为交叉(配对)。
  6. 不断重复2—5步,直到达到指定迭代次数或成本函数连续数代都没有更好的改善。
  7. 得到一组解,该组解为算法输出。

该系列结束,恩,也许以后学了更多,有了更好的了解后会回来改一改,谁知道呢?