基于学习的运筹优化算法进展与发展趋势（一）：优化观点、常见优化方法和概念澄清

1. 运筹优化问题相关背景

运筹学主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。运筹优化算法在日常生活和生产实践中具有广泛的应用，随着过去十多年来物联网、5G、人工智能、数字孪生等科技的爆发性发展带来了算力和算法的巨大进步，传统制造业、物流和工业的数字化发展又带来了海量的数据，三者的日益融合逐渐形成了以“数据+算力+算法”为核心的智能制造技术体系，其中运筹优化算法是作为这个技术体系的核心，数据的价值最终通过运筹优化算法体现（如降本增效）。另外，运筹优化算法在社交、娱乐、教育、交通、安防、工业、物流、电商等众多行业和领域中扮演了不可或缺和无法替代的角色。

2. 运筹算法设计的相关思想和观点

由于实际的生产和决策系统的大部分问题都是多目标的组合优化问题（也是NP难问题）或非凸优化问题，根据计算复杂性理论，无法在预期时间内得到最优解，因此大部门是实际使用的运筹优化算法主要是近似算法，常用的为启发式算法。其中启发式算法主要有两大类，一是基于数学规划的启发式算法，另一个是元启发式算法。针对优化问题，常见有如下观点：

• 单目标优化问题的难度分界线不是线性和非线性，而是凸与非凸，本质上就是P或者NP难。

   优化问题最终需要一个算法来解决，但涉及到算法时需要衡量算法的复杂度。 

   通俗的讲，目前大多数优化算法解决的是凸问题（多项式时间范围找到全局最优解），而大部分非凸问题是NP难的（寻找全局最优解是NP难的）。当然，问题规模较小的时候两者区别不大。 

•  没有一劳永逸地解决所有问题的终极算法，即没有免费的午餐（NFL，No Free Lunch）。 

  基于问题的特化（specialty）研究：当问题领域信息可用时，如何利用问题相关知识设计高效的搜索算法或求解策略。

  基于算法的泛化（generality）研究：如何设计通用方法的泛化策略，以满足异构实力与跨领域问题求解的需求。 

• 大规模优化问题的求解算法和策略是分层的，More is different。

  大规模不同尺度的问题是用分层策略来求解的，大部门都是分而治之的策略。 

   每个层级考虑的问题特性不一样，例如底层的简单搜索规则，高层的搜索策略。

  合理的分层策略是算法成功的关键。 

• 优化计算目的不是数字（numbers），而是背后的洞察（insights）。 

  找到一个好的结果不靠碰运气（随机搜索），而是背后的思想来指导（有目的搜索），这样才能持续改进。

  找到一个差不多的优化算法很容易，但找到一个好的算法却很难。

3. 运筹优化问题和算法类型

优化方法按照变量的特点划分，可以分为连续优化和离散优化，其中连续优化一般称作为非线性规划，核心的难点在于凸或者非凸，相关理论和算法研究得已经很深入，尤其随着深度学习的火爆，吸引了大量的优化学者的加入和研究。离散优化常见的优化问题为组合优化问题，无通用的算法和求解策略，因此此类问题研究难度较大，算法复杂度较高，难以较好的掌握相关算法的精髓和基本思想。因此，我们以组合优化算法为切入点，介绍基于学习的运筹优化算法，相关思想可以同样用于连续优化问题里面。

从问题角度来看，组合优化代表性的优化问题长分为操作优化（operation optimization）和过程优化（process optimization），特点如下：

• 操作优化问题一般是组合优化问题，大多是离散变量。常见调度、计划、分配等场景。

•  过程优化问题一般是非线性规划问题，大多是连续变量。常见于化工过程、电网、流体力学等场景。

•  由于过程优化问题更行业背景知识关联较深，实际中还涉及到大量数据建模，本质上是行业知识和经验的建模和优化，门槛交过。因此我们研究聚焦于组合优化问题，易于建模和分析，难度瓶颈在于高质量的算法。

组合优化问题的常见求解算法是基于元启发式的和基于数学规划的运筹优化算法框架，策略如下：

由于组合优化问题再实际问题里面基本都是大规模的，求解时间和求解质量必须有个平衡和折中，文献【1】对此作了一个概要上的分析，具体如下：

优化模型的常见分类如下：

常见的优化方法分类如下：

4. 启发式算法类型

4.1 启发算法分类

启发式算法是优化算法中常见的算法，具体的含义如下：一个基于直观或经验构造的算法，在可接受的花费 (指计算时间、占用空间等) 下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计。值得说明的是，启发式算法是相对于最优算法提出的，一个问题的最优算法是指求得该问题每个实例的最优解。

启发式算法简单的划分为如下三类：简单启发式算法 、元启发式算法和超启发式算法 (Hyper-Heuristic Algorithms)。

• 元启发式算法（Meta-Heuristic Algorithm）：是启发式算法的改进，它是随机算法与局部搜索算法相结合的产物。元启发式是一个迭代生成过程，通过对不同概念的智能组合，该过程以启发式算法实现对搜索空间的探索和开发。

