组合优化的研究趋势

根据问题选择合适解决方案的启发式方法。另外两份出版物在内容上有着密切的联系。S"orensen（2015）讨论了一个事实，即近年来发展了许多超启发式方法，这些方法主要基于关于自然或人为过程的隐喻，例如蚂蚁或蜂群优化。作者认为，除了一些高质量的创新研究外，许多论文的发表都是基于一个事实，即发达的元启发式方法是基于新颖的隐喻。Blum et al.（2011）还通过以下事实推动了他们对混合元启发式的研究：过去对协同问题的元启发式的研究主要是面向算法的。然而，作者们看到了一种趋势，即协元启发式的研究重点正在从这种面向算法的方向转移到面向问题的方向。因此，为了找到解决问题的最佳方法，元启发式现在经常与其他优化技术相结合。

表6：关于组合优化的科学贡献中的文章，自2010年以来年度引用率最高。文章标题全球引文发布年份来源No。每年，一种使用优化LS-SVM和改进PSO算法的新型智能诊断方法（邓等人，2019年）软计算新无机固态LED荧光粉的最新发展（夏等人，2016年）道尔顿交易人工自旋量子退火（约翰逊等人，2011年）自然超启发式：最新技术的调查（伯克等人，2013年）运营管理杂志Research SocietyMetaheuristics暴露的隐喻（S"orensen，2015）运筹学中的国际交易一种有效的分布式粒子群优化算法，用于灵活的车间调度问题（Nouiri等人，2018）智能制造期刊生物启发自适应网络设计规则（Tero等人，2010）科学模块优化大肠杆菌中脂肪酸产生的多基因途径（Xu等人，2013）自然交流组合优化中的混合超启发式：一项调查（Blum等人，2011）应用软计算一种可行的正交约束优化方法（Wen和Yin，2013）数学编程如前所述，Dorigo等人（1996年）的文章在本文研究的文章中被全球引用最多（5646篇），也经常被8393项研究引用（235篇）。然而，8393篇文章更频繁地引用了五项研究（参见表7）。本地引用最多的研究的重点是识别和处理NP完全（组合优化）问题，即可以在非确定性图灵机上用多项式时间解决的问题（Garey and Johnson，ca.2009）。

表7中的其他三份出版物介绍了新的元启发式（模拟退火（Kirkpatrick等人，1983年13日）和禁忌搜索（Glover，1989年））或元启发式的回顾（遗传算法（Goldberg，2012年））。这三种超启发式方法也是8393项CO研究中最常用的方法（参见第3.4节）。表7：关于组合优化的文章中最常引用的五篇参考文献。文章标题局部引文开放年计算机与难处理性：NP完全性理论指南（Garey and Johnson，ca.2009）数学科学中的一系列书籍模拟退火优化（Kirkpatrick et al.，1983）科学遗传算法搜索、优化，和机器学习（Goldberg，2012）禁忌搜索第一部分（Glover，1989）ORSA期刊关于计算优化问题中决策的“神经”计算（Hopfield and Tank，1985）生物控制论3。4.本节中的大多数相关主题，首先评估基于Levenshtein距离的算法（参见第3.4.1节）。其次，第3.4.2节显示了CO研究领域中最相关的关键词和主题。然后，第3.4.3节试图确定CO.3.4.1最相关的应用领域。关键词算法的评估与R-tool bibliometrix的web界面biblioshiny相比，开发的算法能够更好地识别相关关键词。例如，现在可以组合使用带或不带连字符、单数或复数的不同拼写。关键词组合优化就是一个例子，它在文章中出现的次数最多，为3.051次。

为该关键字分组的不同拼写如下，与第一个关键字相比，拼写的变化以粗体显示：组合优化、组合优化、组合优化、组合优化、组合优化和组合优化。因此，关键字组合优化的出现率可以提高7%（参见图4）。对于图4所示的七个最相关的关键字，关键字遗传算法取得了最大的改进：这里的识别率提高了99%。然而，也有一些例子似乎总是以同样的方式陈述：对于模拟退火，开发的算法没有产生任何改进。图4：一方面与R-tool Biblometrix确定的最相关关键词的外观进行比较，另一方面与为本研究开发的新算法进行比较。26230035031022917925323022555214354193102722582572342250100200300400500600组合优化遗传算法元启发式模拟神经网络优化近似算法禁忌搜索局部搜索整数编程外观关键字bibliometrix自身算法new~~~~~28553051+7%+99%+45%+20%+0%+2%+2%+0%+19%+44%14 3.4.2。组合优化问题和解决方法本节讨论了至少1%的出版物中出现的有关CO的最相关关键字。如第3.4.1节所示，关键词组合优化出现频率最高（3051份出版物）。这并不奇怪，因为这个关键词对应于本次文献计量分析的整体主题，因此也是科学网的搜索查询。因此，在下面的分析中排除了关键字组合优化。

