整数规划精确算法/近似算法/（元）启发算法/神经网络反向传播等算法的区别与关联

↑↑↑↑↑点击上方蓝色字关注我们！

『运筹OR帷幄』温故

作者：作者：@留德华叫兽美国克莱姆森大学数学硕士（运筹学方向）、Ph.D. Candidate，欧盟玛丽居里学者，德国海德堡大学数学博士（离散优化、图像处理方向），期间前往意大利博洛尼亚大学、IBM实习半年，巴黎综合理工访问一季。现任德国某汽车集团无人驾驶部门计算机视觉研发工程师。

本文于2017-02-12首次发布于【运筹OR帷幄】知乎专栏。

编者按：本文于2017-02-12首次发布于【运筹OR帷幄】知乎专栏。运筹学--Operations Research (O.R.), 别名数学规划、最优化理论。此外作者称其为人工智能的“引擎”，因为几乎所有人工智能的问题最后都会转化为求解优化问题。数年前流行的支持向量机（SVM，二次规划问题）如此，近俩年席卷全球的深度学习（DL）的参数优化（训练）也是（高度复合函数无约束优化问题）。本文以运筹学、数学规划的视角来为您介绍多种优化算法的异同, 以及解决实际问题的一般步骤：建立数学模型-设计算法-编程实现。

前言

运筹学(优化)分支非常庞大, 所谓隔行如隔山, 学者往往对自己所在分支的概念\术语了如指掌,但是同属优化领域, 其他分支的术语就一头雾水. 仍清楚记得第一次参加学术会议, 很sb地问老板, heuristic是什么? 以及组合优化会议上问居里项目ETH同事, PTAS是什么东东?

仅从普及运筹学旗下算法概念和知识点出发，主要以运筹学、数学规划的视角，介绍以上优化算法的异同, 以及解决实际问题的一般步骤：建立数学模型-设计算法-编程实现。

本文扩充自以下回答：（敬请前往查看其他学者的精彩答复，如 @大洪）

遗传算法，模拟退火算法，粒子群算法，神经网络等智能算法的作用？：http://t.cn/RQxINE0

正式回答该问题前，先简介一下运筹学--Operations Research (O.R.), 别名数学规划、最优化理论。此外我称其为人工智能的“引擎”，因为几乎所有人工智能的问题最后都会转化为求解优化问题。五年前流行的支持向量机（SVM，二次规划问题）如此，近两年席卷全球的深度学习（DL）的参数优化（训练）也是（高度复合函数无约束优化问题）。

对于运筹学还不是很了解的朋友，或许下面的文章会有用：

人工智能的“引擎”--运筹学，一门建模、优化、决策的科学：http://t.cn/ROBybx3

启发式算法（Heuristic Algorithm）

启发式算法通常是以问题为导向的（Problem Specific），也就是说，没有一个通用的框架，每个不同的问题通常设计一个不同的启发式算法，通常被用来解组合优化问题。

由于组合优化通常是NP（完全）困难（要求得全局最优解通常需要指数级算法复杂度，不存在多项式时间算法）的，现实应用中需要算法（通常多项式时间算法）来快速得到质量较高的可行解，人们一般会根据特定的问题设计只针对该问题的启发式算法，通常是一种贪婪算法，只能求得局部最优解，也没有跳出局部最优解的有效办法。

元启发算法（Mata-heuristic Algorithm）

和一般的启发式算法不一样，元启发算法针对普遍的问题，是Problem-independent的。可以将他当作一个黑箱子对几乎任何问题使用，通常需要给定初始解。（当然了，不能保证多项式时间收敛，但一般可以控制迭代次数）

一些遗传算法，蚁群算法，进化算法，智能算法，大都属于这个范畴。

个人更倾向于把它们看作一个个基本框架（general framework），在这个框架下，有不同的算法。（通常是基于一定规则的迭代算法）

值得注意的是，它们通常设计了跳出局部最优解的方法，例如蒙特卡洛法，从而可以从第二个点有机会跳到第三个全局最低点。（不能在有限时间内保证收敛到全局最优点）

而0中的启发式算法，如果从第一个点出发，通常收敛到第二个点就停止搜索了。

我所建的全球运筹学者群中对该问题进行了激烈的讨论，感谢英国Cranfield大学 @宋伯阳的见解：算法如果只分两种，就是精确算法和启发算法。所有启发、元启发算法都不是精确算法 (不保证能得到最优解），启发算法和元启发算法最大的区别是，启发算法更多求局部最优，元启发算法设计有克服陷入局部优化的机构，更适合寻求全局最优，比如遗传算法GA有突变Mutation机制。其次，启发算法的设计更多是取决于问题Problem-dependent，元启发算法是独立于问题Problem-independent (可以作为一个black box操作，适用性广，但还是要根据问题调算法各种参数）。元启发算法范围内大部分应用了随机优化机构，多目标优化用的蛮多。但是多目标优化中，目标太多时一般会先降维（比如PCA），多于3-5个目标的优化效率低，也没有太多实际的可读性。接近实际的案例里面一般都会涉及多种算法，先用元启发算法求得一个小范围的满意解，再用启发或者精确算法找最优解，这样即提高了计算效率又能有高质量结果。（算法种类和术语名字太多，看到各种名字很容易晕，其实很多都有相关性（差不多），弄清楚他们之间的关系还是有点重要的）。

近似算法（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是其顶级会议。

数学模型、精确算法(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%的成本可能已经是几百甚至上千万的差别！！！

更多介绍：

混合整数规划/离散优化的精确算法--分支定界法及优化求解器

神经网络(Neural Network)

神经网络，包括CNN（深度学习的底层模型），是一个模型/框架，而不是算法，通常限于求解分类问题（Classification Problem）。个人倾向于把CNN看作进化版的元启发模型（当然有监督这一点是其他元启发所不具备的），可以把它当作黑箱子直接拿来用。

其目标函数是一个高度复合的无约束的函数，而训练参数的过程（算法），通常使用方向传播法，可以把它理解为一种特殊的梯度下降法。

CNN里面，有Relu和Dropout，前者是为了提高函数的非线性性，后者为了简化函数参数的训练。

这个高度复合的函数是一个极度非凸函数（请点下一个链接学习基本概念），很难求解全局最优解，但是貌似有理论证明（或是大量实验表明？），反向传播法求得的CNN的局部最优解，通常已经是一个非常好的解（并且存在大量类似高质量的局部最优解，因此随便找到哪一个都是不错的结果）。

离散/整数/组合/非凸优化概述及其在AI的应用

从数学规划的角度，一个没有约束条件的优化问题，比有约束的优化问题（如线性规划）容易求解很多。

因此从这个意义上讲，运筹学比起神经网络可以解的问题更general，问题更难。

但是，CNN虽然没有约束条件，但是难度在于目标函数极度非凸，以及变量的数量极其庞大！

多种模型解分类问题（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

后记

人工智能、运筹学的交叉愈演愈烈，运筹学、优化的国际盛会，AI已逐渐成为运筹学者们热议的话题，并且AI的讲座通常都是爆满状态。

运筹学、数学规划、优化--国际协会、奖项、会议大搜罗

而深度学习这个黑箱子，也亟待深层次优化理论的进一步“洗礼”。

最近因为AlphaGo，AlphaZero火起来的增强学习（也被称为近似动态规划），也会给运筹学、算法学界带来更多的思考。（今天没有提到动态规划算法，希望相关学者踊跃投稿～）

科学因为各个学科深度交叉而快速发展，跨界势在必行。

文末，借用亚琛工大运筹学教授Marco 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