组合优化的研究趋势

因此，如今一家典型跨国制造公司的全球生产网络包括遍布全球的工厂，每个工厂都面临着越来越大的压力，需要协调彼此之间以及与供应链其他部分的运营（Ferdows et al.，2016）。生产应用领域的CO研究也有相对较高的平均发表年份（2011.1），这表明该领域对新问题解决方案的需求日益增加。数据的研究领域与信息相关，这两个应用领域主要集中在数据挖掘（例如Brandner et al.（2013））或信息理论（例如Braun et al.（2017））上。这些领域需要新的方法，因为近几十年来大量的数据已经超过了处理、分析、存储和理解数据集的能力。一个很好的例子是，仅在1998年到2008年间，网页的数量就从100万增加到了1万亿（Fan and Bifet，2013）。与之相关的数据挖掘技术使用的增加也对信息应用领域产生了直接影响：例如，越来越多的隐私保护数据挖掘方法旨在保护个人的敏感信息（Xu等人，2014）。大数据还与能源部门有关，能源部门越来越多地使用智能仪表（智能电网中的传感器和测量设备）来收集实时用电量数据，以便更好地预测和转移电力负荷（Wen等人，2018年）。能源行业相关问题通常是NP难问题（Goderbauer et al.2019），似乎是CO出版物中最常见的主题，其关键词为power和Energy。电力主题主要是关于上述智能电网（例如Meskina et al.（2018））的应用或最优潮流（例如：。

阿比多（2002））计算。能源领域的相关主题包括能源效率（如Alharbi等人（2019））和能源消耗（如Weinand等人（2019））。在能源系统转型以减少人为温室气体排放的过程中，这些问题变得越来越重要。应用领域能源的平均发布年份（2011.7）也反映了这一点，这是12个确定的应用领域中最实际的一个（参见在线附录中的表3）。由于上述工业生产的发展，温室气体排放量进一步增加，因此能源研究也越来越多地与生产应用领域联系在一起。由于不断改进的技术和公司越来越多地试图使其生产计划节能，排放量不会线性增加。从公司的角度来看，造成这种情况的一些原因是政策/立法、资源稀缺、能源价格上涨和环境意识增强（贝尔和格洛克，2016）。100多篇合作文章中涉及的最后两个主要应用领域是管理和许多供应链管理研究（如Mohammadi Bidhandi等人（2009））以及决策，主要研究决策支持系统（如Haastrup等人（1998））。供应链管理研究显然与生产紧密相关，每个应用领域实际上都需要决策支持。分析表明了合作方法的重要性，这种方法被应用于许多不同的领域，并被用于解决当前的许多全球性问题。此外，值得注意的是，在许多应用领域，遗传算法主要用于解决潜在问题。

这种元启发式已经证明在CO领域最为相关（参见第3.4.2节）。此外，这一单词分析还证实了稳健优化是当前CO最突出主题的假设，因为稳健和不确定性这两个密切相关的术语分别显示了2013.8年和2013.3年的最高平均出版年份（参见在线附录中的表18-3）。不确定性的考虑也越来越与上述实际应用领域相关，如生产规划（例如产品的不均匀性（Mundi等人，2019））或能源系统分析（例如可再生能源的随机性和未知的未来全球能源和经济前景（Mavromatidis等人，2018））。4.在本节的讨论中，结果反映了研究领域的挑战和前景，分为（元）启发式（参见第4.1节）和精确算法（参见第4.2节）。此外，第4.3节讨论了本研究的局限性。4.1.  （元）启发法的挑战和前景本文数据得出的一个总体结论是，在协同领域的大多数论文仍然是“问题算法结果”类型。在这些论文中，针对一个特定的协同问题开发并测试了一个算法，在大多数情况下，通过与针对同一问题的其他算法进行比较，证明该算法性能良好。几位作者（Barr等人，1995年；Hooker，1995年；Kendall等人，2016年）警告说，这种类型的研究，尤其是竞争性测试方面，除了轶事之外，产生的科学知识非常少。它将大量的研究时间浪费在实现一流性能所需的“开发”活动（抛光代码、编译器调优等）上。

