文摘
在这项工作中,我们关注的问题选择低级启发式hyperheuristic方法与离线学习,解决不同的问题领域的实例。的目的是改善性能离线hyperheuristic方法,确定等价类的实例在一组不同的问题和选择表现最好的启发式联系在一起。第一步的方法,提出了一套所有问题的实例,每个实例的通用特征和启发式的性能在每个其中之一被认为是定义向量的特征和分组的类。Metalearning与统计检验是用来选择为每个类启发式。最后,我们使用了朴素贝叶斯和k-fold交叉验证测试一组实例,和我们比较所有结果与著名统计值。在本研究中,方法被应用到测试生产配送车辆路径问题(CVRP)和图着色(GCP)。实验结果表明,该方法可以提高性能的离线hyperheuristic方法,正确地识别类的实例和应用适当的启发式。这是基于统计的对比结果与艺术的每个实例的状态。
1。介绍
在计算机科学中,一个启发式技术旨在解决问题当古典方法无法找到一个确切的解决方案或当他们太慢了。目前,有极大的兴趣从科学界提供特别的启发式解决实际的优化问题。为实现这一目标,有必要问题的先验知识,计算高效的解决方案常常在一个合理的生产时间。然而,没有免费的午餐定理提到[1),没有方法或算法可以解决所有的问题;也就是说,特设启发式通常不是可概括的,他们并不总是工作当应用于其他问题即使他们分享一些相似的特点。这一事实使得研究努力的发展通用搜索方法称为hyperheuristics,其主要特点是,它们独立于问题域。
Hyperheuristics可分为根据他们的学习方法,如没有学习,在线学习(2),和离线学习3]。在组合优化的背景下,hyperheuristics被定义为“启发式选择启发式”[4),或为“一个自动化的方法选择或代启发式解决计算搜索问题,”(4]。根据皮莱(2)的一般性hyperheuristic可以从三个层次:泛化问题的实例,概括为一个特定的问题,和一个泛化关注不同类型的问题,后者是高水平。一些变化hyperheuristics取决于使用的学习类型(例如,在线学习(2)和离线学习(3])或启发式的性质。
hyperheuristics的主要问题之一是提出方法,允许生成和/或选择最低的一组启发式执行好手边的问题和这个启发式组通常由专家选择该领域的研究人员(2]。为了自动选择最佳执行最好的启发式的问题,提出了一种方法称为metalearning [5,6),它的使用在可以找到hyperheuristics Amaya et al。7]。同样,不同的含义和分类法用于每个metalearning之间的交互和优化研究了歌曲等。8]。
因为没有方法或算法,可以解决所有的问题,我们的目标是基于自己的信息问题,算法的性能为hyperheuristics提供这方面的知识。Metalearning生成元知识,我们用它来选择更好的方法可以解决问题。通过这种方法,我们假装提出方法就像人类的智慧。人类可以借鉴的问题,他们的特点、变量,和他们的限制,并阐述分析或识别后,“人类专家”提出了最好的工具和解决问题。
在本文中,我们提出一个方法来确定启发式hyperheuristics通过metalearning和分区的一个子集为解决不同的问题(在下面描述)没有临时调整通过提供信息问题和hyperheuristic启发式的表现。众所周知,正确的描述是选择最佳的启发式的关键(6]。因此,这种影响hyperheuristic设计,这就是为什么在我们的方法,我们决定使用离线学习。Metalearning由两个基本部分组成,metafeatures metalearner;第一个产生的信息问题和解决方案的算法,而第二个使用分组技术。我们的方法超越经典metalearner方法,我们运用非参数统计检验,以确定哪些启发式将提供相同的性能如果启发式的全套。
为了测试我们的提议,我们使用两个不同的领域知名的问题:生产配送车辆路径问题和图着色问题。的生产配送车辆路径问题(CVRP)有不同的限制,如减少距离,时间,能力,和交付。这个问题的目的是找到的subtourn城市,没有重复两个城市在同一旅游或不同的旅游。CVRP状态的艺术,存在不同的变体,考虑这个基本定义和额外的限制。另一方面,标记每个顶点的图着色问题由一个给定的图k-colors和它是一个著名的问题,已经解决了具体方法,启发式metaheuristics, hyperheuristics。虽然可以通过特设启发式解决每个问题,到目前为止,没有通用的方法能够解决这两个问题的所有变体。分区的使用约束满足问题,如大学制定时间表和蚁群,有好的结果(9,10]。虽然有分类的问题,描述和分类的实例下hyperheuristic上下文与metalearning统计检验是一种方法,在文献中没有被探索。
最后,值得一提的是,做一个更好的设计或选择hyperheuristics和预测哪些是最好的算法根据前一个实例的分类,我们建议使用metalearning启发式的统计分析,这将使改善这些问题。我们的建议还提供了信息,让我们了解启发式的表现和hyperheuristics感兴趣的问题。
本文的其余内容包含一个描述部分的相关工作2涵盖启发式评估,hyperheuristics, metalearning。问题的定义和相关理论启发式报告部分3。部分4和5提出的方法。发现结果和发现包括部分中描述的性能比较6。最后,给出了结论7。
2。相关工作
在本节中,我们将给一个视图的启发式和hyperheuristic算法。此外,我们将定义metalearning的一些基本概念。最后,我们将讨论的优缺点提出了方法。
2.1。启发式
我们做了一个广泛的审查不同的启发式方法应用于CVRP和丰富。我们选择共有11个启发式,前一个实验分析后,这些启发式适用于这两个问题下面我们列出他们。
K-flip或K-opt提出了启发式的林和克尼汉在[11)的旅行商问题(TSP)。这种启发式方法是基于通用交换转换,即。与另一个城市,必须改变它的位置在同一旅游。此外,这种启发式方法是TSP(最受欢迎的12];它已经被应用在其他问题,如平面图形、无约束二元二次规划,研究其在坐着MAX-SAT复杂性。两点扰动的k-flip,我们给出一个详细描述这些启发式算法在以下部分。
的k-swap启发式和经常混淆相似k-flip。的K-swap启发式改进它的性能作为微扰移动时,它使用两个或三个运动(13]。
启发式搬到更少的冲突,也称为减少冲突,提出了明顿et al。14]。减少冲突启发式一直在计算机科学应用于不同的领域如hyperheuristics、图着色问题,pickup-and-delivery问题,调度问题。搬到更少的冲突启发式是首先满足的一种变体,唯一的区别是,第一个为另一个随机变量,改变其价值产生最少的成本。
的首先满足启发式是证明贝克(15装箱问题。另一方面,近几十年来,这种启发式方法应用最有名的问题,如本包装、虚拟机迁移问题,削减库存。各式各样的启发式最适合由贝克研究[15]和Csirik [16尤其是],装箱问题中的应用。
Soria-Alcaraz et al。17)提出了大学课程时间安排最好的单一扰动三个启发式(BSP),动扰动(SDP)和双动态扰动作为hyperheuristic池低级启发式的一部分。此外,这些启发式应用蚁群在后来的研究18]。
2.2。Hyperheuristics
我们专注于离线学习hyperheuristics与微扰启发式选择,其目的是收集知识的形式规则或程序,从训练集的实例。通常,离线选择hyperheuristics属于机器学习方法,它被训练来创建一个调谐方法问题域(3]。耶茨和Keedwell19]表明,发现了启发式的子序列在离线学习数据库是有效的问题域。他们用Elman网络计算序列的启发式评估在看不见的HyFlex示例问题,intradomain学习和泛化的结果能够有99%的信心。
hyperheuristics设计中的关键问题之一是启发式池的质量和大小(20.]。Soria-Alcaraz et al。20.)提出了一个使用非参数统计方法和健身景观hyperheuristics设计测量。这种方法是课程时间安排和测试车辆路径问题;他们hyperheuristic提议一个紧凑的启发式池和与一些传统方法制定时间表。在制定时间表问题,他们获得了五个著名的24 PATAT实例解决方案(21]。最后,最近的一份报告Amaya et al。7)记录创建的模型选择hyperheuristics与建设性的启发式。Amaya提出的模型的有效性取决于三角洲的价值观,这是有用的较高的增量。
2.3。Metalearning
metalearning的重要性,研究了机器学习和优化歌曲等。8]。metalearning目标可能关注积累和适应经历一个学习系统的多个应用程序的性能。metalearning字段也被称为“学会学习“(22),它使系统可以帮助通过搜索模式在不同的任务控制利用累积经验的过程。metalearning概念已经存在领域的启发式和metaheuristics茶匙(23)、二次分配问题和hyperheuristics。
另一方面,Gutierrez-Rodriguez et al。23VRP使用时间窗口和提出了一个基于metalearning选择最好的方法为每个实例metaheuristic。除此之外,他们的建议共享和利用离线方案院校和行业的即时的解决方案。他们的主要贡献是提出一组特性描述VRPTW实例和设计一个分类过程,预测最适合metaheuristic为每个实例。不过,他们认为,一组实例的解决方案可以存储,共享,利用离线解决方案预测好新看不见的实例。
本文的目的不是提供一个调查启发式或hyperheuristics;我们的建议略有不同。我们的建议考虑的一些重要方面的研究,包括从耶茨和Keedwell [19]。我们把离线hyperheuristic方法从Soria-Alcaraz et al。20.)和统计的方法来选择一个池启发式从神田等。5]。离线hyperheuristic方法是一种有效的和流行的方法在机器学习领域8]。另一方面,选择一个池启发式的统计方法是有用和可靠的方法,因为它需要从输入数据的统计信息。
3所示。组合问题
我们的方法是一个通用的方法来竞争表现在几个类别的问题。因此,我们使用两个问题域:图着色和车辆路径问题。在下面几节中,我们将回顾这些问题的正式定义以及基准实例。
3.1。图着色问题
演示的图着色问题是一个np难问题提出了卡普(24]。根据(25),正式vertex-coloring图的问题 是一个函数 ,中任意两个顶点 分配不同的颜色, ,和是一组有限的无序对顶点命名边缘,函数着色功能和图表吗存在一个vertex-coloring要求颜色被称为k-colorable。图的着色功能引发一个分区成独立的子集 在哪里 和 。基准实例中可以找到http://mat.gsia.cmu.edu/COLOR/instances.htmlmat.gsia.cmu.edu。上面让分区方法输入设计,可以避免临时修改启发式,因为它只会通过不同的目标函数,充分评估这个问题的实例。
3.2。生产配送车辆路径问题
的生产配送车辆路径问题(CVRP)是一个变种的VRP [26]。在这个问题上,我们有一个无向图 , 车辆,能力,和一组城市 。这个城市的是和每辆车必须访问这些城市从回到这一点。阿尔巴和Dorronsoro27)定义一个距离或旅行时间矩阵 城市之间和 。每个城市有需要的东西吗 。我们表示它的路线 ,和是一个排列的城市,开始和完成在仓库吗 。对于每一个路线, 与 。解决方案的成本问题是每个路线的成本的总和作为 在哪里k的总车辆。这个问题的目的是确定每辆车的成本最低(见方程(1)和(2)旅游距离或出行时间,考虑到最大容量。注意每辆车的硬约束能力和两辆车不能访问同一个城市。CVRP有几个约束和一个特定的正式定义的这个问题。这两个特点让我们运用我们的方法与设计城市分区,其中每个车辆相关的一部分。作为启发式处理解决方案,已经完成和尊重等重要的限制能力,如果违反任何运动或超过这种能力,解决方案是目标函数的惩罚。
4所示。方法
对于我们的方法,重要的是要知道约束建模阶段以来的问题可以解决了分区。API-Carpio方法论和方法提出Soria-Alcaraz et al。28)让我们变换问题的实例与限制,输入到应用提出的方法。MMA矩阵生成通过应用API-Carpio方法让我们想象问题的硬限制和评估访问城市或节点的成本。软约束的问题,提出的方法Soria-Alcaraz et al。28)被认为是在限制的列表。
在本节中,我们描述了方法模型输入数据问题信息用于实验基于API-Carpio方法两个组合的问题。我们集成API-Carpio方法(29日和提出的方法设计的Soria-Alcaraz et al。28]。
4.1。API-Carpio方法
这种方法用于解决大学课程时间安排问题,考虑三个因素:学生、教师、和机构(基础设施)。使用先前描述的几个结构方程的方法。这个工作是最重要的结构之一MMA。这个矩阵是由城市或节点的信息。图着色,我们使用邻接矩阵的信息,而对于CVRP被认为是成本矩阵。表1显示了一个示例的一个MMA的矩阵。该算法构造中给出了这个矩阵(29日]。
4.2。方法的设计
这种方法被杜丽莎(扩展的建议29日提出的)和他们的正式定义是Soria-Alcaraz et al。28]。设计的方法论的索里亚允许我们考虑的目标课程时间安排和满足不同的限制,通过将这些列表的时间和空间限制寻求减少学生冲突。
使用这种方法,使用两个结构考虑限制和变量:MMA矩阵和液体变阻器。液体变阻器的信息可能的限制,可以分配给每个节点或城市。这个列表的一个示例可以在表中找到2。列表显示在每一行的部分,即。,节点可以分配部分1、2、4、5、7或8,但不是在6。算法生成人工液体变阻器的实例中可以找到Ortiz-Aguilar [30.]。
5。Metalearning为Hyperheuristics启发式的选择一个子集
根据Brazdil et al。22)的方法metalearning (ML)是帮助一个算法的选择的一组实例元数据。根据Alpaydin [31日],metalearning的目标是找到一组数据的最佳分类器,并找到最好的分类器的特征数据。在我们的方案中,数据相关的问题不同的问题的实例,以及分类器与启发式的集合相关联。我们的目标是能够选择最佳的一组启发式hyperheuristic的一组实例。在图1,我们将展示一种图metalearning过程获得元知识的启发式的选择(图修改Brazdil和Giraud-Carrier32我们的方法)。
在这项工作中,我们使用metalearning选择的一组启发式hyperheuristics数据集。我们命名的特征集的实例两个问题领域“metacharacteristics”和模型映射到对应的每个实例的启发式组hyperheuristics“metalearner。“在这种情况下,metalearner选择是k - means算法。本文中提出的方法在metalearning阶段包括5个步骤:(我)步骤1:获得的一组实例上工作。在这种情况下,我们作为一个标准来选择那些容易被解决的实例分区。(2)第二步:评估和提取特征实例。在这一步中,启发式的特点和生成的实例。启发式选择适用于这两个问题,这个任务变得简单使用的分区方法,这是因为它允许使用通用输入变量和工作总是限制建模。之后,启发式处理这些通用的输入和解决方案,只有一个适应度函数对应于他们的问题(目标是评估)。(3)步骤3:代metacharacteristics。基于每个问题的特征和启发式的性能应用于所有实例,我们生成的特征向量将元数据。(iv)步骤4:metalearning和启发式的推荐模型。在艺术的状态,研究只局限于应用算法的推荐模型的聚类技术。我们建议将统计分析的聚类算法改进的设计基本的启发式的子集。
5.1。问题定义的Metalearning启发式的选择
考虑一个问题属于作业(GCP)。让 使用低级的启发式的子集,在艺术的状态,来解决这个问题 。我们表示启发式的随机选择 ,应用的解决方案 ,在哪里 ,与减少组启发式, 。
让 ,在哪里是一个空字符串。我们定义递归 在哪里 和 。然后代表了所有字符串的长度 ,形成的符号 。所以克林的闭包是(33]
当省略了连接,得到Kleene +关闭 :
换句话说,是集所有可能的有限长度的非空的字符串生成的符号 。
让是一个启发式选择hyperheuristic离线训练,训练认为集 。培训后,提供了一个方法 低级的最佳的顺序应用启发式,我们将表示 在问题的解决方案 ,这可以提高应用程序的性能 ,在哪里 (17]。
我们把两个问题和属于问题集(GCP)符合三级皮莱提出的普遍性(2)和容易被解决了分区。让 和 使用低级的启发式的子集,在艺术,来解决这个问题和 ,和= 。我们表示一个随机选择的启发式 ,应用的解决方案和 ,在哪里 ,与减少组启发式, 。
启发式选择hyperheuristic来标示 ,考虑了离线训练,训练集,训练后提供了一个方法 低级的最佳的顺序应用启发式,我们将表示 在解决问题提高应用程序的性能的一个简单的吗 ,在哪里 。
我们的目标是提出一个方法提供了 ,以减少子集 的培训,这样提供了一个方法 ,最好的应用启发式的设置 ,我们将表示 ,在解决问题和分别等于性能与应用程序的方法 在哪里 。
为了解决这个问题,每一个启发式的独立应用程序和提出了衡量他们的表现在解决问题和 。统计测试适用于独立的启发式的性能对比,从而从每组歧视和这些启发式获得最低的性能。
接下来,我们将重点描述的阶段从启发式提取特征和实例。我们的方法提高了metalearning阶段(步骤4),应用非参数统计检验,以确定哪些启发式的将提供相同的性能将应用如果启发式的全套。这意味着,如果有多余的启发式方法,可以让他们出去,只考虑那些提高搜索的速度解决这个问题。metalearning过程提出了工作选择的启发式方法包括以下步骤:(1)将存在的问题为基本特征的信息来源。(2)给定一组实例表示 ,为每个实例应用数量的启发式 。结果将内在的特性。使用CVRP,贪婪启发式,这将使我们能够构建可行的解决方案的问题。图着色,我们将与一个随机初始化构造启发式。下一步是应用启发式。可能这一步后,最佳解决方案的实例可以解决由于其复杂性。这意味着可以避免执行一个完整的和昂贵的计算过程与应用程序解决问题的一个简单的启发式。(3)的信息获得点1和2,特征向量将将形成我们的元数据。(4)一个更好的治疗从上一步的元数据,进行以下步骤:(一)使用的模式,将用以下公式(k - means将被推广34]: 在哪里 是原始变量的值(特征)。(b)生成模式的基础上内心的和基本特征每个实例。的基本特征将信息和问题内在特性将获得的健身启发式应用次问题。(5)通过特征向量聚类算法形成类。根据Brazdil Giraud-Carrier [32),k - means是一个简单的学习方法,我们运用进行分组实例的类。确定类的数量形成,我们用斯特奇斯法则,因为数据2的效力,这是近似的一个好方法。确定子类与斯特奇斯规则(35)与 在哪里T是数据的总量。随着距离度量的k - means,我们使用Mahalanobis距离;这个距离属性,比如被非退化的线性变换不变的规模。深入研究不同的指标(36,37)将一个特定的工作调查是否能提高性能的方法。(6)标签每个模式根据每个模式的组数(实例)被分类。(7)再次申请的三个统计检验结果的启发式的问题,根据公式(38]。表现最好的启发式测试等级1,2的第二好的n表现最差的启发式。从这些测试,我们将采取启发式的范围和范围将被视为内在特性。这个信息和类标签,现在他们将形成模式。(8)确定每个类的截点范围的基础上,在这种情况下,它将最小和最大范围的平均值。选择那些通过截止的启发式准则最小集的一部分。(9)输出将启发式每个类的最小集。
这个过程是一个特定的方式,如图所示2。metalearning在我们工作的两个重要方面是启发式和metacharacteristics,低级启发式和metafeatures。
5.2。低级的启发式
hyperheuristic方法的一个重要部分是启发式的选择。本文提出从启发式和问题中提取信息来生成metafeatures [32]。这让我们提高hyperheuristic算法的设计和测试。这个阶段的目的是生成metafeatures启发式的可以有一个更好的性能分别为所有问题实例。这提高了的下一部分hyperheuristic必须选择序列应用程序为每个启发式和它使用启发式的最小池的一个基本组成部分(2]。所有实例,它将被应用*每个启发式。启发式方法被应用到这两个问题和各自的实例如下:(1)K-Flip /简单随机扰动(SRP)( )。一个或多个变量的启发式价值变化(在某些情况下 )另一个可行的价值。GCP的目标是改变某一个节点到另一个的颜色(39]。最后,对于CVRP,运动意味着改变一个城市到另一个特定的车辆(12]。(2)K-Swap /肯普连锁社区/ S-Chain附近( )。它必须选择两个或两个以上的品种,然后交换他们的价值观其中如果可能的话;否则,改变不了。我们交换GCP之前选中的节点之间的颜色。这种启发式方法是使用与茶匙或CVRP相关工作,也称为k-interchange [40,41]。(3)最好的单一扰动(BSP)( )。这种启发式方法根据硬限制的列表选择一个变量(液体变阻器)和改变它的值。这个交换产生一个更好的成本或在最坏的情况下,相同的成本(17]。下次这种启发式方法应用,下一个变量将根据下一个位置选择的最后一个变量的修改。选择下一个节点必须改变颜色根据最后一个变量选择的图着色问题。CVRP必须改变城市车辆的另一辆车。(4)动扰动(SDP)( )。它也被称为静态动态扰动(SDP)。它是基于变量选择与概率分布的频率在过去迭代。这种启发式方法选择一个随机变量和改变它的值(17]。较少的变量变化将有更高的概率被选中。适用于质量,这将是一个节点用更少的颜色变化,CVRP,这座城市几次搬到另一辆车。(5)两个点扰动(2页)( )。它也被称为k-opt,它是一种特殊情况下的K-swap值 。(6)双动态扰动(DDP)( )。这种启发式方法是基于SDP,这收到解决方案,修改变量的值概率分布。所不同的是,初始解的副本保存,最后,最好的两个解决方案[返回17]。(7)搬到更少的冲突(多层陶瓷)( )。选择一个随机变量,它分配的一部分价值生成最小成本(18]。GCP的颜色变化根据另一个提高健身,在CVRP,城市搬到另一辆车的总距离最小的路线。(8)Min-Conflicts( )。启发式选择一个随机变量,它分配部分,生成最便宜的成本(18]。GCP的启发式必须改变颜色从选定的节点到另一个地方,可以改善结果。CVRP,所选城市的低成本必须最小化总距离的路线。(9)首先满足( )。改变一个变量的值到另一个地方,也就是至少重复在其他变量(18),即。,in CVRP, the heuristic will take a city and it will change it to the vehicle that has fewer cities in its route. For the GCP, it will select a node and it will assign the color that is least repeated.(10)更糟糕的是适合( )。它分配最重复的值如果可能的话,在不违反硬约束的随机选择的变量(42]。GCP和CVRP,我们指定一个节点或城市最重复的时隙,颜色,或车辆。(11)Burke-Abdullah (BA)( )。这种启发式方法提出了阿卜杜拉et al。43),它选择一个变量应用先失败或Brelaz启发式(44),根据其值变化,取得了更好的性能通过应用以下算法:最小冲突,随机选择,连续选择,至少限制。
5.3。Metafeatures
描述和一代的特点允许分化成至少两组实例在同一类问题。我们使用的条款和基本特征根据提议由Gutierrez-Rodriguez et al。23]。作为基本特征,这是由这个问题,例如,节点的数量,颜色,汽车,等等,根据每个问题的信息。对于两类问题,不同的数量总结了在表3。
健身的性能值的启发式内在特性的关键。最后,每个实例的模式基本特征+内在特性。最终的模式如表所示4。例如,实例1有一个模式(3、3、8、50,3、2、1,4),和数量根据池启发式(八个特性对于给定的例子)。
6。启发式的方法来确定一个子集
在本节中,我们提出一个新方法,选择和确定的一个子集启发式解决GCP和CVRP实例。我们描述的图形表示方法在接下来的步骤中,我们的方法显示在图3。(1)变量和识别问题的限制。首先,变量和限制问题的确定根据问题目的或目标。模型GCP、MMA矩阵中的值代表的边缘节点的权重。如果有一分之十的特定位置 的矩阵,这表示这些节点之间没有连接。对于图着色,每个节点是彩色的考虑到相邻节点没有同样的颜色。CVRP是与我们的方法由于其目标寻求subroutes旅游的成本(群)必须最低或最便宜的。(2)限制问题的建模。在这两个问题,我们必须设计一个分区节点或城市。首先,它是必要的模型为每个变量在一个液体变阻器的限制,例如,一个节点不能被特定的颜色或颜色的限制城市参观。然后,它必须设计MMA代表边缘或连接节点之间的重量或城市。GCP的邻接矩阵对应于MMA, CVRP, MMA矩阵将矩阵节点到节点的距离。GC,我们液体变阻器构造基于颜色的数量的节点可以标记。以防问题限制了五个颜色,将表中所示的列表2。同样,这个列表将建CVRP,机动车辆的数量部分应该代表名单(见表2)。用于这项工作的问题,这是没有必要精心制作的软限制额外的结构。除此之外,一个广泛的审查和如何建模额外的限制,研究提出的奥尔蒂斯(10)所有可能的情况下和不同的功能细节。(3)应用metalearning部分中描述的过程5。1(4)独立模式(步骤6)的训练集和测试集进行分类阶段。重要的是要考虑至少一个模式中每个类的测试集。(5)用训练集上的分类器对其进行必要的调整。描述和每个实例得到所有模式特征后,下一步是分类器的训练和测试所有实例。我们的方法,我们更喜欢使用一个简单的贝叶斯分类器因为我们的目标并不是比较分类算法之间的性能或为我们的研究设计特别的分类器。NBC简化学习通过假设每个类,所有功能都是独立的(45]。在我们的方法中,我们假设每个启发式性能无关,因为我们每个启发式应用于独立的实验。在前一阶段,每个实验都必须只有一个启发式的运行,因此,我们不适用两个或两个以上的启发式。最后,所有功能在创建数据集实例之前规范化应用分类器。(6)最后,组测试实例将使用分类器分配一个“类”和与其相应的启发式解决它。
6.1。设计和测试Hyperheuristic离线学习K折叠
选择启发式和设计的最小集合的每个类hyperheuristic更多细节,我们的方法考虑了hyperheuristics离线训练,因为它展示了好的结果约束满足问题的一般性解决方案(3]。使用一个随机的建设性的启发式生成GCP的解决我们的问题,和CVRP使用贪婪算法。选择hyperheuristic算法有三个组件:运营商的池(低级启发式),一个高级的搜索策略,并选择操作员的控制机制,这将被应用在每个搜索的步骤。
但是。高级搜索策略
迭代局部搜索算法被用来作为一个高级搜索策略。提出的这个metaheuristic Lourenco et al。46),它是构建嵌入式启发式生成的一系列解决方案。生成的解决方案可能是更好的,如果他们只是随机构造。这个算法的本质是强化一个初始方案,探索邻近的解决方案。所示的算法是算法1,这是取自El-Ghazali [47]。hyperheuristics离线学习领域的,它指的是事实,高级搜索策略搜索方法(一个启发式序列),解决了一组实例然后它适用于一个给定的一组实例,与在线学习,这是指给定序列的建设提出了启发式的实例。
|
6.1.2。选择运营商
扰动阶段(步骤4中的算法2),有必要选择一个变量后,概率分布基础上的频率变量选择在过去迭代。这个简单的启发式允许我们修改方法的解决方案。我们使用相同的hyperheuristic框架,根据每个类,我们给不同的低级启发式。例如,如果类1最好的启发式 , , ,和 ,这些是我们hyperheuristic池。一个类似的过程,为每个类设计完成。这个过程后,我们训练每个hyperheuristic为下一阶段各自的类。
|
7所示。实验结果
本节将详细描述我们的实验图着色和CVRP基准用于本文。我们给的配置实现迭代局部搜索hyperheuristic。最后,我们描述了统计测试来比较我们的结果与实验方法。
我们的方法是在JAVA语言中实现与使用IDE NetBeans IDE 8.2 JDK 1.8。实验是计算机处理器上执行英特尔i7 - 7700 u, 2.6 GHz, 16 GB DDR3内存,和操作系统Windows 10家。这项工作中提供的测试被执行在一个常见的笔记本,一个处理器;这是公开的方法的有效性。
对于每一个启发式,限制100000给出了函数调用每个测试运行实例。我们应用Shapiro-Wilks测试检查数据结果是正常的,因此选择一个更好的代表(平均或中等)。如果数据行为是根据正态分布,平均作为代表,否则中间。
7.1。图着色和CVRP启发式结果
安装7.1.1。图着色
我们使用基准图着色(第二DIMACS提出挑战48]这是测试了41分。在表中5和6我们展示我们的成果。我们表示最好的结果与一个大胆的脸,只有的myciel2实例与应用程序解决了个人的启发式优化。
我们采用了非参数检验来验证每个启发式的表现有差异。表7显示范围获得的三个统计图着色的测试实例。这三个综合测试表明启发式之间有显著差异。获得了最高等级的启发式三个测试和 ,即。,these have the worst performance.和最好的结果的问题,这是因为在这些启发式混合测试获得的最低等级(见表7标志以粗体显示)。每次运行的时间报告在表8在。
7.1.2。生产配送车辆路径问题(CVRP)
三套艺术的状态被使用在41运行和测试:(1)Augerat et al .(设置),9个实例,提出了(49](2)Christofides Mingozzi,托斯(CMT), 14个实例,提出了(50](3)金色,Wasil、凯利和曹国伟(GWKC), 20个实例,提出了(51](4)Uchoa et al ., 9个实例,提出了(52]
在表9,我们显示实例的健身价值和城市旅游以粗体显示,成本最低的地方节点的数量,每辆车的能力,汽车的数量(颜色的图着色)。每次运行的时间报告在表10。
我们采用了同样的程序弗里德曼(英尺)的统计检验,疏远了弗里德曼(AFT)和Quade (Qt)区分的行为启发式集合。我们建立了 和因为没有启发式的性能,建立了之间的区别启发式的表现有差异。表11显示的三个统计测试获得的排名。
在这种情况下,启发式测试和最低等级吗对QT倒数第二的排名,英国《金融时报》。
7.2。选择统计特性和类的测试
根据步骤中提到的部分5。1,我们首先必须确定集群的数量或类分割我们所有的测试实例。在这种情况下, 和 。
我们认为8类和使用 - - - - - -意味着集群和我们预期的均匀分布情况下的集群。的 - - - - - -意味着算法应用的最大数量 ,最初随机起始点。考虑类的均匀分布到集群,我们使用曼哈顿距离实验工作后,获得最好的结果。
表12包含类的细节,每个集群/类的实例数量,GCP(第3列)的数量,或CVRP每课(第四列),最小和最大节点,节点最小和最大数量的颜色。在这个实验,集群1、5、6、7只GCP情况下,集群3、4和8 CVRP实例,仅集群2问题域。
7.3。培训和测试分类器实例的类
hyperheuristics启发式池设计阶段后,我们把我们的数据集分为训练集和测试。训练数据集是由125个实例与15特性(基础+内)和看不见的实例是由15个实例。与朴素贝叶斯分类的结果被发表在表13。
表14包含分类混淆矩阵的过程。我们观察到,对于一些类像3、4、7和8,模式分类正确。其余的类有一些模式分类不正确,但是,例如,1对3的模式类分为5和6中,我们使用相同的底层启发式和池这并不代表下一步的问题。
7.4。设计和测试Hyperheuristic离线学习K折叠
在下一步中,统计测试应用于启发式和将形成我们的实例的特点,图着色,CVRP每个类。在这个阶段,我们选择根据排名的启发式 。例如,如果弗里德曼有一个最小等级相一致和马克斯 ,必须考虑启发式的极限值 。因为启发式11表现最差的数据集,我们不认为这是启发式实验阶段。
表15显示了每个类的排名和启发式健身,例如,1类QT,船尾有相同的启发式 , , , , ,和 ,虽然英国《金融时报》的不考虑 。我们只考虑 , , , , ,和作为一个最低设置。
选择的启发式为每个类可以概括分为五组:(1) , , , ,和(2) , , , ,和(3) , , , , ,和(4) , , , ,和(5) , , ,和
因此,我们设计5算法对这些8类。这意味着hyperheuristic与高级搜索策略是相同的,但启发式池设置是不同的根据这些启发式5子集。我们训练和测试hyperheuristic短的长度池。我们离开hyperheuristics 10%的情况下是看不见的,结果如表所示16。
hyperheuristic配置10迭代局部搜索和100000年的函数调用。GCP实例,我们得到了最优数量的颜色(在表中以粗体表示16)。除了为实例,A-n45-k6、A-n55-k9 A-n62-k8, A-n64-k9, CMT13, GWKC1, GWKC2, GWKC3, X-n148-k46,我们得到接近最优值的最大距离的20%。
7.5。分类的测试实例和应用程序Hyperheuristic到相应的实例
最后,对于14看不见的情况下,我们使用了朴素贝叶斯分类器,它决定了这些实例的类。与相应池后,我们采用了hyperheuristic启发式根据前面的设计和我们获得的结果如表所示17和18。
表17显示了混淆矩阵,TP, FP率,和分类的精度测试。在这些结果中,两种模式,属于五班分类不正确,但这并不影响hyperheuristic解决方案,因为这个类与类共享相同的启发式6。
7.6。统计比较的结果
最后,比较是否有差异结果应用方法和应用方法,没有一个实验进行了hyperheuristics被处决的33倍的整套启发式和100000个函数调用。结果如表所示19。
首先,其次是每组的统计分布结果的类进行了分析,即Shapiro-Wilks测试(53)是应用于确定方法的结果,hyperheuristic没有方法(HHPC)和最优状态的艺术遵循正态分布。∝= 0.05的测试应用。测试结果如表所示20.,数据表所示16,18,19被测试。应该注意,方法的结果只对集群4和5是正常的,艺术的最佳状态的结果只对集群4是正常的,和结果的HHPC集群1,4,5和7都是正常的。
学生的t测试方法和先进的应用。艺术的状态、方法论和HHPC,我们建立了∝= 0.05水平的意义。零和替代假说方法和HHPC如下:(我) :没有差异的表现hyperheuristic方法论和方法(2) :有差异的表现hyperheuristics方法和方法论
对于艺术的方法和状态,(我) :没有差异的表现hyperheuristics和最优状态的艺术(2) :有区别hyperheuristics的性能
测试的统计结果如表所示21。这些值,我们可以观察到以下几点:(我)方法和HHPC。它可以推断出的结果的方法明显不同于hyperheuristics一整套启发式。这意味着方法改进的性能和允许限制的启发式为每个集群。(2)方法和艺术。可以推断,没有统计证据发现方法的结果与最优的状态的艺术,除了集群5和7。这是因为它是有更多的非典型数据或他们严重机密开幕的机会的改进方法。
8。结论
在这个工作中,提出了一种方法来选择低级启发式hyperheuristic方式离线学习面向实例的解决方案不同的约束满足问题。众所周知提议被应用于两个不同的问题和研究的艺术,是图的着色和车辆路径问题与特定的能力,分别GCP和CVRP。
重点是优化的启发式方法,可以应用于不同的约束满足问题hyperheuristic方法。原始的性能信息的启发式获得问题的实例从不同的问题。性能信息用于生成特征向量为每个实例,用于生成问题的等价类的实例。类中的分组允许识别的启发式应用到每个类,从这些信息,减少数量的启发式必要获得良好的解决方案在每个类的实例并减少的总数可以应用于hyperheuristic启发式方法解决问题。
应用GCP和CVRP,启发式的性能信息是通过一个metalearning过程,和这些信息被用来获得的基本和内部特征实例。实例被分为5类使用的k - means算法度量。对于每个类,启发式的设置可以应用到所有的实例,并通过一个过程的分层与截止条件,启发式每个类的数量减少。
培训和测试、朴素贝叶斯分类器和实例的特征信息。hyperheuristic的实验结果表明,可以有效地解决每个实例,每个类,分类器能够预测每个问题的类实例。
识别和降低启发式寻找复杂问题的解决方案是一种优化策略,可以做满意的寻找解决问题的有效的限制。允许提供的方法生成一个框架的通用性,可以训练来解决不同的问题hyperheuristic下同时满足约束的方法。一旦训练,它可以找到好的解决不同问题的启发式的公共基础的实例问题启发式组合效率的解决方案。
最后,该方法可以提高搜索解决方案方面的问题探索多样化的一些组件(如分类算法、指标、启发式和选择标准,这可能是不同设置不同的问题。这些可能性的研究提出了未来的工作。
数据可用性
实例数据用于支持这项研究的结果已经存入图着色库http://vrp.atd-lab.inf.puc-rio.br/index.php/en/,http://archive.dimacs.rutgers.edu/pub/challenge/graph/benchmarks/color/,https://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-instances/。他们可以从相应的作者。
的利益冲突
作者宣称没有利益冲突。
确认
作者感谢学府Nacional de Mexico /我。t·莱昂和瓜纳大学。这项工作是由墨西哥国家科学技术委员会(CONACYT)通过奖学金,研究生446106 (l . Ortiz)和科研补助金:catedras - 2598 (a·罗哈斯)。作者感谢参与Valentin Calzada-Ledesma从西班牙著名优越de Purisima本文的修改和校正。