优化算法

上班需要看运筹,顺便就把常见的优化算法复习一下。

运筹常见优化算法

运筹、动态规划需要使用到的算法大部分是最优化算法。常见有:

  • 仓库调度——匈牙利算法
  • 路径规划——遗传算法、蚁群算法等
  • 仓库规划——线性规划、整数规划等

遗传算法

  • 最优化算法之一,灵感神他瞄来源于达尔文的进化论。

  • 基本概念:遗传算法将优化问题的解叫做个体,表示为一个变量序列。每一个序列中的值叫做基因。通常序列表示为0,1向量。

  • 基本过程:
    • 遗传算法首先会随机生成一定数量的个体
    • 计算每一个个体的适应度
    • 使用轮盘法等方法挑选最优的个体,适应度越高,留下概率越大。
    • 接着对该种群进行交叉和变异,重复第二步直到满足循环条件。
      • 交叉就是俩数列抽一段互换
      • 变异就是一个数列随机抽一个值替换成别的值
  • 通俗表达:在广袤的菜园里有一群无忧无虑的豌豆,每隔一代就有个叫孟德尔的恶魔把其他的豌豆掐死,只保留黄色的豌豆,过了一千代后豌豆全变成了黄色的。(我居然还记得高中生物的这个恶魔)

退火算法

  • 灵感来源于合金加热冷却的过程。用一个变量表示温度,一开始非常高,而后逐渐降低。这个变量可以看作是对误差的容忍度。

  • 基本过程:
    • 首先设定一个很高的容忍值,随机生成一个数列。
    • 随机让该数列一个值\(\pm1\)
    • 如果这个新的数列误差较小,或者当概率小于在温度\(T\)的条件下,出现能量差为\(dE\)的降温概率\(P(dE) = \exp(dE / (T))\)时,接受这个新的数列。
    • 降温,重复第三步直到温度降到接受范围。
  • 通俗表达:一个喝醉酒的仙人要到谷底,一开始到处乱跳,可能跳到最高处也可能跳到最低处,随着酒精浓度越来越低,最终仙人朝着最低的路线跳下去。(于是有了仙人跳)

爬山法

  • 灵感来源于人类爬山的过程。每一次都向最高或最低的方向移动,当移动到顶点的时候就停止移动。

  • 基本过程:
    • 随机生成一个数列
    • 向左向右移动一个单位,选择损失最小的点
    • 重复第二步直到无法移动或满足步数要求
  • 通俗表达:一只单身狗要爬山看日出,每次都往高的地方爬,最后爬到一个往前挪一步就是下降的地方停止。(最后举起了FFF团的旗帜)

在这之前的三个算法都可以在《集体智慧编程》第五章找到实现代码。如果愿意也可以看我fork的这部分代码。如果有人用R的话,有个叫genalg的包是提供遗传算法的,代码质量肯定比自己实现的好。

梯度下降

  • 加强版爬山法。爬山法的步长不容易控制,方向不定。梯度下降指定了爬山最快的方向,即导数方向,沿着该方向按照指定步长移动。
  • 梯度下降的数学表达就是: \[ \boldsymbol{\theta}:= \boldsymbol{\theta} - \alpha \nabla f(\boldsymbol{\theta}) \\ \text{or} \\ \boldsymbol{\theta}:= \boldsymbol{\theta} - \alpha \frac{\partial{f}}{\partial{\boldsymbol{\theta}}} \]
  • BGD(批梯度下降)就是最原始的梯度下降,每次更新的时候都是处理全量数据。需要的计算量大。但可以保证收敛到局部最优。
  • SGD(随机梯度下降)每次下降按照某一个点更新。需要迭代次数多,但是计算量小,收敛快。可以收敛到局部最优附近。
  • MBGD(小批梯度下降)一个介于BGD和SGD之间的优化算法,兼顾二者的优点。

实现了一个非常简单的梯度下降,高质量的随机梯度下降实现可以看Machine Learning in Action,或者Data Science from Scratch。

乞讨码