因此，前五个相关关键词是遗传算法（521次）、元启发式（435次）、启发式（419次）、模拟退火（310次）和优化（272次）。这些关键词的年出现率波动，但总体上有增加的趋势（模拟退火除外，参见图2d）。低平均出版年份（2005.7，参考图5）进一步证明了模拟退火在实际联合出版物中的使用频率较低。在图5中，出现在至少1%出版物中的25个关键词被分为不同类别，并显示了它们的平均出版年份。此外，图6中的相关矩阵显示了这些关键词在文章中同时出现的频率，也与以下分析相关。最常见的特定优化问题是TSP（225次出现）、整数规划（225次）和调度问题（219次）。虽然整数规划没有明确的趋势，但TSP的研究主要与元启发式蚁群优化（20）、遗传算法（18）和局部搜索（16）以及禁忌搜索（13）和模拟退火（10）的调度问题有关（见图6）。由于TSP是CO问题的代表，因此经常对其进行检查。如果可以为TSP找到有效的（多项式时间）算法，那么也可以为所有其他NP完全问题找到有效的算法（Hoffman et al.，2013）。整数规划问题（例如分配问题）通常也与CO密切相关（Conforti等人，2014）。然而，如果可行域是无限的，并不是每个协问题都可以表述为整数规划问题（Ibaraki，1976）。

调度问题通常用于决策支持，例如项目管理中的项目调度（Hartmann and Briskorn，2010）、人员调度（van den Bergh等人，2013）或维护调度（Froger等人，2016）。平均出版年数最高的关键词代表了公司最新的主题。最近的两个具体优化问题是稳健优化（平均出版年：2014.0）和多目标优化（2011.4）。自2015年以来，关于这些主题的出版物的年度百分比增长趋势也证明了这一点。在将优化技术应用于实际问题时，经常会遇到一些困难，即必须同时优化多个目标，而且并非所有参数都事先已知（Schmidt等人，2019年）。稳健优化方法包括几种保护决策者免受参数模糊和随机不确定性影响的方法。因此，管理者必须确定拥有稳健的解决方案对他意味着什么。基于最坏情况分析，利用最不利不确定性的实现来评估解决方案（Gabrel等人，2014）。多目标优化包括同时优化多个目标，方法是选择一个（帕累托）有效的解决方案，该解决方案在一个目标中无法得到改进，而在另一个目标中又无法使其恶化。近年来，这两个领域的概念已被结合到多目标稳健优化中（Schmidt等人，2019）。15解决这些共同问题最突出的通用解决方案技术是元启发式（435次出现）、启发式（419次）、优化（272次）和近似算法（258次）（见图5）。现实世界中的协同问题通常比较大，而精确的解决程序大多不够充分。

因此，启发式主要用于解决复杂的协同问题（Hertz和Widmer，2003）。在过去，人们开发了典型的专门启发法。然而，这种方法多年来发生了变化：出现了更通用的（超启发式）和不太专业的解决方案方法。这里的动机是，与从头开始开发专门的启发式相比，将元启发式应用于特定问题或问题类需要更少的努力（Gendreau和Potvin，2005）。对于启发式和亚启发式，对于某些输入，可以确定好的解决方案（即接近问题的最优解），但通常不确定启发式为何工作良好。在这种情况下，近似算法是有用的，这给启发式的研究带来了数学上的严格性。因此，可以证明启发式算法在所有实例上的表现如何，并且可以给出启发式算法表现不好的实例类型的概念（Williamson和Shmoys，2011）。图5：在8393篇文章中，CO上最相关的25个关键词及其出现次数、平均全球引用次数和平均发表年份。此外，8393项研究中包含了许多不同的特定元启发式（参见图5）。在文献中可以找到各种分类法来区分超启发式（见Z"apfel等人（2010））。举一个例子：Hertz和Widmer（2003）通过两个原则来区分超启发式，即局部搜索和总体搜索。作者将局部搜索方法定义为在每次迭代时从当前解转移到邻域中另一个有希望的解，从而对解空间进行深入探索。相比之下，总体搜索包括维护各种好的解决方案，并将它们结合起来生成更好的解决方案。