• 超启发式算法：提供了一种高层次启发式方法，通过管理或操纵一系列低层次启发式算法 (Low-Level Heuristics，LLH)，以产生新的启发式算法。这些新启发式算法被用于求解各类组合优化问题。

文献【2】对此作了如下对比和分析：

• 启发式算法：依赖于问题的技术。

  通常适应当前的问题，并试图充分利用这一问题的特殊性。由于它们往往过于贪婪，它们通常陷入局部最优状态。

• 元启发式算法：独立于问题的技术。

  没有利用问题的任何特殊性，因此可用作黑匣子。一般来说，他们并不贪婪，甚至可能接受某个具体问题中解的暂时恶化(例如，模拟退火技术)，这使他们能够更彻底地探索解的空间。尽管元启发式算法是一种独立于问题的技术，但仍有必要对其内在参数进行一些微调，以便使该技术适应手头的问题。

• 超启发式算法：启发式或元启发式的空间

  不同于以上两者算法的对象，上两者的对象其实都是针对问题找解，只是启发式算法针对特殊问题找出较优解，而元启发式对普遍问题，不加入任何特殊条件找出通解空间。

  特殊性在于它找出的空间不是解的空间，而是启发式或元启发式的空间，可以被看作是“启发式搜索启发式”。

• 总结

   三者之间对象不同，搜索得出的空间也不同，启发式算法搜索得出的是特殊解空间，元启发式算法搜索得出的是普遍问题的解空间，而超启发式算法搜索得出的是启发式的空间。

4.2 元启发式算法谱系

现有的元启发式顺丰种类极其繁多，文献【1】对经典的元启发式算法做了简单谱系分析，具体如下：

其中各种缩写含义如下：ACO (ant colonies optimization) 、AIS (artificial immune systems)、BC(bee colony) 、CA(cultural algorithms)、CEA (coevolutionary algorithms) 、CMA-ES (covariance matrix adaptation evolution strategy) 、DE (differential evolution)、EDA (estimation of distribution algorithms)、EP (evolutionary programming)、ES (evolution strategies)、GA (genetic algorithms)、GDA (great deluge)、GLS (guided local search) 、GP (genetic programming)、GRASP (greedy adaptive search procedure)、ILS (iterated local search)、NM (noisy method)、PSO (particle swarm optimization)、SA (simulated annealing)、SM (smoothing method)、SS (scatter search)、TA (threshold accepting)、TS (tabu search)、VNS (variable neighborhood search)。

4.3 超启发式算法

超启发式算法特点：

•  超启发式算法提供了一种高层次的启发式方法，它操纵管理一组LLH；

• 超启发式算法的目标是寻找一个好的启发式算法；

•  超启发式算法仅使用有限的领域相关信息（理想情况下，这些信息仅包括LLH数量、待求解问题的目标函数等）。

超启发式算法的概念模型如下（可参考文献【2】）：

5. 运筹优化算法（启发式算法）的整体求解流程

文献【1】给出了一般意义下的优化问题的求解流程：

核心的思想和想法如下：

• 元启发式算法（或其他优化算法）尽可能简单，但不要太简单。

• 简单的方法有如下好处：

     易于理解

     易于编码

     易于迁移到工业界

     易于扩展和改进

6. 对元启发式算法研究现状的一些批判性观点

Ruben Ruiz（文献【3】）对当今运筹优化领域的元启发式算法的研究现状提出了一些一针见血的评价和看法，值得令人深思和注意。核心的几个批判如下：

•  Many wild ideas (>130 “unique” entries):

    Lion algorithm

    Flower pollination

    Lizards

    Grey Wolf optimization

    Electromagnetic Field Optimization

    Reincarnation

    Sperm Motility Optimization

    Even Zombies!!!!

• Many of these bizarre methods get cited a lot

    Being the first to apply the method X to the problem Y

    Easy to improve the basic method X by adding operators or hybridizing

    In a little while the method X gets many citations and then everybody thinks that it is good because of that

    Easy to publish: There are more than 50,000 scientific journals in the world and more than 50 million papers published throughout history

• Peas-to-Melons comparisons

    Focusing only on solution quality, not considering (to some extent) CPU time

    Metaheuristics use resources (CPU time, memory) to give a solution

    Not carefully controlling CPU time in the comparisons leads to fallacies that are misleading (part) of the scientific community

• Comparisons often against published tables with results obtained years ago:

    Different processors (older)

    Memory speed, bus speed (older)

    Different compilers (older)

    Different programming languages

    Different operating systems

    Different coding skills

    Different stopping criteria

    These factors add-up!

【参考文献】

[1].   2009 Meta-heuristic - From design to implementation

[2].   2011 超启发算法， 跨领域的问题求解模式

[3].   Iterated Greedy, Rubén Ruiz –November 2018