改进元启发式算法的微调:实验设计与赛车算法相结合的方法

摘要

通常，元启发式算法通过对每个具体情况的参数进行少量修改来适应大量的问题。然而，这种灵活性需要付出巨大的努力来正确地调优这些参数。因此，元启发式的调优成为这些算法研究中最重要的挑战之一。因此，本文旨在提出一种结合统计和人工智能方法的元启发式微调方法。其核心思想是一种启发式方法，称为启发式定向竞赛算法(HORA)，它探索参数的搜索空间，寻找接近于有希望的备选方案的候选配置。为了验证该方法的有效性，我们给出了两个不同元启发式算法:模拟退火(SA)和遗传算法(GA)的优化实例，以解决经典的旅行商问题。考虑到通过竞赛方法调优的相同的元启发式，将结果进行比较。总的来说，所提出的方法在调优过程的总时间方面被证明是有效的。我们的结果表明，通过HORA调优的元启发式算法获得的结果与通过其他微调方法调优的结果相似，且计算工作量少得多。

1.介绍

通常，元启发式算法适用于大量的问题，对每个具体情况的参数很少进行修改。然而，在某些情况下，这种调整需要付出巨大的努力来正确地调整参数。有时，由于调优过程的时间限制，算法最终可能导致质量较差的解决方案。

元启发式的灵活性使这些算法能够为广泛的问题找到可接受的解决方案，但与此同时，由于参数微调的难度，很难获得好的(有时是最优的)解决方案。因此，在这些算法的设计和应用背景下，元启发式的调优成为最重要的研究挑战之一。