试图就启发式和超启发式得出一些可概括结论的论文已经存在（例如Santini等人（2018年）或Watson等人（2003年）），但仍然代表着一种边缘现象。根据竞争性测试（被称为“赛马”）决定发表哪些论文的做法也导致了相当大的发表偏见。文献中出现了主要的积极结果（算法X对问题Y很有效），而表明某些类型的启发式对某些问题（类别）不起作用的消极结果很少（尽管存在一些，例如S"orensen和Schittekat（2013））。再加上很少有被普遍接受的算法结果测试和报告协议，大多数学术期刊甚至不需要简单的统计测试来证明“更好的性能”在统计意义上是重要的。这让人想知道，文献中发表的许多结果在多大程度上经得起独立复制和测试的审查（例如，参见S"orensen等人（2019年）的一个例子，其中独立复制无法证实作者最初的性能主张）。另一个观察结果是，基于隐喻的元启发式（也称为“自然启发的”元启发式，尽管这类元启发式的灵感现在来自与自然关系不大的来源）和不基于某种隐喻的更传统的元启发式之间似乎存在着越来越大的分歧。

在基于隐喻的元启发式领域，关于算法想法是否有价值的决定似乎取决于启发它的隐喻的新颖性，提出了越来越离奇的隐喻（室内装饰（甘多米，2014年）、国际足联世界杯（拉兹穆伊等，2016年）、“智能”水滴（侯赛尼，2009年），而且，在一个壮观的机会主义的演示中，CoVID-19（Maldi-Nez—LVaRez等人，2020）损坏了。在不暗示传统元启发式领域没有问题的情况下，我们只能得出结论，基于隐喻的元启发式子领域的科学标准特别低。作为一个例子，值得注意的是，该领域最受欢迎的论文之一是介绍和声搜索算法的论文（Geem等人，2001年）（参见第3.3节）。这种元启发式假设是基于音乐家一起演奏音乐（例如，和声搜索行话中的解决方案被称为“旋律”），尽管这种算法已被明确证明（Weyland，2010，2015）是进化策略的一个特例，这种元启发式比进化策略早30年。社区项目“大范围内的元启发式”（MitL）最近制定了一个框架，支持元启发式的组合组装和比较，从而也解决了再现性和可伸缩性问题（Swan等人，2020年）。从本文的文献计量结果中可能很难收集到的另一个趋势是，人们越来越关注“丰富”问题（即涉及许多特定约束和目标的复杂公式的问题），这些问题通常基于实际应用。

毫无疑问，启发式和元启发式思想已经渗透到为现实生活优化开发软件的实践者的思维模式中，而且，（元）启发式研究正在越来越多地找到其实际应用的途径。例如，PTV和ORTEC等（软件）公司越来越多地参与会议，并为研究人员解决实际问题提出挑战（Kheiri等人，2019年）。最后，（元）启发式领域的研究人员正越来越多地接触相关领域，结合想法和技术开发更好的优化算法。启发式与精确方法（通常称为“数学理论”）的结合已经发展成为一个自己的领域。约束编程和机器学习的结合也越来越多地被发现。有关此类组合的简要回顾，请参阅（Talbi，2016）。4.2.  精确算法的挑战与展望根据本文报告的数据，关于精确协算法出版物的主要关键词是分枝定界和整数规划。同样从数据来看，与精确算法相关的出版物数量远远少于与近似算法相关的出版物数量。其中一个原因是，许多具有实际意义的硬组合问题都是NP难问题，只有近似方法才能提供好的解。然而，最近描述了NP难问题的精确算法，这些算法能够解决具有数百万个节点的真实网络实例，以证明其最优性（例如，San Segundo等人（2016年）或Walteros and Buchanan（2020年））。关于精确协同算法的出版物数量相对较少的另一个解释可能在于论文中已经提到的“问题算法结果”结构。

通常，这项工作侧重于研究问题实例的特定结构，并开发专门的新算法，然后将其与当前最先进的方法进行广泛比较。只有显示出重要意义的算法感兴趣的读者才会参考“EC Bestiary”，这是一本讽刺性的汇编，汇集了所有在文献中发表的以隐喻为灵感的元启发式算法（Campelo和Aranha，2019）。20与最新技术相比的改进将发表在顶级联合期刊上。此外，有人认为，还应证明精确算法，即提供易于验证的证明，证明解决方案是正确的（Gocht等人，2020年）。尽管如此，这一“问题-算法-结果”研究流对一些基本的NP-hard/NP完全问题，如最大独立集问题和布尔可满足性（SAT）问题，已经显示出一些令人兴奋的改进。特别是在过去20年中，算法方法的进步至少与硬件的进步产生了相同的影响（Fichte等人，2020年）。此外，对特定NP完全问题的研究也导致了对问题之间有效转换的研究。在最近成功转换的许多例子中，可以指出最先进的约束编程求解器的SAT模块（例如，Zhou等人（2015））以及最先进的最大团求解器使用的基于SAT的边界函数（Li等人，2018）。与新的精确算法技术的发展相辅相成的是定期组织的众多共同挑战，如XCSP3、PACE、DIMACS和SAT竞赛，在这些竞赛中，算法与实际兴趣的基准进行比较，并解决最先进的问题。