在8393项关于CO的研究中，最常见的三种元启发式是群体搜索和局部搜索的经典例子：遗传算法（521次；群体搜索）以及模拟退火（310次；局部搜索）和禁忌搜索（257次；局部搜索）。在至少有34个共同事件的研究中，这三种超启发式也经常被联合考虑（c.f.图6）。蚁群优化二次指派问题半定规划优化进化算法鲁棒优化计算复杂性多目标优化超启发式神经网络模拟退火遗传算法局部搜索拉格朗日松弛旅行商问题启发式算法背包问题近似algorithmschedulingbranch and boundlinear Programming Dynamic Programming Integer Programming 16 Optimization（动态规划整数规划优化）经常出现在被引用最多的前20篇文章中，也是最相关的具体元启发式方法之一，共有175次出现。关于蚁群优化的文章平均引用率最高（55，参见图5），其次是关于粒子群优化的文章（52）和关于二次分配问题的文章（50）。有关超启发式研究领域按时间顺序发展的更多信息，请参考S"orensen等人（2018年）。有关国家、组织和来源最重要主题的信息可在在线附录中找到。图6：组合优化研究领域中最相关关键字的相关矩阵。这些数字表示这些关键词在出版物中出现的频率。矩阵中的字段颜色越深，这些关键字出现在一起的频率就越高。3.4.3.

组合优化的应用领域除了关键字分析外，还使用MATLAB算法进行了单词分析。在这种情况下，关键字被分为单个单词，例如，组合优化分为组合优化和优化。这样做是为了确定CO方法的重要应用领域。在线附录中的表3列出了至少1%的CO出版物中出现的单个关键词。在该表中，被确定为CO的特定现实应用领域（而非图5中的特定问题或方法）的词语以粗体书写，并显示了这些应用领域文章最相关的关键词和来源。通过手动检查检查潜在应用区域的物品。例如，调度、旅行或车辆可以代表应用领域，但这些关键字几乎完全分别指协同问题调度问题、TSP或车辆路径问题。共确定了12个应用领域（参见在线附录表3中以粗体书写的关键词）。以下四个领域是最常见的（占所有8393篇文章的2%）：生产、数据、电源和管理。例如，生产研究领域涉及生产计划（如Shishvan和Sattarvand（2015））或组装（如Becker和Scholl（2009）），也与应用领域制造密切相关（如Amen（2006））。

如今，公司在全球生产网络中运营（Lanza et al.，2019），这是激烈的离岸外包、外包、全球采购、，andA B C D E F G H I J K L M N O P Q R T U V W X Y Z258 0 2 1 11 8 10 2 3 2 1 0 7 1 0 8 10 9 1 4近似算法（A）175 1 21 2 0 1 0 0 1 0 4 3 9 22 9 11 4 0 4 1 0 0 0 0 1 1蚁群优化算法（B）141 12 3 0 1 9 10 10 5 12 2 3 1 0 0 0 3 1 0 2 3 1 0 0 0 3 1 3 1进化算法（C）521 9 0 1 14 18 18 35 54 13 3 9 1 18 0 3 4遗传算法（D）112 0 33 0 4 5 3 8 1 2 1 0 2 6 0 1 3 1神经网络（E）101 0 1 0 0 0 0 0 0 6 4 6 1 7 1 0 1 0 2半定规划（F）136 4 5 4 0 5 5 5 5 2 1 1 0 1 1 1 2 3 0 3 1 8算法（G）219 10 7 1 2 3 21 13 10 3 0 2 6 2 2 6 6 6 6调度（H）272 7 1 30 8 17 2 6 2 2 3 0 1 2 4优化（I）234 8 31 34 23 3 3 3 3 3 8 2 2 2 16 1 2 0局部搜索（J）3 12 2 2 4 1 2 0 1 2 1 2 0 2 2 2多目标优化（K）419 28 35 17 3 24 8 4 9 2 12 1 1 7 8启发式（L）435 48 22 8 11 15 3 2 1 18 0 1 4 3元启发式（M）257 34 3 2 13 1 2 0 3 1 0 1 1 1 3禁忌搜索（N）310 9 3 8 3 0 2 13 0 3 1 1 1 1模拟退火（O）84 0 0 0 0 0 0 0 4 0 2 1粒子群优化（P）225 1 5 9 7 7 7 6整数规划（Q）101 0 4 0 12 1 3 0 2 0 2 0二次分配问题（R）84 5 3 1 1 1 1 1拉格朗日松弛（S）136 2 6 1 5 7分枝定界（T）84 2 1 2 0 0线性规划（U）225 1 7 3 4旅行商问题（V）83 7 4 6稳健优化（W）108 0 3计算复杂性（X）84 9背包问题（Y）128动态规划（Z）17拓展到新的国际市场。