文摘
一生的最大覆盖问题(MLCP)需要启发式优化方法由于其复杂性。模型的一个真实问题决定了如何表示和运营商解决方案应用于这些启发式。我们的论文描述了适应本地搜索方案及其运营商MLCP优化。运营商源自三个本地搜索算法之前我们提出:LS协会,LSCAIA,LSRFTA。两个步骤的LS计划的主循环可以在三种不同的方式执行。因此,九个版本的LS方法可以获得。在实验研究中,我们验证了它们的有效性。测试用例来自三个基准:SCP1,早些时候提出的,用于我们的上述三个LS算法的研究,和另外两个文献中找到。SCP1的结果表明,该算法基于超图模型方法(协会)是最有效的。剩下的其他算法的结果把他们分成两组:有效的和弱的。然而,其他指标显示,越冗余覆盖的兴趣点(POIs)的传感器,更有效的微扰法方法受细胞自动机(CAIA)。这些发现的优点和缺点暴露问题特定的步骤应用于LS算法。
1。介绍
无线传感器网络(网络)在许多应用程序中至关重要的部分解决方案:军事、战场监视、和公民,包括预测系统、环境观察,或栖息地监测(1]。传感器可以集成到大量的电子设备和机器。此外,由于半导体和微机电技术的进步和计算机的微型化和传感技术,传感器和微控制器都很小,低功率消耗,便宜。因此,网络可能由大量的小而强大的设备在大领域的合作。轮的目的是监控一个地区或一组目标收集有价值的信息建模和预测情况的区域或控制资源的使用。在网络组成的小型设备,监控质量成为一个能源效率问题,由于电池容量有限。
传感器网络寿命最大化技术依赖于一个问题的两个主要组件模型。首先是目标,例如,网络的生命周期优化,报道,连接,或传输参数。第二个是WSN设计约束,例如,通信介质、资源限制、容错性和自组织,QoS需求,或迁移和部署2]。在我们的研究中,我们关注问题的网络寿命最大化,也就是说,最大化网络的不间断时间间隔满足覆盖率超过一定阈值的水平在某些资源有限的约束。我们的研究问题简化网络模型,传感器仍固定一旦部署,和他们的连接总是得到保证。我们假设单个传感器位置不可行是因为环境条件,例如监控灾区或战场。因此,传感器是随机分散在监控领域。传感器有一个有限的电池容量。因此,排水后,他们应该更换或充电。但是,我们假设这两个选项适用由于操作条件。所以,一旦能源储备耗尽,传感器被认为是挽回的失去网络。网络是配备一个外部固体计算单位负责网络设备之间的优化调度和分配任务。
我们假定传感器有统一的电池和传感范围和监控的目标也叫的兴趣点(POIs)。当传感器广泛的数量和他们的监视范围重叠,一些传感器可以在所需水平的报道仍满意。在这种情况下,优化的目标是找到一个传感器与最大完工时间最长的活动安排和保证足够的覆盖水平。这类问题被称为一生最大覆盖问题(MLCP)。的方法解决MLCP是基于不同型号的实际情况;因此,他们有不同的解决方案的结构和复杂的问题。
在本文中,我们开发本地搜索策略丰富了我们早些时候提出问题特定的程序源自三个算法:LS ,LS ,和LS 。策略共享相同的执行计划。一开始,他们先找到一个可行的计划,变成了一个初步的解决问题的办法。然后,迭代,他们生成邻国并试图改进它。新解决方案以其祖先的地方,当我们获得改善。这些策略的优势在于邻居代(所谓的扰动)和细化程序,利用一些模型相关的属性。
近年来,许多启发式方法提出了;因此,很自然地,一个想法出现验证组件组成的混合启发式算法的效率不同的起源。不幸的是,有些方法不共享相同的实际问题的模型和相同的一组约束。因此,他们融入一个方法是一个重要的任务,有时甚至是可疑的。然而,这不是LS ,LS ,和LS ,方法共享相同的模型的实际问题和解决方案的结构表示。因此,选择一个可以很容易地使用问题特定的步骤可交换的构建块。最终,我们构造的九个本地搜索策略通过交换两个步骤:扰动和细化,从三种方法。然后,我们评估他们的性能实验。
本文的主要贡献在于生成9启发式,基于构件的来自其他三个现有的方法,并通过实验验证其效率。我们使用三个基准测试启发式的表现:SCP1,我们以前的出版物中提供3- - - - - -6];基准从[7,8];和基准(9]。
本文组织如下。相关工作简要讨论的部分2。部分3正式定义了一生的最大覆盖问题(MLCP)。本地搜索的方法是引入部分4。部分5描述了我们的实验对MLCP LS算法。我们的结论给出了部分6。
2。相关工作
大多数MLCP解决方法是基于两阶段方法。在第一阶段,我们解决目标覆盖问题,发现的最大数量传感器组,每组可以单独完成报道任务。在第二阶段,我们解决集合覆盖问题,找到最优调度的集覆盖在第一阶段获得的。集有关的约束完全覆盖POIs提议的出版物,例如,在[10),后来在[放松11)通过引入所需的最小覆盖的比例限制。
覆盖集的最小基数,可以分离或non-disjoint。分离集,每个传感器都可以包括在一个覆盖集的最多,而在non-disjoint集,没有这样的限制。在[12],作者介绍了分离设置封面(DSC)问题,也就是说,问题的发现的最大数量不相交的封面,在每一个封面是一组在一起监视所有POIs的传感器,并证明其np完全。情况的复杂性non-disjoint套覆盖进行了分析(13),最大设置封面(MSC)定义问题。这是一个确定的问题non-disjoint覆盖最大化网络生命周期 ,在哪里 ,时间间隔而吗 - - - - - -封面是活跃的。的作者(13]证明了MSC也是np完全问题。
选择论文MLCP优化分离和Non-Disjoint基于集合覆盖方法展示在表1(DSC)和表2和3(NDSC)。传感器的信息活动调度策略对其他传感器网络生命周期优化定义,读者被调查和专著,例如,(1,2,35,36]。
3所示。一生最大覆盖问题(MLCP)
3.1。真实的传感器网络的模型
我们研究的主题是一个固定同质传感器网络监测的兴趣点(POIs)。这些传感器是随机分布在监测区域。传感器的电池容量有限。出于节能的目的,一些传感器可以被关闭的时候。我们提出一个模型的网络活动,我们认为时间是离散的。在每次槽,一个传感器可以打开或关闭。当一个传感器,其能源消费是可以忽略的。当一个传感器被激活时,它消耗了一个单位的能源在每一个时间段。时间段的数量时,传感器可以活跃,也就是说,传感器的初始电池负载,用 。
传感器的模型被认为是简化。在现实生活中,电池的工作时间取决于周围的温度和电池是如何使用的。当我们经常打开和关闭它,它排放超过当我们保持了很长时间。我们忽略这些问题在这个研究。
我们假设每个POI都可以由至少一个传感器。一些POIs的感应范围内多个传感器。自一个活跃的传感器覆盖每一个POI的感应范围,这意味着并不是所有的传感器必须是活跃的。此外,许多应用程序并不需要监控所有POIs的时间。通常足以随时监控80或90%的人。我们称之为价值所需的水平的覆盖和表示的 。我们要保持这种级别的报道,但为了节省传感器电池,我们想保持覆盖水平接近越好。它不应超过超过公差的因素(通常2 - 5%)。
在现实世界中,一些传感器不需要监控可能需要保证网络中的通信。我们简化模型假定稳定传感器通过网络连通性一生和微不足道的精力花在沟通。
3.2。正式的描述
让我们制定网络最大化关于调度问题,提出了在(37]。我们考虑并行的机器,它代表的传感器 和POIs从 。每台机器已分配的任务组成的POIs的子集。的 - - - - - -th任务包含POIs位于的监测范围 - - - - - -th传感器: 。一个 - - - - - -th工作 ,在哪里 ,同时包括正在执行一些任务安排在一个时间段。任务包括在一份工作并不是随机抽取的。他们确定一组机器积极执行这份工作时。也就是说,它们是一组传感器的选择标准是POIs的请求数量。每个位置都有其持续时间 ;因此,安排时间是乔布斯的总和时间*: 。在进一步考虑,为简单起见,我们假设等于一个时间单位,因此安排考的总数是一样的工作时间表 。
在我们的实验中,一个网络活动时间表表示为0 - 1矩阵行相应的机器和列对应的工作。元素的行和列= 1(分别地。,0) when the machine(职责。,off) in job 。
所需的覆盖水平约束表示基数之和POIs的任务分配给活跃的机器的工作应该等于或超过 ;也就是说,t
此外,对于所有的机器,处理时间不应超过极限 :
目标是最大化的安排时间所需的水平没有超过最大的覆盖率和处理时间的机器 。
4所示。总体方案的本地搜索
在我们以前的论文4- - - - - -6),我们提出了解决MLCP三个启发式算法。他们都遵循本地搜索算法中给出的一般方法1。他们每个人都使用不同的方法在本地搜索的三个步骤:初始化(步骤#1:1号线)、微扰(步骤#2:第3行),和细化(步骤#3:4行)。
|
方法在初始化阶段提出的算法有以下名称:随机和微调的方法(RFTA),细胞自动机方法(CAIA)的启发,和超图模型方法(协会)。因此,我们表示LS算法提出了相应的论文,分别由LSRFTA,LSCAIA,LS协会。这个符号第一次出现在[3),而不是原来的论文(4- - - - - -6]。在所有的初始化步骤方法,我们从一个空的计划表,并添加新的插槽,一个接一个。只是用于获得一个新的槽的方法是不同的。添加一个新的槽计划降低了电池的传感器活跃在这个位置。
在初始化步骤终止时(步骤#1算法1),一些传感器通常剩下空电池。然而,甚至打开所有这些传感器并不能保证足够的覆盖水平。因此,我们不能把这作为另一个槽的配置设置。这些传感器的微扰和细化步骤(步骤#2,#3算法1)。在扰动步骤中,我们要么删除一些槽或修改组活跃传感器在某些时段,添加传感器从上面提到的设置和删除。当我们删除整个槽的时间表或关闭一个或多个传感器在一个位置,我们恢复能量。这种方式,传感器与非空集电池增长,我们希望从这组获得一个或多个新槽。在细化步骤中,我们使用一个方法初始化步骤中创建新的插槽,并将它们添加到修改后的时间表。如果新的时间表是超过最初的一个,它取代了最初的一个。摄动和细化步骤重复直到满足终止条件。
删除一些槽时间表的摄动一步可以以两种方式完成。在[4随机选择),这样的插槽。在[6),首先,我们试图关闭每一个活跃的传感器槽。关掉它的决定是由一个低概率阈值。接下来,如果删除一个活跃的传感器从槽使这个位置是不可行的,整个槽被删除。我们的实验表明,多个插槽是即使是一个非常低的概率,比如0.0005。因此,这种方法的扰动比前者。
在[5),我们使用一个完全不同的扰动的方法。我们添加的传感器设置与随机选择的非空电池槽但只有当添加一个额外的传感器增加覆盖水平。如果不是这种情况,我们必须选择另一个位置传感器。当我们使用所有的传感器,我们试图从修改后的槽删除其他传感器覆盖水平接近越好。
因此,对于每一个本地搜索的三个步骤,我们有三种不同的方法进行。每一步通过选择其中一个方法,我们得到了27个不同的变体。我们将使用的名称调用这些算法每一步的起源。例如,[协会、RFTA CAIA)表示一个从LS算法的初始化过程算法生成初始调度,源于LS摄动一步 ,源于LS和细化步骤 。[RFTA, RFTA RFTA]与LS是相同的算法因为所有来自这个算法三个问题特定的步骤。
5。实验
评估新算法的性能,我们对其中一些人进行了大量实验。我们决定总是使用相同的方法来生成一个初始的时间表。这种方式,组27节中描述的算法4已经减少到9因为我们的算法只在不同的主循环算法的步骤1。的初始化步骤中,一个方法生产时间表温和的质量将是合适的。它应该给主循环更多提升空间这些时间表,从而突出算法之间的性能差异。因为协会通常生成最扩展计划,通常很难改善,我们选择在剩下的两个methods-RFTA和CAIA之间。我们决定使用CAIA,这个选择有点武断。最后,我们比较实验9版本的LS算法的形式(CAIA, , ),代表协会之一,CAIA, RFTA。因此,对于一个问题,所有版本的主循环从相同的初始计划开始。循环的终止条件是500次迭代的限制。
从现在起,我们跳过初始CAIA符号的部分4和参考测试算法只给摄动一步的起源和细化步骤。相比九算法[协会,协会],[协会,RFTA], [CAIA协会],[RFTA,协会],[RFTA RFTA], [RFTA CAIA], [CAIA协会],[CAIA RFTA], [CAIA, CAIA]。
在实验部分中,我们使用基准SCP1提议在我们以前的出版物,也与两个外部基准测试:一个来自[7,8)和其他从(9),选择由于兼容问题定义和优化标准但不同定义的测试用例。
实验在惠普工作站Z2 G4设定触发器与英特尔®™核心i7 - 8700 CPU @ 3.20 GHz和16 GB的RAM和Windows 10 Pro。申请模拟是实现MS Visual StudioC+ +。
5.1。测量方法
最好的测量我们的LS算法的效率将会是一个比较获得问题解决方案的最优解。在本例中,我们将比较LS算法返回的行程的长度与一个最优调度的长度给定问题的实例。不幸的是,我们不知道最佳的解决方案,因为它是不可能去计算他们在合理的时间由于问题的计算复杂性。因此,我们决定把我们解决问题的最佳理想解决方案实例。最佳LS算法产生的次优的解决方案是使用这些协会最初的时间表。由于最初的时间表由协会长比通过其他方法,我们希望得到的时间表后真正接近最优应用LS改善他们。最佳非最优时间表的长度被用作参考价值评估产生的质量百分比进度我们九LS算法。
此外,我们测量的平均百分比提高最初的时间表的长度,获得主循环的算法1。被减去的长度计算初始调度长度的最终日程和差除以初始计划的长度。每一类问题,获得的值是平均值问题实例的数量。
5.2。使用基准SCP1性能比较
在我们的第一组实验中,我们使用基准SCP1(传感器覆盖问题,设置1号)中引入我们的出版物(早些时候3- - - - - -6]。
5.2.1。基准SCP1
SCP1由八类问题。有2000个传感器的传感范围的抽象单位之一。监视的区域是一个正方形。其大小不同于13日至28日抽象单元(16个可能值:13日,19日,22日,25日和28)。POIs放置在一个矩形或三角形网格的节点。由于网格节点之间的距离与面积大小,一起成长的节点数量为所有类型的SCP1相似。然而,只有80%的网格节点POI。POI位于节点只有在0和1之间的随机生成的数小于0.8。
因此,相同的测试用例的实例可以有不同的POIs的数量。三角网格,这个数字是在199年至240年之间,而对于矩形网格,它是在166年和221年之间。传感器的坐标位置是获得使用一个随机发生器或荷生成器。最后,测试类有以下配置:1。 ,2。 ,3所示。 ,4所示。 ,5。 ,6。 ,7所示。 ,8。 ,在哪里意味着一个三角形网格的POI的地点,意味着一个矩形网格,和意味着哈尔顿和一个随机发生器的传感器位置。我们生成40每一个类的实例。
图1描述了箱线图(最小值、下四分位数、中位数,上四分位数,和最大)的最大最小距离(MMD) (38)的值集传感器和POIs的实例。准确地说,箱线图显示了多党民主运动的均匀度测量和计算如下: 在哪里 之间的欧几里得距离吗和 , 是一组传感器的位置和是泰森多边形法多边形的顶点集POIs的设置位置。图中的值增长随着侧监测区域的大小的增长,这是合理的。此外,区域的大小同一侧,值情况下POIs位于三角形网格的节点小于的POI的情况下应用矩形网格分布。
图2显示平均数量的传感器覆盖0,1,2,3,4,5,超过5 POIs SCP1的八个测试用例。一个可以看到数量的传感器覆盖更大数量的POIs减少随着一边监控区域的大小。边的大小增加时,邻居传感器监测区域的重叠部分萎缩,甚至一些消失,所以共享POIs的数量减少。上节课的问题,几乎75%的传感器盖只有一种芋泥。
在我们的实验中,我们假定所需的覆盖水平80或90%,而宽容的因素是5%。同一组实验重复了五种不同的值-10、15、20、25和30。
5.2.2。意味着规范化长度的进度和质量百分比的时间表
返回的时间的长度LS算法问题是我们实验的自然结果。然而,所有问题实例的平均长度返回从一个特定的类不能测量算法的质量好。最优调度长度为后续实例和的值可能不同 。输出值为目的的兼容性,我们归一化调度长度。我们假设电池的寿命是一样的,但不同数量的传感器活动间隔为代表可以用于调度。我们认为, ,电池寿命分为30间隔和槽需要一个单位。因此,安排时间等于完全的槽数的时间表。因此,对 ,一个槽需要三个时间单位;为 ,两个单位;为 ,1.5个单位;和 ,1.2单位。最终,规范化的长度安排代表安排考,也就是说,插槽的总数乘以时间单位的数量每槽。
另一个措施就是计算每个结果质量对最著名的次优进度百分比,然后这些百分比平均超过所有的问题在一个类的实例。
表4礼物的意思是考安排特定类的测试用例。最大完工时间平均计算的总和所有实例和考获得的所有值除以 (一个类的实例的数量乘以不同的值的数量问题 )。表5所示,对于每个SCP1八类的,最好的平均百分比品质计划返回的LS算法(顶部表)。它还显示了平均百分比提高LS返回的计划阶段的长度对返回的时间的长度初始化阶段(下表)。表4和5现在的结果 。表6和7显示相同类型的结果表4和5但假设 。
从这些结果可以看出,(协会,协会)通常是LS最好的版本。其他三个LS算法,[协会,RFTA], [CAIA协会],[CAIA协会],也有效,其余五个LS版本给更糟糕的结果将称之为弱的方法。然而,对于 ,[RFTA,协会]比其他弱方法有效但不太好。因此,所有的LS算法从LS与微扰法产生一个相对良好的安排,无论什么方式用于改进扰动后获得的时间表。
然而,我们的研究结果还表明,(协会,协会)并不总是最好的方法。在表4,在三种情况下,值(协会,RFTA)略优于的协会,协会。此外,在表的前三行4和5,的值(CAIA协会]比对应的值(协会,RFTA)。在表中6和7,的值,CAIA协会总是比[CAIA协会],在三种情况下,比相应的值(协会,协会)。此外,过去五类SCP1,的值(协会,RFTA)比(协会,协会)。从这些观察中,我们只能说,一群算法比另一组,但我们不能说一个特定的算法总是比另一个。
比较结果由[CAIA协会]和[RFTA,协会],有人可能会问为什么第一种方法属于组有效的,而第二个可以弱。一个可能的解释是,LS的摄动法从LS远远比一个吗的槽数删除从原来的时间表。因此,在[CAIA协会)的情况下,细化步骤开始更高的能级电池可用的传感器。这允许一个有效的协会方法改善短输入进度远远超过在更多的情况下扩展输入计划但更少的能量电池可用的传感器。
数据3和4现在的箱线图的考四好LS算法返回的时间表SCP1基准分别为80%和90%。这些图表显示,所有统计参数值(最小值、下四分位数、中位数,上四分位数,最大)(协会,协会)通常比其他三个算法相应的值。
在图3上课,只有7中,最小的值,最大,四分位数(协会,RFTA)比的协会,协会。类8,最小的值,下四分位数,和中位数(协会,RFTA)比的协会,协会,当上四分位数的值和最大值相等。第4类,中位数和上四分位数(协会,RFTA)比的协会,协会,但最低,下四分位数,最高是相等的。因此,没有这两个算法可以产生一个时间表的时间比最好的时间表,但[协会,RFTA]更多回报更好的结果。类1 - 3,最大CAIA协会,是比最大的协会,协会,但是其他箱线图参数(CAIA协会]不如(协会,协会)。[CAIA协会]有一个更广泛的四分位范围和分布的结果。这是由于从LS微扰法的性质这是比LS所使用的方法更随机吗 。因此有时,它可以产生更好的使用的传感器比LS的更系统化的方法 。
在图4类4 - 8,最小值,最大值,和四分位数(协会,RFTA)比的协会,协会。此外,类4和8,几乎所有参数的值(协会,CAIA)比的(协会,协会)(唯一的例外是在课堂上最大8),类8 CAIA协会,有四分位范围小于(协会,协会)。对于类7,相应参数的值[CAIA协会]和[协会,协会]几乎是相等的。因此,从平均值箱线图图确认结论。
5.3。使用两个基准性能比较
来验证我们的结果部分5.2,我们决定使用其他作者提供的基准进行更多的实验。我们选择了相同的两个基准我们用原来的LS算法用于实验 ,LS ,和LS(3]。
5.3.1。在[Tretyakova等人提出的基准7,8]
我们选择了四类问题提出了7,8]。在所有情况下,监控区域是一个广场,一边100抽象单位的大小。在三个类(8),有100个POIs的传感器数量是100,200,300(病例#1,#2,#在类(3)。7),我们有400 POIs和100个传感器(案例#4)。其余的参数也相同的值(7,8];也就是说, ,传感范围是20抽象单位, 。表8介绍了测量长度的时间表。表9显示的平均百分比品质最好安排返回我们的LS算法(顶部表)和平均长度的百分比改进LS阶段对返回的时间表安排返回的初始化阶段的长度(下表)的四类指标的问题,假设 。
这组实验结果类似于我们的结果与基准SCP1早些时候。(协会,协会)总是能给出最有扩展的时间表。算法(协会,RFTA], [CAIA协会],[CAIA协会]比(协会,协会),但明显比其余的五个方法。
与SCP1以来在实验中,我们的两个值执行计算 ,80%和90%,我们也做了同样的测试用例(7,8]。表10和11显示的结果类似的表8和9但获得 。
这组基准,降低从90%到80%的相对性能没有改变我们的LS算法三组。然而,相对性能的三个有效的算法已经改变了。
数据5和6返回的时间表显示箱线图的长度的四好指标提出的LS算法(7,8)与分别为90%和80%。在图5,一个可以看到的最低标准(协会,协会)总是大于或等于最大的其他三个算法。此外,结果(组织协会,协会)一个小得多的四分位范围比其他算法。时间表的长度不太分散,证明的高稳定性(协会,协会)的变体 。在图6,所有参数的值(协会,协会)比其他算法相应的参数。然而,对于基准的四分之三的类,结果(CAIA协会]最小的四分位范围。少分散时间的长度证明的高稳定性[CAIA协会]变体 。从平均值,箱线图图确认结论。
5.3.2。在[Manju等人提出的基准9]
的作者minimal-heuristic方法(9)提出以下为实验算法解决MLCP设定的基准。监控区域是一个广场,一边150抽象单位的大小。POIs和传感器随机分布在这个区域。5测试用例(1.1 - -1.5),我们有100 POIs传感器的数字是50、100、150、200和250年,分别。在未来5测试用例(2.1 - -2.5),有150个传感器,虽然POIs的数量是20,40岁,60岁,80年和100年。在[9),抽象单位和传感范围是70 。需要完全覆盖是合理的因为这组基准给更多的冗余覆盖POIs的传感器;,大量的传感器覆盖个人比SCP1 POIs的基准(7,8(有关详细信息,请参阅下一节)。我们使用 。
表12给我们的结果LS的基准策略(9]。表的顶部13显示的平均百分比品质最好安排返回的LS算法。在表的底部部分13长度的比例,我们现在意味着改进LS阶段产生的时间表关于时间表的长度返回的初始化阶段。
从这些结果可以看出,组织协会,协会仍然是赢家。[CAIA协会)是第二个最好的LS方法9 10例。传感器数量的增加(这意味着覆盖率也增加的冗余),[CAIA RFTA]变得比[协会,RFTA]。
因为在我们的实验与基准设定SCP1和基准从[7,8我们使用等于80%和90%,我们也执行测试的数据集9使用相同的值 。对于这些测试用例,可供选择的传感器的数量活动配置满足覆盖率层次相对较高是由于高冗余POI的报道。降低使这些配置的数量更大。的结果 表中给出14和15虽然结果 提供的表16和17。
在这组实验中,[CAIA协会)是最好的LS算法在所有情况下。为 ,(协会,协会)是第二个测试用例2.1中最好的。在所有其他测试用例等于80%,等于90%,第二个最好是[CAIA, RFTA]。第三是[CAIA, CAIA]。因此,对于等于80%或90%,使用的微扰法CAIA总是使结果优于其他两种方法。有趣的是,对 ,其余6 LS算法(包括[协会,协会])给一个相对提高不到1%。
数据7,8,9返回的时间表显示箱线图的长度的四好指标提出的LS算法(9)与分别为100%,90%,80%。在图7[协会,协会]总是给予最大的最小值,最大值,和四分位数。[CAIA协会]和[CAIA协会]四分位范围通常小于[协会,协会]和[协会、RFTA]。小的四分位范围值(,CAIA协会)的平均值低于平均值的结果返回的其他算法意味着[CAIA协会]从来没有给这个基准和好的结果 。在图8[CAIA协会)不仅具有最高的所有参数值也几乎总是最小的四分位范围(仅为1.1类,[协会,RFTA]有一个较小的四分位范围)。减少从100年的90%改变了从LS winner-more随机摄动方法在这种情况下被证明是更好的。最后,在图9(CAIA协会]又最高的所有参数值,通常最小的四分位范围。然而,在这种情况下,四分位范围为所有四个算法接近对方。一次,箱线图图从平均值确定结论。
5.4。什么会影响算法的有效性?
5.4.1之前。覆盖的冗余传感器POIs的基准
解释我们九LS方法的相对性能的差异在不同的基准,我们研究了传感器的数量能够控制特定POIs SCP1和基准从[7- - - - - -9]。我们的研究结果提出了数字10- - - - - -12。
数据10和12显示,在测试用例从SCP1和(7,8),可以监控每个POI不超过50个传感器,在有些情况下,甚至不超过20个传感器。另一方面,数字11显示在测试用例(9),就可以观察到许多POIs 100多个传感器。这高监控冗余使得发现掩盖POIs更可控的,甚至 。
我们从上面的因素得出微扰法用于LS比其它两种方法更有效时所需的形成有许多可能性给定组POIs的掩护。当这些选项的数目减少由于更高的价值或少的传感器,LS的摄动法变得更好。LS的微扰法的优势在一个从LS当有很多冗余覆盖的POIs可能是前删除比后者更槽从原来的时间表。当类似的法律覆盖的数量变大,有许多的可能性创造一个有效的计划。消除传感器电池插槽和恢复更多权力给细化方法更多的空间来显示其有效性和改善原来的时间表。另一方面,当POIs的冗余覆盖减少,协会更好的更系统化的方法。
我们也注意到太多的冗余覆盖POIs的传感器是不可取的在现实生活中由于成本的增加。当然,最终的冗余水平主要取决于特定的应用程序。
5.4.2。优点和缺点的扰动
从LS微扰法的性能良好来自这样一个事实:这个方法不删除单个槽从原来的时间表。相反,主动传感器的方法只改变设置选定的时段。因此,传感器的设置与非空电池变化。它开辟了新的可能性,产生一个额外的插槽在细化步骤,这就足以获得更多扩展的时间表。另一方面,从LS的摄动方法和LS删除槽从最初的时间表。这意味着在细化步骤,最低目标是创建至少尽可能多的新槽在扰动被移除。当我们成功了,我们可以更进一步,尝试产生更多的槽,使新计划了。它可以发生,然而,我们不能得到尽可能多的额外的插槽。尽管细化步骤执行,我们得到一个更短的时间表。槽的槽或传感器随机选择删除,所以我们的成功取决于运气。正如我们上面提到的,当有很多冗余覆盖POIs的传感器,我们把许多槽从最初的时间表,删除右槽的机会,最终获得更多扩展的时间表生长。
6。结论
在本文中,我们提出了27个本地搜索算法解决MLCP和研究9的相对性能。本研究的起点是三LS算法在我们的论文: , ,和LS 。
局部搜索方法包括两个主要步骤:生成一个初始解问题,寻找它的邻居。第二步可以分为两个子步骤执行迭代:原始解决方案和改进的扰动扰动的结果。通过这种方式,我们有三个问题特定的步骤在我们MLCP LS算法。通过交换这三个步骤之间的三种基本算法,我们可以得到27个不同版本的解决MLCP LS。
我们的研究研究这些版本的相对性能仅9总是使用CAIA生成初始问题的解决方案。实验研究中,我们使用基准SCP1(早些时候提出的在我们的论文)和标准提出了(7- - - - - -9]。
我们计算的平均长度安排返回的LS算法,意思是品质最好的比例安排返回的LS算法,和平均长度的改进进度百分比由LS阶段对时间表的长度返回的初始化阶段。此外,我们分析了箱形图的长度返回的安排四个最好的LS算法。
我们的实验结果表明,SCP1基准和标准从[7,8),最好的一双摄动和细化方法通常是一个用于LS ,即。,(协会,协会]。方法[协会,RFTA], [CAIA协会],[CAIA协会]也有效,而其余的组合给出更糟的结果。然而,实验的基准(9]给出不同的结果。当我们假定 ,(协会,协会)仍然是最好的方法,但是对于等于80%或90%,LS的摄动方法给出更好的结果。我们认为越冗余覆盖POIs的传感器和较低的价值 ,更有效的LS的摄动法 。当这种冗余或低较高,LS的摄动方法吗变得更好。你可以询问的阈值从LS的摄动法变得比LS的方法 。结果表明,该值是problem-dependent。这取决于POIs的冗余覆盖传感器。然而,没有哪条规则定义这个阈值可以确定的基础上,提出实验。它可以发现只有通过进行实验与给定类的问题。
数据可用性
使用的数据来支持本研究的发现可以从相应的作者。
的利益冲突
作者宣称没有利益冲突有关这篇文章的出版。