没有合适的资源?快使用搜索试试~ 我知道了~
埃及信息学杂志22(2021)505混合估计分布算法求解设施布局问题AmaliaUtamima智能电气和信息技术学院,Institut Teknologi Sepuluh Nopalan,印度尼西亚阿提奇莱因福奥文章历史记录:2020年6月30日收到2020年9月15日修订2021年4月11日接受2021年4月30日在线提供保留字:估计分布算法设施布局问题混合算法安全工作A B S T R A C T估计分布算法(EDA)是一种进化算法,它使用概率模型来创建候选解决方案。为了避免EDA算法的早熟收敛,前人提出了多种混合算法。本研究对EDA中的几种杂交变量进行了客观值描述性统计的比较研究本研究还提出了一种新的混合方法,命名为自适应EDA(AEDA),通过调整EDA的结构,通过增加彩票过程,精英策略,和邻域搜索。将所提出的AEDA算法、几种混合EDA算法以及遗传算法和禁忌搜索算法应用于制造业中的设施布局设计问题--增强设施布局问题(EFLP),分析了正在比较的混合EDA是EDA加GA(EDAGA),EDA加粒子群优化(EDAPSO),EDAPSO加TS的组合(EDAhybrid)和AEDA。实验结果表明,与其他算法相比,AEDA算法在求解所有EFLP实例时都能显著提高解的质量。©2021 THE CONDITOR.出版社:Elsevier BV代表计算机和人工智能学院埃及开罗大学。这是一篇CC BY-NC-ND许可证下的开放获取文章(http://creative-commons.org/licenses/by-nc-nd/4.0/)上提供。1. 介绍估计分布算法(EDA)是一种进化技术,它从总体概率分布的评估中再生新的候选解,以获得更有效的搜索。EDA存在缺乏多样性的问题,这导致其解决方案的过早收敛[1]。以往的研究提出了各种混合的EDA与其他的并行算法或元并行算法,以避免局部最优。应用EDA杂交技术解决了不同类型的超市选址问题[2]、农业路线规划问题[3]和车辆路线规划问题[4]。该算法的结果被证明是提供实用的解决方案的问题。尽管杂交的效果的EDA来解决各种问题,没有研究比较,*通讯作者。电子邮件地址:amalia@is.its.ac.id开罗大学计算机和人工智能系负责同行审查不同类型EDA杂交的溶液质量。因此,本研究对几种不同的EDA杂交进行了比较研究。单行设施布局问题(SFLP)被归类为NP完全问题,并且需要一种启发式方法来提供近似最优解[5]。增强设施布局问题(EFLP)是SFLP的扩展,增加了安装成本和安全约束[6]。实验结果表明,EFLP的几个实例的解决方案仍然可以改进。因此,EDA的新的变体被提出来处理这个问题。本研究测试所提出的算法,解决EFLP的实例。本文的主要贡献是对EDA的杂交算法进行了比较研究,提出了一种新的EDA算法--自适应EDA(AdaptedEDA,AEDA),并将其应用于EFLP数据集。本文的组织结构如下。在第2节中回顾了以前的研究,而在第3节中描述了问题。该方法是由AEDA的描述,EDA的杂交,遗传算法(GA)与禁忌搜索(TS)在第4节。第5节对实验结果和对比研究进行了记录和分析。最后,根据第六节的结果分析,对本研究进行了讨论和总结。https://doi.org/10.1016/j.eij.2021.04.0021110-8665/©2021 THE CONDITOR.出版社:Elsevier BV代表开罗大学计算机和人工智能学院。这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。制作和主办:Elsevier可在ScienceDirect上获得目录列表埃及信息学杂志杂志主页:www.sciencedirect.comA. 歌间埃及信息学杂志22(2021)505506.XXnn22. 文献综述EDA被归类为一种随机优化方法,它从一组有希望的解决方案中构建和采样概率模型。元启发式算法倾向于生成随机候选解,并将其处理成新的生成。相比之下,EDA使用概率模型来创建一组新的候选解决方案。这种方法提高了EDA的解决方案的质量,因为所产生的后代是基于从一组父母的最佳适应度导出的概率模型统计地构建和采样的。作为进化计算的工具,EDA成为一种有前途的算法,可以竞争性地解决优化问题[1]。在[7]中首次由Baluja引入的EDA以前包含一个单一的概率模型。目前的研究假设,EDA的有效性主要取决于概率模型的准确性,以提取人口中的信息。因此,多变量概率模型成为构建更好概率模型的一种选择[8]。这种推理决定了在EDA中使用两种概率模型,序数和依赖,在这项研究中。提供了详细的解释第4.1.1节。3. 问题描述EFLP考虑了安装成本,并插入了安全约束。安装成本与将设施分配到特定位置的固定成本有关[19]。由于设施在各个位置的安装费用是变化的,因此EFLP除了流矩阵外,还增加了安装费用矩阵。同时,[20]中的安全约束(也称为技术约束)禁止两个指定设施直接相邻放置[5]。EFLP数学模型中的变量描述EFLP(1)该方法使各设施间的流动距离和各设施的安装费用之和最小。本研究通过增加三个决策变量(Eqs.(2)- (4)。决策变量xij、yik和aij表示两个设施的相邻性,设施在位置中的位置和安全约束。当量(5)指定两个相邻设施点的距离,并考虑它们的长度和净空空间。等式(6)(7)确保流量负荷和安装成本大于0。最后,Eq。(8)限制所有决策变量是二进制数。与其他元启发式算法一样,EDA在处理大规模问题时似乎陷入局部最优[9]。因此,EDA与几种语言学和Meta语言学相结合,Z¼minn-1ni<$1j<$i<$1. xijWijdijaijPXk¼1Xi¼1Yi kCik!ð1Þ改进算法以改进解决方案。其中,有粒子群优化(PSO)[10],差分进化(DE)[2],GA[11]和贝叶斯优化算法(BOA)[4]。EDA与变异算子的特定组合,如[12]所示,可以提高算法的可搜索性。超市选址问题的解决,xij是的,国际新闻报1个;如果设施i放在j0;否则1个;如果设施i被分配给位置k0;否则1个;如果设施i不能与j0;否则ð2Þð3Þð4ÞEDA和DE杂交[2]。采用混合EDA和PSO求解水库防洪调度问题[10]。同时,将遗传算法与EDA相结合来处理调度问题[2].将EDA和BOA相结合来求解车辆路径问题[4]。SFLP的目标是基于设施间距离的产品流动成本之和最小。SFLP在许多现实世界的问题中被发现,例如房间安排,办公室中的部门安排,以及制造中的机器安排[13]。在[5,14]中描述了一个约束SFLP,它考虑了一些设施需要放置在某些位置,允许/不允许在两个有序设施之间布置任何其他设施。[5]提出了一种基于置换的遗传算法(pGA)来求解约束SFLP。最近,在[14]中的工作表明,烟花算法比pGA更好地解决约束SFLP。在文献[15]中提出了在每个时期开始时考虑材料处理成本和部门重新安排成本的SFLP。采用模拟退火算法(SA)和遗传算法(GA)及其混合算法来处理该问题。结果表明,与其他算法相比,SA表现出更好的性能[15]。同时,DE及其变体被[16]探索用于求解SFLP。在以前的文献中也提出了GA和邻域搜索来处理SFLP[17,18]。概括地说,如前文导言部分所述,可以指出以下研究差距。首先,没有研究比较杂交的溶液质量的EDA。因此,进一步的研究对指导EDA技术的发展是十分必要的.其次,近年来,还没有研究利用EDA来处理SFLP和EFLP。因此,对这一问题的比较研究是一个很有潜力的研究领域.s.t.:dijPliljsij;dij;sijP0;li;lj>0 5W ij> 0; i; j ^l; 2;. ; n6C ik> 0; i; j; k 1; 2;. . ; n7xij2 f0; 1g;yik2 f 0; 1g;pij2 f 0; 1g4. 方法4.1. 算法:AEDA本研究提出一种新的混合EDA,自适应估计分布算法(AEDA)。EDA的结构被修改,表1EFLP数学模型中的变量描述。可变描述xij决策变量,如果设施i与j相邻,则等于1;否则等于0yik一个决策变量,如果设施i被放置在位置k,则等于1;否则等于0aij一个决策变量,如果设施点i不能与设施点j相邻,则等于1;否则等于0n设施数量k设施的位置(k 1; 2;. . ;n)i; j设施指数(i; j ^1; 2;.. . ; n)li设施长度iWij设施i和设施jCik将设施i分配到位置k的安装成本dij设施i和设施j的两个设施违反安全约束.¼..¼A. 歌间埃及信息学杂志22(2021)505507←←nð Þ←ð Þ← ð Þ增加了彩票部分,轮盘选择,精英策略,和TS。AEDA中的这些附加组件用于维持进化算法的自适应[21]。AEDA的主要阶段是选择、概率模型计算、采样和邻域搜索。AEDA的伪代码在算法1中详细描述,而变量的描述在表2中给出。首先,随机初始化一组候选解这些候选解的结构是使用基于置换的变量构造的。然后计算每个候选解决方案的成本迭代开始并执行AEDA的主要阶段(在以下小节中描述)。4.1.1. 选择和概率模型计算阶段AEDA的迭代从选择阶段开始,该阶段使用截断选择。截断选择显著提高了模型精度[22],选择了一组与其他解决方案相比具有更好适应性的候选解决方案。选择阶段的结果(算法1,第4行)记录在S中。AEDA中的以下步骤计算概率模型(算法1,第5-6行)。在这个阶段中使用两个概率模型,顺序和依赖。当量(9)用于计算将设施分配给位置的概率。由方程式Pik是将 设施 i安装在位置 k处的概率(其中,k1/4 2; 3;. ;n;i;j; 1; 2;. ;n)。有序概率模型(uik)表示位于某个位置的设施的重要性,而依赖概率模型(Wij)指的是与另一设施相邻放置的设施的重要性乌鲁夫在一个位置,它被添加到F,X将从unas签名的设施中删除它。计算每个候选解决方案的成本,并更新cBest。描述了TS(算法1,第23-25行)在下面的小节中。4.1.3. 邻域搜索阶段AEDA首先检查cBest是否优于gBest。如果在当前一代中gBest没有改进,则执行邻域搜索[18]。如果当前代中的cBest 不能改进gBest,则运行基于TS的邻域搜索否则,AEDA将直接进入精英程序并进入下一代。AEDA能够在运行TS或继续进行下一次迭代之间进行选择,从而节省了计算时间。如果gBest仍然优于cBest,则TS将被操 作 ; 否 则 , gBest 被 设 置 为 等 于 cBest 。 对 一 些 代 进 行 TS 程 序(tabuGen)。在每个tabuGen中构造的swaplist包含一组移动(两个设施的交换)和相关成本(tcost)。接下来,TS检查移动是否是禁忌,以及每个移动的成本(tcost)是否比tabuSol差。如果一个移动符合这些条件,就会受到惩罚。TS然后更新tabooList和tabu- Sol。在一代结束时,tabuSol将包含TS的最佳解决方案如果在tabuSol中找到更好的解决方案,则TS阶段以用tabuSol替换gBest结束最后,在每一代AEDA结束时执行精英主义程序,该程序记录了一代中10%的最佳解算法1 AEDA1:初始化变量和设置参数派伊杰92:每一代都要我们的团队þwijð Þ3:计算成本;cBest;和gBest4:S选择()5:计算有序概率模型(S)4.1.2.采样相位采样相位在算法1第7-21行中示出。对于每个候选解决方案,采样步骤从在第一位置上放置设施开始本研究提出了一种彩票程序,以保持人口的多样性。在文献[11]的基础上,提出了在EDA部分中增加随机性的方法,该抽签过程选择来自前一代(来自S)的第一设施或随机设施以放置在第一位置。本研究在运行AEDA与几种组合的LotteryRate进行了实验,发现最佳设置为5%。然后利用轮盘选择将设施分配到第二位置,直到到达第n位置(算法1,第14-20行)。将设施设置到某个位置的概率(在等式中计算)(9)在每个位置记录。接下来,计算累积概率,并生成均匀分布的随机数[31]。使用轮盘赌的概念,设施被放置到位置。每次放置设施时表2AEDA伪代码中使用的变量的描述变量描述S一组选定的候选解决方案n设施数量cBest当前最佳解决方案gBest迄今为止几代人的全球最佳解决方案F一套指定设施P设施分配到地点X一套未分配的设施h随机数i通过轮盘赌选择的设施k设施点位置的索引6:计算依赖概率模型(S)7:对于每个候选解,8:F←£9:如果jlotteryRate,则<10:F1彩票()11:其他12:F1 RandSe1ect(S1)13:如果结束14:对于k=2直到n,15:cumP←计算P的累积概率16:h←U0; 117:轮盘选择(h;cumP)第18章:我的天19:X Xi20:结束21:结束22:计算成本;更新cBest23:如果cBest>gBest,则第24章:你是我的女人25:如果结束第26章:你是我的女人第27章:你是我的!28:结束4.2. EDA的杂交本研究在以往文献解释的基础上,重新编码了EDA的几个杂交。这些 组 合 是 EDA + GA ( EDAGA ) 、 EDA + PSO ( EDAPSO ) 和EDAPSO + TS(EDahybrid)。ikA. 歌间埃及信息学杂志22(2021)505508←4.2.1. 埃达加EDAGA的概念首先由Chen等人(2012)[23,24]引入,将GA结合到EDA的结构中。GA确保候选组保持多样性,而EDA利用候选来实现良好的解决方案。EDAGA已用于调度问题[23]、无空闲流水车间调度问题[24]。算法2给出了EDAGA的基本伪代码10:如果结束11:更新适应度、人口和gbest12:结束一般的概念是交替运行EDA和GA,直到停止标准(即,最大代数)。EDA过程(算法2,第4-6行)在每个偶数代上运行。基于所选择的染色体开发概率模型。采样过程基于概率模型生成新的染色体。当生成是奇数时,执行GA方法(算法2,第7两点交叉过程应用于选定的染色体。同时,突变将在染色体的几个点使用0.7的交叉率和0.3的突变率将交叉和突变程序应用于染色体[6]。该过程继续评估每个染色体的适应度值。最佳解决方案和人口更新将随之而来。4.2.2. EDA混合算法3 EDA混合1:初始化变量和设置参数2:对于每一代gdo3:计算适应度;pBest;和gBest4:如果g是偶数,则5:选择S;计算序数概率模型(S)6:计算依赖概率模型(S)7:采样()8:其他9:计算速度();更新人口()10:如果11:更新适应度,pbest第12章:你是谁?第13章:你是谁14:结束EDAhybrid是EDA,PSO和TS的组合一般来说,EDA和粒子群算法交替运行以保持EDAhybrid算法的多样性,并加入TS概念。该算法用于解决设施布局问题[6]。算法3给出了EDAhybrid的伪代码。EDA Pro-candidate(算法3,第4-7行PSO程序(算法3,第8-9行然后执行粒子更新。EDAhybrid继续计算每个粒子的适应度值然后更新粒子最佳(pBest),即在群中找到的当前最佳粒子和gBest(到目前为止通过生成找到的最佳粒子TS(算法3,第12行)将利用gBest来发现是否可以进行改进如果TS的解决方案优于gBest,则它将取代gBest。在每次迭代结束时应用精英主义4.2.3. EDAPSOEDAPSO算法是EDA和PSO的结合算法4给出了EDAPSO的伪代码。在水库防洪调度中也可以看到EDA和PSO的混合应用[10]。这种EDAPSO的概念是将PSO嵌入EDA中,以保持算法的多样性。EDAPSO和EDAhybrid的区别在于存在局部搜索和精英主义。EDAPSO在其迭代中不使用本地搜索和精英主义EDA部分在每偶数代运行(算法4,第4然后,pBest和gBest将被更新,新的粒子是传给下一代。算法4 EDAPSO1:初始化变量和设置参数2:对于每一代gdo3:计算适应度;pBest;和gBest4:如果g是偶数,则5:选择S;计算概率模型(S)6:抽样()7:其他8:计算速度();更新swarm()9:结束如果10:更新pbest和gbest11:结束4.3. 禁忌搜索遗传算法遗传算法,以及它与其他启发式算法的混合,经常在文献中找到[25]。在[26]中演示了一种混合遗传算法,该算法具有用于设施布局问题的解构和重构解决方案。GA中的修改的旋转算子用于静态设施布局问题[27]。其中,GA和TS的混合被证明是解决作业车间调度[28]和车辆调度等组合问题的鲁棒算法路[29]。然而,在SFLP领域,算法2 EDAGA1:初始化变量和设置参数2:对于每一代gdo3:计算种群中的适应度4:如果g是偶数,则5:选择P;计算概率模型(P)6:抽样()7:其他8:选择P;交叉(P)第9章:突变因此,本研究建立了GA + TS(GATS)算法,并将其与AEDA算法进行了比较。GATS的概念是将TS作为本地搜索添加进来。算法5给出了GATS过程。如算法5所示,生成从种群中每个染色体的适应度计算开始然后通过轮盘选择来选择父母交叉(使用两点算子)和变异程序适用于染色体。之后,替换步骤将更新染色体与他们的后代。GATS中的TS部分在GBEST没有改善的情况下执行。精英主义的过程在每一代人的最后阶段都要进行.A. 歌间埃及信息学杂志22(2021)505509←←算法51:初始化变量和设置参数2:为每一代做3:计算种群中的适应度4:PRouletteWheelSelection()5:交叉(P)第6章:突变7:Replacement(); Update fitness,cbest8:gbestTabuSearch(cBest)9:Elitism()10:结束5. 实验结果这项研究利用Matlab在PC与英特尔i5处理器和12 GB RAM开发所有的算法。这些算法的参数是相似的,问题规模越大,需要的迭代次数越多。本节列出了所有算法的实施结果以及结果分析5.1. 测试在测试阶段,所有的算法都被编码来解决SFLP中的15个基准数据集每个算法运行10次。表3显示了我们提出的算法(AEDA)生成的最小值,以及EDAGA,EDAhybrid,EDAPSO和GATS的最小值。粗体值表示每行中的最小问题代码的不同名称意味着问题的不同规范。最后一行是每个算法实现的解与迄今为止找到的最优解(来自文献[17,30])相比的差距(表示差异)。EDAGA和EDAPSO在15个问题中的9个问题上都获得了最优解。然而,EDAGA的解决方案与其他算法相比差距最大。同时,GATS在15个实例中有13个实例实现了最低限度的解决,与EDAGA和EDAPSO的差距较小。AEDA在表3中列出的所有15个问题中实现了最佳解决方案,与其他算法相比,这些问题的差距为0%,并且最小(最佳目标值)。在13个问题(LW5到P30)中,AEDA实现了与EDahybrid相同的最优解,而在A30中,AEDA优于EDahybrid。5.2. 求解EFLPEFLP数据由7个实例组成,从5到30个设施不等。其中三个问题(设施数为5、11和20的问题)取自以前的文献[6]。本研究产生了另外四个实例,即8、15、17和30个设施的问题。本研究比较了AEDA,EDAGA,EDAhybrid,EDAPSO和GATS在100次重复中的最小结果,最大值,平均值,标准差和运行时间。表4比较了求解EFLP的算法的最小值和最大值,而表5列出了平均值和标准差。表4中的结果表明,AEDA和GATS在所有问题实例中成功地完全实现了最小(最佳)解决方案,而EDAhybrid从问题5到问题20得到了最小解决方案。AEDA和EDAhybrid分别在5个和4个问题上获得最佳最大值。然而,GATS只在两个问题中获得最佳的最大值。而EDAGA和EDAPSO都只能得到3个问题的最小解.所有求解EFLP的算法的性能也如表5所示。表5中最后一行中的百分比误差表示100次运行中的平均值与所有算法的最低最小值之间的差距。AEDA在6个问题中实现了最小均值,而EDAhybrid在1个问题中获得了最小均值。AEDA的标准差在4个问题中最小,而EDAhybrid的标准差在3个问题中最小。同时,EDAGA、EDAPSO和GATS都不能得到最小的均值和标准差.在误差百分比方面,AEDA获得了第一位(最低值为1.12%),而EDahybrid和GATS分别排在第二和第三位。EDAPSO图1显示了所有算法对小规模问题(8)、中等规模问题(15)和大规模问题(30)的解决方案的箱形图。问题8中每个算法的箱形图几乎都是问题15和问题30的箱形图显示AEDA、EDAhybrid和GATS优于EDAPSO和EDAGA。为了测试每种算法的平均值是否显著不同,然后应用ANOVA检验。既然两问题15和30的箱形图几乎相似,对问题8和30进行方差分析。表6和表7分别显示了问题8和30的ANOVA表。表6和表7中的p值表明ANOVA拒绝所有算法平均值相等的零假设事后检验使用多个表3所有算法的最小结果的比较(SFLP中)。情况最小(目标)值埃达加EDA混合EDAPSOGATSAEDAS4638.0638.0638.0638.0638.0LW5151.0151.0151.0151.0151.0N62.02.02.02.02.0S8801.0801.0801.0801.0801.0S8H2324.52324.52324.52324.52324.5S92469.52469.52469.52469.52469.5S102781.52781.52781.52781.52781.5S116933.56933.56933.56933.56933.5LW116933.56933.56933.56933.56933.5N1223.55023.36523.55023.36523.365P156335.06305.06320.06305.06305.0P2015849.015549.015797.015549.015549.0P254699.04618.04668.04618.04618.0P3046985.044965.045577.044985.044965.0A3047444.045454.046002.045544.045449.0间隙0.922%0.001%0.419%0.017%0.000%A. 歌间埃及信息学杂志22(2021)505510表4所有算法的最小值和最大值的比较(在EFLP中)。问题EDAGA EDAhybrid EDAPSO GATS AEDAMinMaxMinMaxMinMaxMinMaxMinMax5410.39425.39410.39425.39410.39440.45410.39425.39410.39425.398823.12856.07823.12835.12823.12873.14823.12836.03823.12836.03119398.109902.409398.109801.859398.109916.359398.109846.509398.109793.85155805.006457.005700.006375.005708.006388.005700.006443.005700.006317.00178294.009197.008074.008550.008092.009029.008074.008573.008074.008597.002061401.965937.260334.661783.960639.565257.060334.662122.760334.661783.93024970.7029307.7023694.2025836.7024138.1028852.4023606.1026406.3023606.1025995.40表5所有算法的平均值和标准差的比较(在EFLP中)。问题EDAGA EDAhybrid EDAPSO GATS AEDA是说STD是说STD是说STD是说STD是说STD5412.945.66412.795.53414.578.21413.696.24414.296.618830.825.87829.144.60833.108.99828.865.09828.7724.97119512.5893.879480.26119.759519.65131.219517.30149.889458.354105.93156123.52131.655790.49151.515772.14134.615784.16152.535771.78122.72178755.08184.738201.46132.138394.21167.028230.53149.428200.65120.262063867.88933.6660816.19387.2961983.28857.6260840.50396.2860739.43336.853027282.48841.8724261.73607.0926105.371268.5524140.78633.5024092.755623.39百分比误差5.69%1.28%3.12%1.33%百分之一点一二图1.一、所有算法在(a)问题8、(b)问题15和(c)问题30中的解决方案的箱形图表6问题8的ANOVA结果。源SSDFMSFp值列1374.14343.5229.183: 69x 10-7误差18526.949537.428总19901499表7问题30的ANOVA结果。源SSDFMSFp值列8: 38x 1084209: 6x 106301.383: 9x 10-131误差3: 44x 1084950: 7x 106总1: 18x 108499然后使用比较检验(Dunnett检验)来确定哪些算法平均值与其他算法不同。在Dunnett检验中,如果两组均值的区间不相交,则两组均值存在显著差异;如果两组均值的区间重叠,则两组均值不存在显著差异。图图2显示了(a)问题8和(b)问题8的Dunnet检验。30. 图2(a)描述了在问题8中,EDAhybrid、GATS和AEDA具有与EDAPSO显著不同的平均值;没有算法具有与EDAGA显著不同的平均值;并且EDAhybrid、EDAGA、GATS和AEDA的平均值不显著A. 歌间埃及信息学杂志22(2021)505511图二. (a)问题8和(b)问题30的Dunnet检验。表8所有算法运行时间的平均值和标准差的比较问题EDA混合埃达加EDAPSOGATSAEDA平均标准品是说STD是说STD是说STD是说STD50.0213 0.00480.00960.00030.01100.00060.04560.00120.00940.005180.0548 0.00120.04510.00080.04280.00050.05660.00110.03780.0009110.2232 0.00930.17450.00900.16240.00520.16700.01020.12200.0072150.59610.02630.50550.01600.38520.01290.49750.02890.38400.0108171.0940 0.02700.65480.02000.61870.01300.79360.02600.62240.0170202.17580.04831.11900.03111.04950.02071.50790.03071.25100.03893014.26400.26304.60060.13174.40650.166310.23250.35988.28880.1533图3. (a)问题8、(b)问题15和(c)问题30中所有算法运行时间的箱形图不同.另一方面,图2(b)显示,在问题30中,EDAhybrid、GATS和AEDA的平均值与EDAGA和EDAPSO显著不同; EDAhybrid、GATS和AEDA的平均值没有显著不同; EDAGA和EDAPSO的平均值显著不同。表8提供了所有算法的运行时间(以秒为单位)的平均值和标准差。AEDA在7个问题中的4个上实现了最小的平均运行时间,而EDAPSO在其余3个问题中获得了最小的平均运行时间。EDAPSO的运行时间标准差在4个实例中最小,而AEDA和EDAGA的运行时间标准差分别在2个和1个实例中最小。GATS同时,EDAhybrid图图3给出了所有算法在小规模问题(8)、中等规模问题(15)和大规模问题(30)中的运行时间的箱形图。图中的箱线图。 3(a)问题8和(c)问题30表明,每个算法的框面积彼此不相同;因此,它们的均值可能显著不同。因此,ANOVA检验仅适用于问题15,p值为2: 93x 10-301。问题15中运行时间的Dunnett检验如图所示。 四、结果表明,AEDA和EDAPSO的平均运行时间差异不显著,而其他配对的平均运行时间差异显著图5给出了求解EFLP问题15时所有算法收敛性的图解说明。如图5所示,AEDA算法与其他算法相比,能够以较少的迭代次数得到最优解。GATS比AEDA收敛得快,但客观价值不如AEDA和EDAhybrid.A. 歌间埃及信息学杂志22(2021)505512见图4。 问题15的运行时间的Dunnet测试图五. 所有算法的收敛性比较(问题15)。虽然EDAhybrid优先算法优于其他算法,但与AEDA和GATS算法相比,它需要更多的代来收敛。同时,EDAPSO和EDAGA需要更多的迭代才能获得更好的解决方案。6. 结论本研究提出了一个比较研究的几个杂交的EDA在解决设施布局问题。本研究还提出了一种新的算法称为AEDA。AEDA,EDAGA,EDAPSO,EDAhybrid和GATS的实验结果应用于EFLP的实例所有算法在前3个问题中表现良好,而AEDA,EDahybrid和GATS在所有问题中都表现良好。通常,基于解的最小值、最大值、均值和标准差的比较 , 最 好 的 算 法 是 AEDA , 其 次 是 EDAhybrid 和 GATS , 最 后 是EDAPSO和EDAGA。对结果的一些实例进行ANOVADunnett检验表明AEDA、EDAhybrid和GATS的平均值无显著差异。同时,通过对所有算法运行时间的均值和标准差的比较,表明AEDA和EDAPSO算法的运行速度要快于其他算法。在这项研究中的混合算法的比较研究,预计将启发未来的研究,以确定哪些方法是可能的选择。所提供的数据和结果可以成为EFLP未来研究的基准未来的研究也可以集中在提高算法的性能或应用不同的情况下。确认作者非常感谢Institut Teknologi Sepuluh Nopalgia在出版物写作和知识产权激励计划(PPHKI)项目计划下对这项工作的财政支持。引用[1] Gao S,de Silva CW.约束优化问题的估计分布算法。应用数学计算2018;339:323-45.[2] Zhou B-H,Tan F.超市选址问题的自适应差分进化分布估计算法。神经计算应用2020;32(10):5791-804。[3] Utamima A,Reiners T,Ansaripoor AH.田间物流配送路径规划的进化估计算法ProcComputSci2019;161:560-7.doi:https://doi.org/10.1016/j.procs.2019.11.156网站。[4] Pérez-Rodríguez R,Hernán-Aguirre A.带时间窗车辆路径问题的混合分布估计算法。计算机工业工程2019;130:75-96。[5] Kalita Z,Datta D.一个有约束的单行设施布局问题。国际先进制造技术杂志2018;98(5-8):2173-84。[6] 放大图片作者:Ou-YangC,Utamima A. 求解单排设备布局问题的混合估计分布算法。 Comput Ind Eng 2013;66(1):95-103.[7] S. Baluja,基于人口的增量学习。一种集成基于遗传搜索的函数优化和竞争学习的方法,技术。代表,Pittsburgh大学计算机科学系(1994年)。[8] Martins JP,Delbem AC.成对独立性及其对分布估计算法的影响。Swarm EvolComput2016;27:80-96.[9] Cravo GL,Amaral AR.求解大规模单排设备布局问题的GRASP算法。ComputOper Res2019;106:49-61.[10] Luo J,Qi Y,Xie J,Zhang X.水库防洪调度的混合多目标PS O -E D A 算法 ApplSoft Comput 2015;34:526-38.[11] 陈世辉,陈明春,刘永春. 人工染色体与遗传算法2(ACGA 2)的单机排序问题与序列相关的调整时间。Appl Soft Comput2014;17:167-75.[12] 汉达·H变异操作在分布估计算法中的有效性。生物系统2007;87(2-3):243-51。[13] 杨文龙,李晓梅,李晓梅.设施布局问题:文献计量和基准分析。Int J Ind EngComput 2019;10(4):453-72.[14] 刘顺,张智,关聪,朱丽,张明,郭萍。求解约束单排设施布局问题的改进烟花算法。Int J Prod Res2020:1-19.[15] S,ahinR,NiroomandS,DurmazED,Molla-Alizadeh-ZavardehiS. 动态单行设施布局问题之数学公式与混合式启发式解法。Ann Oper Res 2020:1-24.[16] KrömerP,Platoirj J,Snášel V. 应用差异演化法求解单行设施布局问题。在:2020年遗传和进化计算会议的会议记录。p. 210- 8[17] Datta D,Amaral AR,Figueira JR.以置换式基因演算法求解单行设施布局问题。Eur J Oper Res 2011;213(2):388-94.[18] Ripon KSN,Glette K,Khan KN,Hovin M,Torresen J.自适应可变邻域搜索求解具有不等面积设施的多目标设施布局问题。Swarm Evol Comput2013;8:1-12.[19] Sule博士,制造设施:位置,规划和设计。CRC Press;2008.[20] 赫拉古号设施设计。第4版。CRC Press;2018.[21] 克莱默岛进化自适应:运营商和战略参数的调查。Evol Intel2010;3(2):51-65.[22] Utamima A,Ou-Yang C.扩展人工染色体遗传算法求解单排设备布局问题。Journal of Technology2012;27(4):189-94.[23] 陈玉梅,陈明春,张培春,陈世辉.置换流水车间调度问题的扩展人工染色体遗传算法。Comput IndEng 2012;62(2):536-45.[24] 沈建南,王玲,王世银.基于总拖期准则的无空闲置换流水车间调度问题的双种群EDA。基于知识的系统2015;74:167-75。[25] Briskorn D , Dienstknecht M. 施 工 中 的 定 量 方 法 综 述 Comput Oper Res2018;92:194-207.[26] Paes FG,Pessoa AA,Vidal T.求解不等面积设施布局问题的带分解阶段的混合遗传算法。Eur J Oper Res 2017;256(3):742-56.[27] 放大图片创作者:Hasda RK,Bhattacharjya RK,Bennis F.改进遗传算法求解设备布局问题。 Int
下载后可阅读完整内容,剩余1页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)