基于学习的运筹优化算法进展与发展趋势（一）：优化观点、常见优化方法和概念澄清-英雄云拓展知识分享

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

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

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 启发算法分类

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

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

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

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

文献【2】对此作了以下对照和分析：

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

  通常适应当前的问题，并试

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

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

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

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

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

• 总结

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

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