《运筹帷幄》温故
作者： @badyb是兽米克莱门森大学数学硕士(运筹学方向)，Ph.D. Candidate，欧盟酷灰狼学者，德国海德堡大学数学博士(离散优化、图像处理方向)，期间在意大利博洛尼亚大学，作者目前德国某汽车集团无人驾驶部门的计算机视觉研究开发工程师。
本文于2017-02-12首次在【运输业OR运筹广】知乎专栏发表。
编辑：本文于2017-02-12首次在【运输业OR运筹广】知乎专栏发表。 运筹学---operationsresearch(o.r.)，又名数学规划、优化理论。 另外，作者将其称为人工智能的“引擎”。 因为大多数人工智能问题最终都会求解优化问题。 正如几年前流行的支持向量机(SVM，二次规划问题)一样，近两年席卷全球的深度学习)的参数优化(训练)也是高度复合函数无约束优化问题)。 以运筹学、数学规划的角度介绍多种优化算法的异同和解决实际问题的一般步骤。 数学模型的建立-算法的设计-编程的实现。
前言
运筹学(优化)的分支非常巨大，所谓隔行如隔山，学者对自己所属分支的概念)术语非常熟悉，但如果属于优化领域，其他分支的术语就会一头雾水。 第一次参加学术会议，上司heuristic是什么？ 我很记得曾问过他。 然后在组合优化会议上向奇怪的长筒袜项目ETH的同事问，PTAS是什么psddy？
介绍以上优化算法的异同和解决实际问题的一般步骤，仅从操作系统下算法的概念和知识点的普及出发，主要从操作系统、数学规划的角度出发：数学模型的建立-算法的设计-编程的实现。
这篇文章从以下回答中扩展了。 (请看其他学者的精彩回答。 如@大洪) )。
遗传算法、模拟退火算法、粒子群算法、神经网络等智能算法的作用是什么？ http://t.cn/rq新0
在正式回答这个问题之前，我先介绍一下运筹学――operationsresearch(o.r.)，又名数学规划，优化理论。 另外，我把它叫做人工智能的“引擎”。 因为大多数人工智能问题最后都会变成求解优化问题。 正如五年前流行的支持向量机(SVM，二次规划问题)，近两年席卷全球的深度学习)的参数优化(训练)也是高度复合函数无约束优化问题)。
对还不熟悉运筹学的朋友，下面的文章可能会有用。
人工智能的“引擎”---运筹学、建模、优化、决策的科学： http://t.cn/ROBybx3
0
启发式算法(Heuristic Algorithm )
启发式通常是面向问题的。 也就是说，没有通用的框架，每个问题都会设计不同的启发式算法，通常用于求解组合优化问题。
由于组合优化通常是NP (完全)困难的)，所以一般需要指数算法的复杂性，不存在多项式时间算法)，在现实应用中，为了迅速得到高质量的可行解，算法)通常需要多项式时间算法，人们普遍认为通常，它是一种贪婪算法，只求局部最优解，没有摆脱局部最优解的有效方法。
1
元启发算法(魅力大象(-heuristic Algorithm ) ) )。
与一般的启发式算法不同，元启发算法对于普遍问题来说是布尔独立的。 把他当作黑匣子可以用于大部分问题，通常需要给出初始解。 (当然，不能保证多项式时间会收敛，但一般可以控制迭代次数)
一些遗传算法、蚁群算法、进化算法、智能算法几乎都属于这个范畴。
个人倾向于把它们看成一个个的基本框架(general framework )，在这个框架下，有不同的算法。 (通常是基于一定规则的迭代算法)
值得注意的是，通常会提出摆脱局部最优解(如蒙特卡罗方法)的方法，从而可以从第二个点跳到第三个全局最低点。 (不能保证在有限的时间内全局收敛是最有利的)
另一方面，0的启发式算法从最初的点出发时，通常会收敛到第2个点并停止搜索。
在我建设的全球物流学家中就这个问题进行了激烈的讨论，感谢英国Cranfield大学@宋伯阳的见解。 算法如果只分为两种，就是精确的算法和启发算法。 所有的启发，元启发算法都不是精确的算法(不能保证得到最优解)。 启发算法和元启发算法最大的区别在于启发算法要求更多的局部最优。 在元启发算法的设计中，有克服陷入局部最优的机制，适合寻求全局最优。 例如，遗传算法GA有突变Mutation机制。 其次，启发算法的设计多依赖于问题Problem-dependent，元启发算法独立于问题Problem-independent (可以作为black box进行操作，适用性很广，但根据问题不同，算法也可以元启发
算法范围内大部分应用了随机优化机构，多目标优化用的蛮多。但是多目标优化中，目标太多时一般会先降维（比如PCA），多于3-5个目标的优化效率低，也没有太多实际的可读性。接近实际的案例里面一般都会涉及多种算法，先用元启发算法求得一个小范围的满意解，再用启发或者精确算法找最优解，这样即提高了计算效率又能有高质量结果。（算法种类和术语名字太多，看到各种名字很容易晕，其实很多都有相关性（差不多），弄清楚他们之间的关系还是有点重要的）。2
近似算法（Approximation）、PTAS
其次求解组合优化问题时，近似算法也经常用到，他们本质上通常是贪心算法，而且通常都是多项式时间的算法。
与一般的贪心算法不同，他们通过巧妙的算法设计，可以用严格的数学证明这个算法得到的解，离全局最优解差A倍。（A被称为近似系数。）
例如一个最大化的组合优化问题，假设全局最优解的目标函数为100，那么近似系数A=2的近似算法收敛求得的解一定在[100，200]，最坏情况是200。
文章开头提到 PTAS，也是近似算法的一种，这里需要保证近似解无限接近于全局最优解，例如(1 + ε)L，L是全局最优解， ε无限接近于0。
但是必须要求算法复杂度还是多项式复杂度， 例如O(n^(1/ε))甚至 O(n^exp(1/ε))。
Polynomial-time approximation scheme：http://t.cn/RRIFlEG
理论计算机方向便是专门研究近似算法的，其顶级会议FOCS，STOC，SODA是其顶级会议。
3
数学模型、精确算法(Exact Algorithms)
组合优化问题的精确算法，是混合整数规划模型下的优化算法，然后用分支定界法求解。然而分支定界法是指数级复杂度的，例如n是{0，1}变量(binary variable)的个数，那么最坏情况下，分支定界法最坏情况需要求解2^n个线性规划问题（每个线性规划多项式时间可解），才能得到全局最优解。
因此解决实际问题通常的做法是，先用1或2的算法，快速得到一个可行解F，然后把这个可行解F作为初始解插入到分支定界法的优化求解器（例如IBM Cplex, Gurobi, FICO Xpress），作为上界（Min 问题）。
这时候，混合整数规划模型的意义有两点：
一、只需要求解Root node（原问题的线性松弛问题），便得到原问题的下界，上下界的所形成的百分比（GAP），便可作为初始解F质量的一个检验标准。（上界=下界时，GAP=0，即已找到全局最优解）
二、随着分支定界法求解的进行，优化求解器很有可能找到比F更优的解（Better Upper Bound），从而缩小GAP。
在工业应用中，例如最小化企业成本，我们通过1或2可以较为快速地得到一个方案（可行解），其成本为F（例如F=100）。然后我们设计一个混合整数规划模型，那么我们可以很快地知道F这个解到底有多好，其次，优化求解器可以帮我们找到一个更优的解G（例如G=98），缩小了2%的GAP 。
可别小看这2%，在工业界，2%的成本可能已经是几百甚至上千万的差别！！！
更多介绍：
混合整数规划/离散优化的精确算法--分支定界法及优化求解器
4
神经网络(Neural Network)
神经网络，包括CNN（深度学习的底层模型），是一个模型/框架，而不是算法，通常限于求解分类问题（Classification Problem）。个人倾向于把CNN看作进化版的元启发模型（当然有监督这一点是其他元启发所不具备的），可以把它当作黑箱子直接拿来用。
其目标函数是一个高度复合的无约束的函数，而训练参数的过程（算法），通常使用方向传播法，可以把它理解为一种特殊的梯度下降法。
CNN里面，有Relu和Dropout，前者是为了提高函数的非线性性，后者为了简化函数参数的训练。
这个高度复合的函数是一个极度非凸函数（请点下一个链接学习基本概念），很难求解全局最优解，但是貌似有理论证明（或是大量实验表明？），反向传播法求得的CNN的局部最优解，通常已经是一个非常好的解（并且存在大量类似高质量的局部最优解，因此随便找到哪一个都是不错的结果）。
离散/整数/组合/非凸优化概述及其在AI的应用
从数学规划的角度，一个没有约束条件的优化问题，比有约束的优化问题（如线性规划）容易求解很多。
因此从这个意义上讲，运筹学比起神经网络可以解的问题更general，问题更难。
但是，CNN虽然没有约束条件，但是难度在于目标函数极度非凸，以及变量的数量极其庞大！
5
多种模型解分类问题（Classification Problem）
众所周知，解决同一个问题，可以用不同的模型和算法。
和3同样的思路，我可以把CNN这个黑箱子所解的实际问题，例如分类问题，也建模成一个混合整数规划模型。
例如下面这个分类问题，2016年运筹学者的新作，引入混合整数规划做了改进版的支持向量机，其中{0,1}变量z_i代表了outlier(=1)，就可有效防止神经网络模型的“用力过猛”（over-fitting）。
Recall that一个数学规划问题的三要素：变量、目标函数、约束条件，和神经网络模型的思路 是完全不同的。
而第二张图用神经网络（不是CNN）来求解这个分类问题，其output--神经网络求得的局部最优解（多层网络便可产生极度非线性），可以作为上面混合整数规划模型的初始解，直接插入Cplex这样的商业优化求解器中，直接给出GAP以及搜索更优解。（很遗憾，CNN解决的问题通常规模实在太大，MIP基本跑不动，因此几乎没有学者在做这件事：）
更多介绍：
大话“人工智能、数据科学、机器学习”--综述：http://t.cn/RXkSyMn
6
后记
人工智能、运筹学的交叉愈演愈烈，运筹学、优化的国际盛会，AI已逐渐成为运筹学者们热议的话题，并且AI的讲座通常都是爆满状态。
运筹学、数学规划、优化--国际协会、奖项、会议大搜罗
而深度学习这个黑箱子，也亟待深层次优化理论的进一步“洗礼”。
最近因为AlphaGo，AlphaZero火起来的增强学习（也被称为近似动态规划），也会给运筹学、算法学界带来更多的思考。（今天没有提到动态规划算法，希望相关学者踊跃投稿～）
科学因为各个学科深度交叉而快速发展，跨界势在必行。
文末，借用亚琛工大运筹学教授radbm Lübbecke在德国运筹学年会特邀报告上的一句话结尾：
If the fourth industrial revolution is about AI, OR should be part of it.
下面链接是全文最干货的地方--教授的演讲PPT。（国内需要fanqiang）
Machine Learning meets Optimization:https://t.co/r1d6qhrlvi