这些挑战通常是不同研究团体感兴趣的。在当代文献中，统计技术的研究脱颖而出，并得到有效方法的支持，以帮助理解过程，也达到有效的设置(例如，[1- - - - - -7和许多其他的)。

本文旨在对文献作出贡献，提出一种结合统计和人工智能方法的元启发式微调方法，如实验设计(DOE) [8]及赛车概念[9，10］.广义地说，我们的方法使用DOE作为定义参数搜索空间的工具。然后，我们应用Racing概念探索之前定义的搜索空间，寻找与有希望的候选配置接近的替代方案，以便始终找到好的配置。搜索过程关注于在迭代过程中动态创建备选方案，并基于统计证据对其中一些方案进行评估和丢弃。

提出的方法结合了文献中不同策略的特点，如CALIBRA [11]，I/F-Race[10，12]和ParamILS [13，使用一个启发式方法来定义搜索空间，并有效地集中搜索该搜索空间内的候选配置。这种方法将通过一个简单的案例研究来说明，其中两种截然不同的元启发式算法(模拟退火，SA，和遗传算法，GA)的一组参数将被调整来解决一个经典的优化问题，如旅行推销员问题(TSP)。建议设置的质量将与赛车调优方法进行比较。

论文的其余部分结构如下：第一节2提出了调整元启发式的问题，我们的方法结合统计和人工智能方法来解决这个问题。节3.本文概述了所考虑的问题，以及案例研究中使用的元启发式方法。提出的方法应用于案例研究（第节）4)来微调元启发式SA和GA。部分4并给出了案例分析结果。我们最后要考虑的是Section5．

2.元启发式优化问题的一种方法

在当代文献中，有可能找到与算法参数微调问题相关的正式定义[10，14，15］.

让具有一组参数的元启发式(例如，)，必须调整以解决类的问题。的参数可以假设一个有限的值集，它的基数也可以根据和．如果是一组候选构型吗θ是任何设置，则调优元启发式问题可以形式化为状态空间:

广义地说，这个问题包括确定最佳设置出现在解决问题．然而，它的确定并不总是简单的，在最坏的假设下，它可能需要在状态空间中进行全面搜索．

2．1．状态空间的动态

在本研究中，我们提出一种自动方法来避免在状态空间(1)，并仍然找到一个良好的设置来解决．这个想法是考虑一个代理谁的行动修改状态(1) [16］.在我们的方法中，这个代理是一种启发式方法，它结合了稳健的统计方法在迭代过程中创建候选配置并发现好的配置，基于对广泛问题的统计评估。如果一个行为(例如，创建替代品)遵守某些约束(例如，状态空间边界)，那么它是有效的。因此，给定一个初始状态(例如，最知名的候选配置)，我们应用启发式方法来探索(1)通过在有希望的备选方案附近创建候选配置。

启发式方法产生的动作修改(1)通过在一些最知名的备选方案附近按需创建候选配置，作为一系列候选配置：

这样的动作可以被认为是状态空间中的有向图，其中节点是状态，弧线是动作(图)1）.

从步骤来候选配置的集合可能会丢弃一些在统计上较差的备选配置。假设一些候选配置保留在这个集合中，它们将在更多的实例中进行评估。因此，求解等价于在(1); 从初始状态到最终状态，也就是说，为．

为了说明这个过程(图1)，让我们考虑任意状态空间，在每个迭代中，创建候选配置。在迭代结束时，集合中的所有备选项对候选配置进行评估，质量较差的配置将被丢弃。因此,一组是动态的;也就是说，它的大小可以增加或减少。该过程继续在搜索空间中寻找备选项，直到一个停止条件(例如，在，运行时限制)。

2．2．元启发式的自动调优

调优过程从任意选择的开始实例()，然后定义元启发式的参数范围。将之前选择的实例作为训练集，使用响应面方法(RSM)进行实验研究，为每个实例定义最佳参数设置。因此，在实验阶段结束时会有每个参数的不同设置，每个参数都与一个实例相关。

在训练集中确定的设置保证了参数的多样性，用它们来定义每个参数的边界，即以训练集中每个参数的最大值和最小值为限制的参数搜索空间。然后，目标是根据先前定义的搜索空间边界，在一些最知名的候选配置的邻域上动态地创建替代方案。对于每个备选方案，目标算法都在一个扩展的实例集中运行，该实例集比前一个实例集大。

这个过程(图2)被称为启发式面向竞速算法(Heuristic Oriented Racing Algorithm, HORA)，这是由于在搜索空间中探索备选方案的方法，即使用启发式方法，并通过竞速方法对其进行评估。

3.考虑的问题和元启发式:概述

优化问题在许多领域(例如，科学、工程、管理和商业)和不同的领域都很常见。本质上，它们涉及到从一个具有许多局部极值的函数(称为目标函数)中找到一个称为最优的极值(最大值或最小值)。其中一些问题是运筹学领域的经典问题，如旅行推销员问题，涉及大量的专业文献[17- - - - - -20.］.

旅行商问题(traveling salesman problem, TSP)是一个经典的优化问题，它的思想是在一组给定的城市之间找到一条最短的路线，起点和终点都在同一城市，使每个城市只访问一次。TSP由一个集合组成城市()和相应的距离每对城市中，以致．这个问题被归类为对称的，或不对称［20.］.

这个问题被认为是NP-hard [21]；因此，为了获得最佳解决方案，需要大量的计算工作，并且需要使用有效的算法。元启发式是解决没有特定有效算法的问题的最著名的方法之一。许多元启发式的灵感来自不同知识领域的隐喻，如物理ics（粒子群优化和模拟退火）和生物学（遗传算法和神经网络）。通常，这些算法在搜索模式方面彼此不同，但为多样化（搜索空间探索）和集约化（开发有前景的区域）提供准确和平衡的方法和共享特征，例如使用随机成分（涉及变量的随机性），并具有必须根据所研究问题设置的各种参数。

模拟退火(SA)是Kirkpatrick等人提出的一种概率方法[22]及Černý [23，以求得具有多个局部极小值的目标函数的全局极小值。SA被广泛应用于解决优化问题，它模拟了固体缓慢冷却的物理过程，使最终产品成为均匀质量，以达到最小的能量配置[24］.另一方面，遗传算法(Genetic Algorithm, GA)是由Holland [25达尔文的进化论启发了他求生的原则。遗传算法模拟了一个进化过程，在这个过程中，个体(父母)的适应度对生成新的个体(孩子)至关重要。

这些算法之间的主要区别在于所实现的搜索方法。SA在一个解决方案()和另一个()，并使用概率测试来接受新的解，这有时允许低质量的解在搜索过程中被考虑。另一方面，遗传算法作用于一个解的种群，它的新一代(后代)是由前一代(父母)的最适个体产生的。这个特性(生存原则)保证了新一代解决方案的质量提高。

SA和GA算法都有广泛的参数(例如，SA的初始温度及其下降速率、交互次数、交叉和变异速率、GA的种群规模)，在开始解决问题之前必须调整这些参数。由于元启发式极其依赖于分配给这些参数的值，因此在微调过程中必须仔细研究它们，因为它们可以定义算法的成功。

4.个案研究

在我们的研究中，我们选择了每个元启发式的一组参数，这些参数在文献中使用最频繁，似乎会影响SA和GA的性能，而不管研究的问题是什么。考虑的SA参数为初始温度值()，一个温度级的迭代次数()和温度冷却速率(α)，而遗传算法选择的参数为突变率()、交叉率()、人口规模(μ)，以及代数().参数（表1）1)在参数的可操作性范围内(它们的实际限制)进行选择，以促进搜索空间的多样性，以及每个特定参数设置之间的差异。

调优过程从一个训练集开始从TSPLIB中任意选择的TSP基准实例[26］.与DOE的研究是通过限定中心复合材料设计(CCD)进行的[8，其中一些点克服了以前设置的限制，以确保对参数的适当估计。

因此，经过实验研究，我们对每个参数有四个不同的结果，每一个都与一个实例相关。根据这些结果，我们定义了参数的搜索空间，其极限是参数在训练集中的最大值和最小值。因此，SA搜索空间为(我) ：；(2) ：；(3) :【］.在GA的情况下，我们有如下的搜索空间:(我) :【］(2) :【］(3) :【］(iv) :【］

值得注意的是观察结果，其中一些参数值超出了最初定义的限值（表1）1)然而，正如前面指出的，这是由于选择了CCD，其轴向点为感兴趣的区域建立了新的限制。

在此基础上，通过HORA启发式在一些最著名的候选配置的邻域创建备选方案，对状态空间进行探索。对于每个备选方案，我们在15秒内对扩展的实例集（例如，在本研究中，扩展集与基准TSP中的40个实例相匹配）运行目标元启发式（例如，SA和GA）。该过程重复了10次，通过HORA对超启发式进行微调的结果以平均值和标准偏差表示()在桌子上2．该表还显示了调优过程的总时间(以秒为单位)。

为了比较，我们考虑了前面定义的参数搜索空间和另一种微调方法，如基于F-Race方法的竞速算法[10，12，14，从这里叫赛车。SA使用的设置如下所示：，,；对于GA，我们有，，,．

这些设置被定义在一个被先前定义的搜索空间所限制的离散区间内，对于导致一个好的结果的算法来说，若干级别似乎足够了。因此，每一种可能的参数组合都有不同的算法设置，因此，对于SA算法和GA算法，搜索空间分别由70个和192个不同的参数设置组成。这个想法是用赛车在HORA之前使用的同一组实例上运行目标算法15秒后，从多个选项中选择一个可能的良好配置。这个过程也重复了10次，所研究的元启发式的微调结果(表3.)以平均值和标准偏差()。该表还列出了总时间(，以秒为单位)。

从这些结果(表3.)，我们可以注意到HORA和赛车在参数设置方面，由于两种方法对候选配置使用相同的评估方法。但可以强调的是，使用HORA进行调优的过程花费了使用微调过程所需的11.6%和5.3%的时间赛车，分别为SA和GA。

4．1.分析的结果

虽然这不是本文的主要目的，但验证HORA和赛车为TSP取得良好的结果。注意，由配置的算法产生的结果的质量赛车可能在很大程度上取决于最初建立的候选配置的数量，因为这种方法对先前定义的候选配置的搜索空间进行了详尽的分析。因此，候选配置空间越小，调优过程以较差的参数设置完成的可能性就越大，从而影响该过程调优的算法的结果质量(甚至是执行时间)。对于HORA方法，这个限制不存在，因为它从任何候选配置开始，动态构建参数设置空间。

一般来说，元启发式采用一定程度的随机性来分散搜索，避免搜索空间的限制。因此，这些算法的一次运行可能导致与下一次运行不同的解决方案。因此，为了测试设置的质量，我们在TSP上运行了5次元启发式SA和GA后收集了实验结果。为了比较结果，我们使用 在哪里算出的解是和吗是问题的最佳解决方案。因此，降低差距，算法的性能越好。

研究结果由科学软件Scilab (http://www.scilab.org)，英特尔®Core i5TM 1.8 GHz, 6gb内存，1TB硬盘，Windows 8 64位。

收集结果时考虑了表中所示的元启发式SA和GA的设置2和3.，为HORA和赛车,分别。表4和5在TSP基准的10个实例中，给出了SA和GA的5次运行的结果，停止条件如下:不改变目标函数的迭代次数(200次)和最大运行时间(300秒)。在这些表格中，方法的结果用大写字母标出(霍拉舞)(赛车）.列差距的最佳发现价值是3.),是运行时间的平均值()，及和为所有选定实例的算术平均值和标准偏差。

从元启发式SA的结果(表4)我们注意到，通过HORA的微调过程可以获得更高质量的解决方案。请注意,差距平均而言，由HORA调音的SA比差距的相应版本赛车，虽然运行时间是不是平均比去年高4.5%．性能的下降可能与参数有关（初始温度的值），根据HORA，该值略高，需要更多时间才能找到优质溶液。

对于通过遗传算法获得的结果（表1）5)，我们还注意到，当由HORA调优元启发式时，质量稍好一些的解决方案，尽管此版本平均要求运行时间是由HORA调优的相应版本的两倍赛车．

图形分析（图1）3.)揭示了所研究的元启发式数据分布的差异，使得SA图的结果更接近最优解。根据结果(表4和5)在图形分析的支持下，可以确认通过HORA进行的微调过程可以获得更高质量的解决方案。

5.最后考虑

本文提出了一种解决元启发式优化问题的方法。将问题形式化为状态空间，采用统计(DOE)和人工智能(竞赛算法)相结合的启发式方法对状态空间进行有效探索。

所提出的方法称为HORA，它对一类问题中有限数量的实例应用稳健统计，以定义参数的搜索空间。因此，从一些最著名的候选配置的邻域动态创建的备选方案中，它采用竞速方法来一致地找到好的设置。

从一个案例研究，HORA应用于两个不同的元启发式的微调。它的结果与同样的元启发式算法进行了比较。HORA方法被证明在整定过程的总时间上是有效的，因为它只需要其他研究方法所需时间的一小部分。通过实验研究发现，通过HORA调整的元启发式SA和遗传算法可以获得类似的结果(最终更好)赛车方法，但需要强调的是，使用HORA进行调优的过程要快得多。这种更好的性能可以通过如何探索状态空间中的备选项来解释，这包括在一些最知名的候选配置的邻近区域创建备选项，并通过竞赛方法对它们进行评估。

本研究的目的是提出提出的方法，并验证其有效性，当应用于不同的元启发式。我们的结果表明，HORA可能是一个有前途和强大的工具，以协助微调不同的算法。考虑到其他元启发式和问题，还可以进行一些额外的研究来验证它的有效性，以及探索其他启发式方案，以在参数设置的状态空间中追求良好的配置。

的利益冲突

作者声明，本论文的发表不存在利益冲突。

参考文献

1. F. Dobslaw，“基于实验设计和人工神经网络的元启发式参数调优框架”第六届国际自然计算会议论文集，第6卷，第1-6页，埃及开罗，2010。视图:谷歌学术搜索
2. S. Lessmann, M. Caserta和I. M. Arango，“调优元启发式:一种基于数据挖掘的粒子群优化方法”，专家系统与应用第38卷第2期10, pp. 12826-12838, 2011。视图:出版商的网站|谷歌学术搜索
3. C.Neumüller、S.Wagner、G.Kronberger和M.Affenzeller，“元启发式优化算法的参数元优化”，年第十三届计算机辅助系统理论国际会议论文集(EUROCAST 2011)，第13卷，第367-374页。视图:出版商的网站|谷歌学术搜索
4. J.Ries，P.Beullens和D.Salt，“基于模糊逻辑的实例特定多目标参数调整，”欧洲运筹学研究杂志第218卷第1期2, pp. 305-315, 2012。视图:出版商的网站|谷歌学术搜索
5. H. Akbaripour和E. Masehian，“启发式算法的有效和稳健参数优化”，国际工业工程与生产研究杂志，德黑兰，第24卷，第2期2, pp. 143-150, 2013。视图:谷歌学术搜索
6. M. Amoozegar和E. Rashedi，“使用DOE的GSA参数调谐”，收录于第四届计算机与知识工程国际会议论文集，第431-436页，2014年10月。视图:出版商的网站|谷歌学术搜索
7. L.Calvet，A.A.Juan，C.Serrat和J.Ries，“基于统计学习的超启发式参数微调方法，”统计和运筹学交易，第40卷，第5期。1, pp. 201-224, 2016。视图:谷歌学术搜索
8. d . c .蒙哥马利实验设计与分析，John Wiley&Sons，新泽西州，美国，第8版，2012年。视图:MathSciNet
9. O. Maron和A. W. Moore，“Hoeffding竞赛:加速分类和函数近似的模型选择搜索”，出版神经信息处理系统研究进展，第59-66页，摩根考夫曼，圣马特奥，加州，美国，1994。视图:出版商的网站|谷歌学术搜索
10. M. Birattari, T. Stützle, L. Paquete，和K. Varrentrapp，“一种配置元启发式的竞赛算法”遗传与进化计算会议论文集，页11-18，纽约，纽约，美国，2002。视图:谷歌学术搜索
11. B. Adenso-Díaz和M. Laguna，“使用分数实验设计和局部搜索的算法微调”，运筹学第54卷第5期1，页99-114,2006。视图:出版商的网站|谷歌学术搜索
12. P. Balaprakash, M. Birattari, T. Stützle，和M. Dorigo，《f竞赛算法的改进策略:抽样设计和迭代优化》，刊于第四届混合超启发式国际研讨会论文集, 108 - 122页。视图:出版商的网站|谷歌学术搜索
13. F. Hutter, H. H. Hoos, K. Leyton-Brown, and T. Stützle，《ParamILS:一种自动算法配置框架》，人工智能研究杂志，第36卷，第267-306页，2009。视图:出版商的网站|谷歌学术搜索
14. m . Birattari调整元启发式：机器学习的视角，施普林格，纽约，纽约，美国，第二版，2009。
15. S. Smit和A. Eiben，“比较进化算法的参数调优方法”，刊于IEEE进化计算大会论文集，页399-406,IEEE，特隆赫姆，挪威，2009年5月。视图:出版商的网站|谷歌学术搜索
16. S. Russell和P. Norvig，人工智能:现代方法，皮尔森，伦敦，英国，第三版，2009。
17. D. L. Applegate, R. E. Bixby, V. Chvátal，和W. J. Cook，《旅行推销员问题:计算研究》普林斯顿应用数学系列，普林斯顿大学出版社，美国新泽西州普林斯顿，2007年第2版。视图:谷歌学术搜索
18. G. Laporte，“关于车辆路径问题你应该知道什么”海军研究物流第54卷第5期8，页811-819,2007。视图:出版商的网站|谷歌学术搜索|MathSciNet
19. 美国Derigs,优化与运维研究，第2卷，法国巴黎EOLSS出版社有限公司，2009年。
20. R. Matai, S. P. Singh, M. L. Mittal，“旅行推销员问题:应用、配方和解决方法的概述”，刊于旅行商问题:理论与应用， D. Davendra, Ed.，第1章，第1 - 24页，InTech, 2010。视图:出版商的网站|谷歌学术搜索
21. J. K. Lenstra, A. H. G. Rinnooykan, P. Brucker，“机器调度问题的复杂性”，刊于离散数学年鉴E. L. Johnson, B. H. Korte, G. L. Nemhauser, Eds。，第343-362页，Elsevier，阿姆斯特丹，1977。视图:谷歌学术搜索
22. S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi，“模拟退火的优化”，美国科学促进协会。科学，第220卷，第4598号，第671-680页，1983年。视图:出版商的网站|谷歌学术搜索|MathSciNet
23. V. Černý，“旅行商问题的热力学方法:一种有效的模拟算法”，最优化理论与应用杂志，第45卷，第1期，第41-511985页。视图:出版商的网站|谷歌学术搜索|MathSciNet
24. D. Bertsimas和J. Tsitsiklis，《模拟退火》，统计科学，第8卷，第2期1，第10-15页，1993。视图:出版商的网站|谷歌学术搜索
25. j . h .荷兰,自然和人工系统的适应，密歇根大学出版社，波士顿，马萨诸塞州，1975年。视图:MathSciNet
26. G. Reinelt，《TSPLIB:旅行推销员问题库》计算机学报，第3卷，第2期。4、第376-384页，1991年。视图:出版商的网站|谷歌学术搜索

版权

版权所有©2017 Eduardo Batista de Moraes Barbosa and Edson Luiz França Senne。这是一篇发布在知识共享署名许可协议，允许在任何媒介中不受限制地使用、分发和复制，前提是原作被正确引用。