运筹学--Operations Research (O.R.)，有时也称为数学规划、最优化理论，是人工智能的“引擎”，因为几乎所有人工智能的问题最后都会转化为求解优化问题。几年前流行的支持向量机（SVM，二次规划问题）如此，近几年席卷全球的深度学习（DL）的参数优化（训练）也是（高度复合函数无约束优化问题）。现今在社会经济管理、生命科学领域中，决策环境越来越复杂，众多因素有着错综复杂的相互作用，复杂的决策过程致使建立模型的难度越来越高，决策变量的量级、取值、目标的复杂多样、约束的非线性成程度都是经典优化算法难以求解的，这样启发式算法就应运而生。启发式算法通常是以问题为导向的（Problem Specific），也就是说，没有一个通用的框架，每个不同的问题通常设计一个不同的启发式算法，由于这些问题都是NP-Hard（要求得全局最优解通常需要指数级算法复杂度，不存在多项式时间算法）的，人们一般会根据特定的问题设计只针对该问题的启发式算法。
一、精确算法与启发式算法
精确算法：找到最优解并评估最优性，有严格的最优化数学理论支撑。到目前为止，已提出的精确算法种类较多，有单纯形法、分支定界法、割平面法、整数规划算法和动态规划算法等。一般可用软件为MATLAB，LINGO，Python等。(Exact optimization method> s (Jourdan et al, 2009): ‘Exact methods find the optimal solution and assess its optimality’.)
启发式算法（heuristic algorithm)：在问题结构不良的情况下，为得到近似可用的解，分析人员必须运用自己的感知和洞察力，从与其有关而较基本的模型及算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径，这种方法称为启发式方法。由此建立的算法称为启发式算法，可为复杂的优化问题快速生成近似最优解，许多启发式算法是相当特殊的，依赖于某个特定问题。启发式策略在一个寻求最优解的过程中能够根据个体或者全局的经验来改变其搜索路径，当寻求问题的最优解变得不可能或者很难完成时，启发式策略就是一个高效的获得可行解的办法。
启发式算法一般用于解决NP-hard问题，其中NP是指非确定性多项式。因为传统算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但对于NP问题，传统算法花费几乎无穷的时间和算力才能求得答案。而启发式方法则限制了搜索空间，大大减少尝试的数量，能迅速地达到问题的解决。但由于这种方法具有尝试错误的特点，所以也有失败的可能性。
举一个通俗易懂的例子：
驾驶汽车到达某人的家，写成算法是这样的：沿167 号高速公路往南行至Puyallup；从South Hill Mall 出口出来后往山上开 4.5 英里； 在一个杂物店旁边的红绿灯路口右转，接着在第一个路口左转；从左边褐色大房子的车道进去，就是North Cedar 路714 号。
用启发式方法来描述则可能是这样：找出上一次我们寄给你的信，照着信上面的寄出地址开车到这个镇；到了之后你问一下我们的房子在哪里。 这里每个人都认识我们——肯定有人会很愿意帮助你的；如果你找不到人，那就找个公共电话亭给我们打电话，我们会出来接你。
1.1 数学最优化模型的结构
一般而言，算法所需要解决的问题，都能分成三个部分：
目标：什么是目标呢？简单点说就是要优化的东西，比如在上述背包问题中，要优化的就是所选物品的价值，使其最大。
决策：顾名思义就是根据目标所作出的决策，比如在这里就是决定选取哪些物品装进我们的背包。
约束：那么何又为约束呢？就是说再进行决策时必须遵循的条件，比如上面的背包问题，我们所选取的物品总的重量不能超过背包的容量。要是没有容量的约束，小学生才做选择呢，我全都要！
1.2 启发式算法特点
启发式算法一般用于解决NP-hard问题，例如，著名的推销员旅行问题（Travel Saleman Problem or TSP）：假设一个推销员需要从南京出发，经过广州，北京，上海，…，等 n 个城市， 最后返回香港。 任意两个城市之间都有飞机直达，但票价不等。假设公司只给报销 C 元钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 C？推销员旅行问题显然是 NP 的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于 C 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排。
启发式算法的基本特点： 复杂度不确定，但是在实际中往往也能得到一个比较好的效果. （1）随机初始可行解； （２）给定一个评价函数（常常与目标函数值有关）； （３）邻域，产生新的可行解； （４）选择和接受解得准则； （５）终止准则。 其中（４）集中反映了超启发式算法的克服局部最优的能力。
启发式算法目前缺乏统一、完整的理论体系，启发式算法的提出就是根据经验提出，没有什么坚实的理论基础。启发式算法中的参数对算法的效果起着至关重要的作用，如何有效设置参数是经验活但还要悟性，只有try again。启发算法缺乏有效的迭代停止条件。还是经验，迭代次数100不行，就200，还不行就1000，启发式算法收敛速度的研究等。应用启发式算法，你就知道没有完美的东西，要快你就要付出代价，就是越快你得到的解也就越差。启发式算法中，不能保证找到最佳解决方案，局部最优值的陷入无法避免。启发式本质上是一种贪心策略，这也在客观上决定了不符合贪心规则的更好（或者最优）解会错过。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案。
二、启发式算法的发展
启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，取得了巨大的成就。40年代：由于实际需要，人们已经提出了一些解决实际问题快速有效的启发式算法。50年代：启发式算法的研究逐步繁荣起来。随后，人们将启发式算法的思想和人工智能领域中的各种有关问题的求解的收缩方法相结合，提出了许多启发式的搜索算法。其中贪婪算法和局部搜索等到人们的关注。60年代: 随着人们对数学模型和优化算法的研究越来越重视，发现以前提出的启发式算法速度很快，但是解得质量不能保证。虽然对优化算法的研究取得了很大的进展，但是较大规模的问题仍然无能为力（计算量还是太大）。70年代：计算复杂性理论的提出。NP完全理论告诉我们，许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，得到的解不能保证全局最优性。由此必须引入新的搜索机制和策略，才能有效地解决这些困难问题，这就导致了超启发式算法（meta-heuristic algorithms）的产生。
Holland模拟地球上生物进化规律提出了遗传算法（Genetic Algorithm），它的与众不同的搜索机制引起了人们再次引发了人们研究启发式算法的兴趣，从而掀起了研究启发式算法的热潮。80年代以后： 模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。最近，演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms）， 拟人拟物算法，量子算法等油相继兴起，掀起了研究启发式算法的高潮。由于这些算法简单和有效，而且具有某种智能，因而成为科学计算和人类之间的桥梁。在一些寻找最优解问题中，传统的能够求出最优解的精确式算法（如分支界定、动态规划等）花费的时空过大。启发式算法（heuristic algorithm）是一种能以更快速度找出问题近似最优解的方法。启发式算法通过牺牲一些精度来换取较小的时空消耗，可以看作是解决问题的捷径。
三、常用的启发式算法
启发式算法的主要思想来自于人类经过长期对物理、生物、社会的自然现象仔细的观察和实践，以及对这些自然现象的深刻理解，逐步向大自然学习，模仿其中的自然现象的运行机制而得到的。
遗传算法(GA)：
遗传算法（Genetic Algorithm, GA）起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解。
模拟退火算法(Simulated Annealing, SA)：
模拟退火算法的思想借鉴于固体的退火原理，当固体的温度很高的时候，内能比较大，固体的内部粒子处于快速无序运动，当温度慢慢降低的过程中，固体的内能减小，粒子的慢慢趋于有序，最终，当固体处于常温时，内能达到最小，此时，粒子最为稳定。模拟退火算法便是基于这样的原理设计而成。
蚁群算法(AG)：
蚁群算法是一种模拟蚂蚁觅食行为的模拟优化算法，它是由意大利学者Dorigo M等人于1991年首先提出，并首先使用在解决TSP（旅行商问题）上。 之后，又系统研究了蚁群算法的基本原理和数学模型.
粒子群优化算法（Particle Swarm Optimization, PSO）：
粒子群优化算法是一种基于鸟类觅食提出来的进化计算技术，由电气工程师Eberhart博士和美国社会心理学家Kennedy博士发明，是一种基于迭代的优化工具。该算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。由于没有遗传算法的交叉、变异，粒子群算法更容易实现
禁忌搜索算法TS（Tabu Search）
禁忌搜索由美国科罗拉多州大学的Fred Glover教授在1986年左右提出来的，是一个用来跳出局部最优的搜寻方法。 禁忌搜索是一种亚启发式随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向。
这几种启发式算法都有一个共同的特点：从随机的可行初始解出发，才用迭代改进的策略，去逼近问题的最优解。
总结
在问题结构不良的情况下,为得到近似可用的解,分析人员必须运用自己的感知和洞察力,从与其有关而较基本的模型及算法中寻求其间的联系,从中得到启发,去发现适于解决该问题的思路和途径,这种方法称为启发式方法,由此建立的算法称为启发式算法。优点:(1)计算步骤简单,要求的理论基础不高,可由未经过高级训练的人员实现;(2)比优化方法常可减少大量的计算工作量,从而显著节约开支和时间;(3)易于将定量和定性分析相结合。不足:(1)不能保证求的最优解。(2)表现不稳定,启发式算法在同一问题的不同实例计算中会有不同的效果,有些很好,而有些则很差。在实际应用中,这种不稳定性造成计算结果不可信,可能造成管理的混乱。(3)算法的好坏依赖于实际问题,算法设计者的经验和技术,这点很难总结规律,同时使不同算法之间难以比较。