从现有数据来看，还值得一提的是，研究旨在通过利用结构特性减少问题实例，从而加快精确协算法收敛速度的方法。这些技术只能在被称为核化的预处理阶段应用一次。或者，它们可以应用于分支树的每个节点，表示分支和reduce范式。这两种技术最近都有助于解决一些硬组合大规模问题实例（Akiba和Iwata，2016；Hespe等人，2020）。未来对能够解决大规模现实问题的精确协同算法的研究肯定会随着时间的推移而继续。新的算法分支和定界以及分支和缩减技术将带来令人兴奋的发展，但人们也可能期待新的算法框架，其中最近的车辆路径和其他相关问题的分支切割和奖励框架就是很好的例子（Pessoa等人，2020）。由于这些挑战和前景主要涉及第3节的结果，其他新出现的问题可能会被忽视。一个例子是基于机器学习的方法，它通过以更具原则性和优化的方式做出手工专家基于知识的启发式决策，在不同的应用中显示出有希望的结果（Bengio et al.，2020）。例如，在最初的AlphaGo论文（Silver et al.，2016）中，机器学习算法首先基于专家知识进行训练，然后通过使用自我游戏（强化学习）中的奖励信号进一步完善。一般来说，机器学习用于精确和启发式框架（Bengio等人，2020年）。4.3.

本研究的局限性与所有综述研究一样，本文献计量分析中的主题评估取决于搜索查询的类型。最有可能的是，大量的研究涵盖了协同问题，但没有将组合优化作为关键词，也没有在标题、摘要或文章中使用。如果这些出版物也未通过科学网的KeywordPlus分配给CO，则不包括在本分析中。因此，无法给出100%全面的CO图21。另一方面，目的是分析明确将合作作为一种方法论的研究，并假设分析的文献语料库会产生合作研究领域的代表性样本。此外，有些方法使用或多或少任意设置的参数，不同的参数可能会产生不同的结果。例如趋势分析中的年数，或为Levenshtein距离设置的最大距离。在分组过程中，不可能使用Levenshtein距离等距离来识别所有相关关键字，因为这总是涉及一些解释。例如，图5显示了关键字旅行推销员问题，它被使用了225次。然而，旅行（384）和推销员（349）这两个词的出现率较高（参见在线附录中的表3），这表明旅行推销员问题包含在超过225篇文章中。然而，如果使用了明显不同的关键字，并非所有文章都可以通过一种算法进行分组。例如，与模拟退火不同，大邻域搜索也被称为破坏与修复、破坏与重建，但自动分析不会（也不能）将这些概念分组。因此，第3.4节中的关键词分析只能理解为趋势的指示。5.

摘要与结论越来越多的现实问题变得非常复杂，必须用组合优化技术来解决，这一直是科学界非常感兴趣的问题。因此，1990年至2019年间，关于组合优化的出版物数量呈指数增长，在本次分析时达到8393份。这需要对文献进行研究，以展示组合优化研究的现状和趋势。因此，本研究使用了文献数据库Web of Science、R-tool Biblometrix以及为关键词分析开发的新算法支持的文献计量分析。在85个投稿国中，美国是最重要的投稿国，发表了1918篇文章，h指数最高（104篇），其次是中国（1197篇文章），自2014年以来年度发表量最高，以及法国（676篇文章）。总的来说，关于组合优化研究的合作出版物的份额相当低，美国和中国之间的合作最多（146）。最具生产力的组织是法国国家科学研究中心（235篇），加利福尼亚大学系统，有162篇文章以及最高的H指数（37）和中国科学院（118篇）。由于跨国合作的比例很低，来自同一国家的组织倾向于合作，蒙特利尔大学和蒙特利尔理工学院记录了学院间合作的最高数量（42）。组合优化的核心来源是《欧洲运筹学杂志》、《计算机科学和计算机与运筹学》的课堂讲稿，该杂志发表了8393篇文章中的15%左右。