上班需要看运筹，顺便就把常见的优化算法复习一下。
运筹常见优化算法
运筹、动态规划需要使用到的算法大部分是最优化算法。常见有:
- 仓库调度——匈牙利算法
- 路径规划——遗传算法、蚁群算法等
- 仓库规划——线性规划、整数规划等
遗传算法
最优化算法之一，灵感神他瞄来源于达尔文的进化论。
基本概念：遗传算法将优化问题的解叫做个体，表示为一个变量序列。每一个序列中的值叫做基因。通常序列表示为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。
