基于LHHS和FCM的参数整定方法在优化问题中的应用

沙特国王大学学报一种基于拉丁超立方体Hammersley抽样和模糊C均值聚类的有效参数整定方法YaseminEryolda，s， AlptekinDurmus，og，土耳其加济安泰普大学工业工程系阿提奇莱因福奥文章历史记录：接收日期：2022年2022年8月5日修订2022年8月10日接受2022年8月13日在线提供保留字：LHHS模糊C均值聚类分析参数整定A B S T R A C T元启发式算法，这是为了在可接受的时间内找到接近最优的解决方案的优化问题，有一个显着影响其性能的特定参数并且微调这些参数可以导致这样的算法的有效且性能良好的版本。提出了一种基于拉丁超立方体Hammersley采样（LHHS）和模糊C均值聚类（FCM）的算法配置方法。这些方法的使用首先在算法配置文献中我们在两个实验和四种情况下评估了所提出的调整方法，并将其性能与当前最先进的自动参数调整方法进行了比较。在第一个实验中，我们调整了标准遗传算法（SGA）的三个数值参数，在第二个实验中，我们调整了人工蜂群（ABC）算法的两个数值参数。我们的实验结果表明，所提出的调整方法表现出更好的性能比其他国家的最先进的调整方法在两种情况下。并在另外两种情况下与其他算法配置方法进行了比较我们的实验的最重要的结果是，不仅最佳配置，而且保留在最终配置集合中的其他配置都表现出与用其他最先进的参数调整方法发现的最佳配置竞争的结果然而，由于所提出的方法被设计为使用所有可用的调谐预算在大的初始配置集合中找到性能最佳的配置，因此它需要更多的计算时间。©2022作者（S）。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍近年来，由于现代科学技术的进步，现实世界中的优化问题（如设施选址、车辆路径等）的难度和维数也在不断增加。优化问题可以被定义，例如有效地分配有限的单一资源以满足给定的目标，并且可以在许多不同的领域中找到，例如如生产、管理、财务和工程。为解决这些问题而开发的精确数学方法不再足以解决它们，因为大量*通讯作者。电邮地址：y as eminsiri n 87@wi n dowslive. com（Y. 你好，我是说，我是说。edu。tr（A. Durm u，sogu）.沙特国王大学负责同行审查制作和主办：Elsevier需要计算工作量来获得最优解，并且没有多项式时间算法可用于找到解。因此，为了在可接受的时间内找到优化问题的近似最优解，研究人员开发了所谓的启发式和元启发式方法。元启发式被Birattari和Kacprzyk（2009）定义为Meta启发式方法的发展和改进已经研究了四十多年。然而，这些元启发式算法的性能很大程度上受其参数值的选择。微调这些参数可以导致这种算法的有效且性能良好的版本，而选择不佳的参数值可以导致较差的算法性能（Eryolda，s和Durmu，s ogJumlu，202 2）。直到最近，优化算法的设计和参数调整由于这种手动过程通常是不充分的，自动参数调整方法在过去几年中已经开始变得可用https://doi.org/10.1016/j.jksuci.2022.08.0111319-1578/©2022作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comY. Eryolda，s和A. Durmu，soglu沙特国王大学学报8308自动算法配置方法研究表明，在处理计算困难的优化问题时，自动算法配置技术可显著提高元启发式性能，并有助于分析和理解测试问题、目标算法性能和所选参数值之间的相互作用（Eiben和Smit，2011）。参数配置问题的一个简明的定义可以描述如下：对于给定的具有多个参数的参数化算法A，(C)（每个配置ce C都是对参数）、问题实例集（I）和评估算法性能的性能度量（m）目标是找到算法（A）的参数设置，其根据性能度量（m）优化性能指标通常基于算法速度或解决方案质量，或它们的组合（Eryolda，s和Durmu，s oglu，202 2）。 Birattari和Kacprzyk（2009）提供了参数整定问题的更正式的定义。Smit和Eiben（2009）将算法配置过程分为三层。这些层可以从下到上列出如下：应用层（优化问题，例如，TSP或基准测试函数）、算法 层 （ 求 解 器 或 元 启 发 式 ， 例 如 ， CPLEX 求 解 器 、 ABC 算 法（Karaboga和Basturk，2008））和设计或调整层（参数调整方法，诸如ParamILS（Hutter等人，2009 b）或irace（López-Ibáñez等人，2016））。在这个整体过程中，有两个优化问题。第一种是算法层的Meta启发式算法，试图为应用层的目标问题确定一个最优解。第二种是调整方法，试图确定算法层上元算法的最佳参数值。图1总结了这个过程。算法配置问题有一些特殊的困难，例如它是一个耗时的过程（通过对性能较差的配置使用有效的早期消除策略，可以进一步降低调整的计算成本），参数之间存在复杂的非线性相互作用，并且最佳参数配置取决于目标测试问题（Joshio等人，2014年）。它也是一个随机过程，因为算法本身通常是随机的（对于确定性算法，它们的性能取决于特定的实例）（Birattari等人， 2010年）。本文提出了一种基于拉丁超立方体Hammersley采样（Wang etal.，2004）和模糊C均值聚类（Bezdek等人，1984年）提出。使用LHHS以获得初始参数配置集并基于其对目标函数的性能对这些集进行聚类，代表了算法配置中的新方法。Fig. 1.算法配置过程。文学。从一个良好的初始配置集开始是非常重要的参数调整技术，和开发的参数调整方法的最终性能取决于初始配置集的质量虽然一些研究评估了各种配置技术的抽样方法，但在以前的算法配置问题研究中没有使用LHHS方法标准方法如全因子设计（FFD）或拉丁超杯采样（LHS）被当前最先进的算法配置方法（即，F-race方法使用FFD或随机均匀采样，SPO方法使用LHS来生成初始（或候选）配置 集 ） 。 由 于 LHHS 方 法 的 成 功 已 在 最 近 的 研 究 中 得到证明（ Eryolda ，sand Durmu ，s oglu ， 2021;Dige and Diwekar ，2018），我们决定在研究中使用LHHS获得广泛的初始配置集。所提出的方法的另一个新颖之处是使用模糊聚类方法，这导致避免不公平的消除配置考虑其性能上只有一个问题。虽然问题集的聚类和为这个指定的问题簇找到最佳参数值已经被广泛研究（并且被称为每实例算法配置问题），但是参数配置集的聚类对于自动算法配置的文献来说是新的。3.1和3.2小节讨论了LHHS和FCM方法背后的逻辑以及选择这些方法的原因我们通过两个实验来评估所提出的调谐方法和四种情况下，并比较其性能与国家的最先进的参数调整方法。在第一个实验中，我们调整了标准遗传算法（SGA）的三个数值参数（Mrsio等人，2014）（种群大小，突变率和交叉率），在第二个实验中，我们调整了人工蜂群算法（ABC）的两个数值参数（“限制”和“种群大小”）。在所提出的方法中，LHHS方法被用来获得一个广泛的初始配置设置通过采样的参数空间。采用FCM算法基于候选配置在测试问题上的性能对候选配置进行聚类，并基于这些聚类步骤在每次迭代中进行本研究规定如下：在第2节中，我们定义的参数调整问题，并提供有关本研究中所采用的方法的信息，而在第3节中，我们详细解释了建议的参数调整程序，并在第4节中，我们提供了一个实验评估建议的调整方法和讨论所考虑的四种不同情况下所获得的结果最后，在第5中，我们提供了一组结论性意见和一些建议，为未来的研究。2. 自动算法配置方法算法的配置问题引起了研究者的关注，近年来出现了大量的算法自动调整方法。Eiben和Smit（2011）对此领域进行了详细的分类综述，将这些方法分为四类，即基于模型的方法、采样方法、筛选方法和MetaEA。这些技术在文献中通常分为两无模型方法包括元EA方法和基于局部搜索的方法。基于模型的方法包括基于竞争的方法、传统的基于实验设计的方法和基于序列模型的优化方法。这两种方法之间的主要区别在于，基于模型的方法构建了一个模型，用于评估算法Y. Eryolda，s和A. Durmu，soglu沙特国王大学学报8309P1/1PT1通过在几种设置下运行目标算法获得的观测值的参数值（Hutter等人，2009年a）。Huang等人（2019）提供了关于自动算法配置的详细调查。在图2中，我们举例说明了广泛使用的无模型和基于模型的自动化算法配置方法。在本节中，我们将简要介绍五种最常用的自动参数调整技术，我们在本研究中使用这些技术来与我们新开发的技术进行比较。法有关其他已开发的自动算法配置的详细信息参数向量或先前定义的时间预算。F-Race应用基于不同问题实例的区组设计（一个实例被认为是一个区组）弗里德曼检验零假设声称每个块内参数向量的所有可能排名都是相等的。Freidman检验的检验统计量在等式中展示（一）.这里，k是竞争的步长，r是竞争中幸存的候选参数配置，Rij是配置cj的秩在迭代（或块）I内，且R j =PkRij是总排名C2在使用方法时，我们参考Huang等人， 2019年;和Eiben和Smit，2011.此外，Eggensperger等人（2019）提到了算法配置问题的常见陷阱，并建议处理它们的最佳实践。在所有迭代中的j。弗里德曼统计量是v分布的，n- 1自由度。BURR-1BURPrRj-22K1/1R第1页Rij-krr1= 42.1. F-RaceBirattari等人（2002年）基于机器学习文献中用于模型选择的方法（Maron和Moore，1994年; Moore和Lee，1994年）和Friedman该程序的目的是通过消除表现不佳的参数向量，找到在有限配置集（通过全因子设计或均匀随机抽样创建）中表现出最佳性能的参数向量，只要它们在统计学上表现不佳。然后对剩下的进行迭代。F-Race过程通过对每个配置执行“n”次运行开始，以便在消除之前获得足够的数据。针对每个参数配置记录所获得的数据。在每次迭代中，随机选择一个问题实例，用于候选参数配置的性能比较。在评估每个实例中的配置之后，每个配置的成本（或效用）被添加到存储的值。每次迭代后，Friedman如果根据给定的显著性水平拒绝零假设，则可以推断至少一个参数向量优于至少一个其他参数配置。然后执行参数配置之间的成对比较。从候选人的配置集中丢弃统计上较差的配置。终止条件是只剩下一个F-Race有自己的参数，必须在开始之前设置。这些参数包括显著性水平（a）、初始比赛的数量（n）以及应该执行的最大数量。在消除之前执行（max-exec）。连续参数整定时参数值的离散化是该方法的主要局限性之一。另一个问题是，在过程开始时，必须评估所有配置，这限制了用于小调优预算的配置空间的大小。F-Race的优点是它允许快速消除较差的配置，从而加速整个过程。2.2. REVACNannen和 Eiben（ 2007 ） 提 出 了参 数 的 相 关性 估 计 和 值 校准（REVAC），以调整元分析的数值参数。REVAC方法可视为在估算范围内分布算法（EDA）（Pelikan et al. 2002）。Revac从N个配置开始，并通过渐进过程对其进行改进。每个配置都在所有问题实例上进行评估（仅使用一个随机种子;它不会使用不同的种子复制同一问题的运行），并存储每个配置的性能。在每次迭代中，使用多父交叉和变异变换来创建一个子参数向量，并且使用最旧的配置来改变该子参数向量。首先对K N个<最优配置进行均匀交叉，得到子配置; 然后，所获得的新配置在间隔2H上突变。 换句话说，随机值是从第H较低和第H较高的邻居选择的图二. 最有效的自动化参数调整技术的说明。2ð1ÞY. Eryolda，s和A. Durmu，soglu沙特国王大学学报8310目标参数，它对每个参数重复，然后分配给子配置。人口的最旧配置已更改为新的子配置。在REVAC的起始点，所有参数具有均匀分布，并且在其后续步骤中，REVAC缩小参数值的范围。该范围的狭窄性给出了关于给定参数对算法性能的重要性的信息Revac的终止标准是实现的最大执行次数。Revac还返回最后生成的参数配置总体，并根据性能从该总体中选择一个“m”可调参数的Revac总体矩阵如图所示。3.第三章。矩阵的每一行代表一个常数，种群N的形态第j个配置的第i个参数的值由pi;j表示。每列显示了N配置总体中每个参数值的分布。通过取相应列的下限和上限值评估每个参数的最终区间值Revac有四个参数，应该根据所考虑的测试问题设置：交叉算子大小（Cs），变异算子大小（H），最大执行次数（max-exec）和种群大小（N）。2.3. SPOBartz-Beielstein等人（2005）提出了基于实验设计（DOE）和计算机实验设计与分析（DACE）的序贯参数优化（SPO）。SPO程序首先使用拉丁超立方体抽样（LHS）定义一组设计点（初始参数向量或配置）。 为了选择k个设计点，它将参数值的范围划分为k个相等的范围，之后在每个间隔中选择随机数（Bartz-Beielstein等人，2005年）。每个参数向量的perfor-mance通过几个exansion- tions评估。性能最佳的设计点标记为初始解。随后，构建无噪声的随机高斯过程模型，然后选择下一次迭代的新设计点，并使用该模型的预测和预测不确定性进行测试，该模型由迄今为止发现的最佳点和根据在先前阶段中创建的模型的一组预期良好设计组成（Mr.P. 2014年）。为了找到任何期望的好设计点，使用LHS方法获得了新的且通常更大的可设计构型集。使用候选配置模型值来计算广义预期改进标准。通过考虑模型的预测不确定性，选择比现有最佳参数配置更好的概率最高的配置用于以下迭代（Mrsano等人， 2014年）。图3.第三章。REVAC一个种群的结构这种方法的主要缺点是它只能处理小数和整数值。SPO方法有其自己的参数，需要在开始之前设置，如初始设计大小、重新评估的数量、候选配置的数量、最大执行次数以及新旧设计点的比率。2.4. ParamILSParamILS由Hutter等人（2009 b）提出，它是一种迭代局部搜索算法，并受到手动参数调整技术的影响。ParamILS从一个默认参数配置（根据用户经验设置）和n个随机生成的配置开始。选择这些n +1个配置中的最佳配置作为初始配置以开始本地搜索过程。一个迭代的第一次改进算法是ParamILS的一个局部搜索过程这些选定的（r +1）配置进行评估，并与最佳性能的配置初始化本地搜索过程ParamILS通过迭代以下步骤构建一个局部最优值链该算法从初始解出发，通过随机选取几个参数的值，进行局部根据该比较，如果观察到对最佳解决方案的改进，则选择新的解决方案作为最佳配置。ParamILS 还包括在使用随机初始配置重新启动每个局部搜索ParamILS之后具有重新启动概率pr的多样化机制ParamILS方法有自己的参数，如重新启动概率（pr），最大执行次数（maxExecs），以及第一步和每次迭代中的随机解2.5. CRS调谐Vecek等. （2016）提出了一种新的算法配置技术，该技术基于一种用于比较和排名进化算法的新方法，即进化算法的国际象棋评级系统（CRS4EAs）和Meta进化方法。在该方法中，每个参数向量被证明是一个国际象棋选手，它有自己的评级，评级偏差，和评级区间。评分代表玩家的绝对实力在每次执行锦标赛之后，更新评级和评级偏差，并且从评级和评级偏差计算评级间隔该方法以与REVAC类似的方式从M个随机生成的配置群体开始在开始时，执行具有M个配置的锦标赛。在每次独立运行期间，针对每个问题的每个配置的性能被记录为一组结果。然后，成对地比较配置的性能结果，并相应地标记为赢、输和平局。每个参数配置的评级、评级偏差和评级区间根据评估的评级系统（Glicko-2评级系统（Vecek等人， 201 4））。 为了选择将在下一次迭代中保留的参数，它们从总体中消除所有比最佳参数向量表现明显更差的参数向量。他们使用一个称为最大母体大小（MPS）的参数，以在群体中保持最多MPS（通常为M/2）配置最后，应用均匀交叉和变异从剩余的构型中产生新的构型，以再次达到种群中的M个构型终止标准Y. Eryolda，s和A. Durmu，soglu沙特国王大学学报8311方法是最大执行次数。CRS调整方法创建一个排行榜，该排行榜显示所有幸存的配置、其评级、评级偏差和评级间隔作为输出。具有较高额定值的配置可被视为最佳参数配置。CRS-Tuning有五个参数，分别是种群大小（M）、最大执行次数（max-exec）、最大父代大小（MPS）、变异概率和交叉概率。MPS用于提供太多不属于总体的类似性能配置3. 该方法在开发算法配置方法的过程中有两个重要步骤：第一个是生成并启动一个好的初始参数配置集。第二步是在第一步生成的初始配置集合中选择最佳参数配置的过程（或者换句话说，消除性能较差的参数配置）。在所提出的算法配置方法中，我们选择LHHS方法来生成初始参数集，我们使用模糊C均值算法来消除性能较差的参数配置。LHHS和FCM方法背后的逻辑、选择这些方法的原因以及使用这些方法的优点详见第3.1和3.2小节。随后，在第3.3小节中详细提供了建议的参数整定程序3.1. 使用的采样方法（LHHS）抽样方法已被用于广泛的科学领域，如工程和计算统计，在概率算法，数学和物理的实施（Eryolda，s和Durmu，s oglu，202 1）。近年来，Dige和Diwekar，2018; Metropolis和Ulam，1949; Box和Hunter ， 1961; Owen ， 1992; Hammersley ， 1960; Kocis 和Whiten，1997; Sobol，1976;McKay等人， 一九七九年加鲁德等人（2017）对这些采样技术进行了全面的分类调查。建立一个有价值的初始配置集来评估算法的性能是算法配置方法的关键。此外，这些算法配置方法的最终性能取决于初始配置集的质量然而，这些问题在现有文献中尚未被深入研究，并且当前最先进的算法配置方法（即，F-race方法使用FFD或随机均匀采样，SPO方法使用LHS来生成初始（或候选）配置集）。如上所述，抽样方法被广泛用于参数设置问题，如果与完全析因设计相比，抽样方法的优点是它们减少了搜索参数向量的数量，因此，减少了相关的搜索工作（Eryolda，sand Durmu，s oglu，202 1）。在我们以前的研究（Eryoldas，和Durmu，s oglu，202 1），我们比 较 了 八 种采 样 方 法 的 参 数 配 置 的 差 分 蚂 蚁 Stigmergy 算 法（DASA）。据我们所知，这是第一次研究，以评估使用的LHHS方法的算法配置问题。研究结果表明，LHHS方法产生的结果优于所有其他抽样方法。LHHS是一种新颖的采样技术，它结合了LHS具有HSS的优异多维均匀性。用于创建多维样本集的LHHS方法的基本步骤总结在图4中。在该方法的初始步骤中，使用LHS生成样本值，然后继续使用HSS方法（Eryolda，s和Durmu，sog）将其2021年）。近年来，LHHS已被用于各种研究作品，以及使用LHHS方法获得有效样本集的最新研究是：Mukherjee等人，2020;Mukherjee and Diwekar，2021.对于该方法的详细解释，我们参考原始论文（Wang等人， 2004年）。由于LHHS方法的成功已在最近的一些研究中得到证实（Eryolda，sand Durmu，s oglu，2021;DigeandDiwekar，2018），我们决定在我们的研究中使用LHHS。然而，由于最近才意识到HSS的均匀性在30多个变量下会发生扭曲，因此建议使用跳跃式HSS和LHHS方法来克服这个问题（Dige和Diwekar，2018）。他们的实验结果证明，这些方法比基本的HSS和LHHS方法具有更好的均匀性。因此，当测试算法的参数数量大于30时，可以使用跳跃-LHHS方法，例 如 为 解 决 混 合 整 数 问 题 而 开 发 的 CPLEX 求 解 器 （ Dige 和Diwekar，2018）。3.2. 模糊c均值聚类聚类可以定义为基于定义的相似性度量从给定数据集 模糊聚类技术是最有效和最广泛使用的聚类方法之一（例如Rubio等人，2017年，Sanchez等人，2014年）。一种特定的聚类技术是模糊C均值（FCM）聚类，其由Dunn（1974）开发并由Bezdek（2013）改进。 FCM方法在最近的研究中得到了充分的研究和改进，例如Askari，2021; Zhou等人，2021; Hua等人， 2021年; Ke等人，2021年在FCM方法中，每个数据点被认为属于两个或更多个聚类，其隶属度值范围为[0，1]。所有聚类器的数据点的成员资格值之和换句话说，对于m个数据点的集合X =（x1，x2，. . ，xm），我们得到一组n个簇，c1;c2;;Cn，以及模糊分块矩阵U = uk，j2 [0; 1]（其中k = 1.m，j = 1 n，uk，j表示数据点的隶属度xk在聚类cj中）。a的隶属度见图4。 LHHS方法流程图。●●Y. Eryolda，s和A. Durmu，soglu沙特国王大学学报8312KJ≤1PuPnc¼k¼1KJ≤≤KJkxk-clk-XXP如果聚类j中的数据点靠近聚类j的中心，则聚类j中的数据点的隶属度高于该数据点在其它聚类中的隶属度（Cj），并且将该数据点分配给Cj。FCM算法是基于迭代最小化的目标函数定义在方程。（二）、FCM算法有一些输入参数需要在开始之前设置;例如，聚类数（n）;参数（f），其是任何实数并且指示权重的影响;终止准则（e）;和内积范数 ||*||、表示任何数据点与聚类中心之间的相似性;此外，初始聚类中心的集合U（°），可以随机提供或初始化（Bezdek，2013）。然而，在关于FCM的现有文献中，运行FCM的常见方式是使用随机初始模糊划分矩阵（Mishro等人，2020; Lei等人， 2018年）。在调谐过程的各个阶段，幸存的候选配置可以展示出更相似的性能，使得评估配置之间的差异变成更具挑战性的任务。在这里，我们预计，使用聚类方法，以确定赢家配置将比使用显著性检验更有效，即使使用少量的独立运行的配置。这是我们的消除方法优于零假设显著性检验的第一个优点，零假设显著性检验通常用于这种消除。其次，它免除了现有显著性检验方法的常见统计陷阱（Dunn，1974）。3.3. 建议的参数调整程序本文提出了一种基于拉丁超立方体Hammersley采样（LHHS）和模糊C均值的M nJf<$ufkxk-cjk21≤ f12

下载后可阅读完整内容，剩余1页未读，立即下载