没有合适的资源?快使用搜索试试~ 我知道了~
¼×XXXX工程科学与技术,国际期刊20(2017)1531完整文章带通问题Arif Gursoya,Mehmet Kurtb,Hakan Kutucuc,Mr. Kuta,Urfat Nuriyevaa土耳其伊兹密尔35100埃格大学数学系b工程和自然科学学院,Bahcesehir大学,伊兹密尔35310,土耳其c土耳其Karabuk 78100 Karabuk大学计算机工程系阿提奇莱因福奥文章历史记录:2017年10月2日收到2017年12月5日修订2017年12月6日接受2017年12月14日在线发布保留字:带通问题组合优化问题启发式和元启发式算法布尔规划波分复用A B S T R A C T由Babayev等人建模的带通问题(BP),是在使用波分复用技术的光通信网络中出现的组合优化问题。BP的目标是设计一个最佳包装的信息流在不同的波长成组,以获得最高的可用成本降低。在本文中,我们提出了新的方法来解决BP。首先,我们提出了两个新的启发式算法产生更好的解决方案比Babayev等人介绍的算法。对于BP库的几乎所有问题实例其次,我们提出了一种新的元启发式算法,使用三种不同的交叉和五种不同的变异算子。总共创建了15个实现,并使用两个不同的输出进行了测试,这两个输出是由我们提出的算法作为初始种群获得的实验结果表明,所提出的元启发式算法提高了解决方案。©2017 Karabuk University. Elsevier B.V.的出版服务。这是CCBY-NC-ND许可证(http://creativecommons.org/licenses/by-nc-nd/4.0/)。1. 介绍电信网络中出现的带通问题(BP)于2004年首次讨论[1],并于2009年建模[2]。根据该模型,在通信网络上,存在一个发送点,该发送点具有要发送到n个不同目的地点的m个信息包如果一个信息包被发送到一个目的地,它将显示为1,否则为0。 图 1表示包1将被发送到目的地1,但不会发送到目的地2,依此类推。为了在数学上用公式表示这个通信网络,我们将信息包称为矩阵的行,将目的地点称为矩阵的列该位置由维数为m×n的二进制矩阵Aλijλ来描述。如果该信息包i = 1;. ; m的目的地是点j j<$1;. ; n= 0,则为ij<$1;否则为ij<$0 [2]。带通问题可以描述如下[2]:给定一个m×n维的二进制矩阵A和一个称为使得所有列中的带通总数最大化。我们在图2a中的维度为8 - 4的矩阵上示出BP。矩阵的3个连续的非零项(用相同的颜色着色)形成一个带通。 图 2a,有三个带通。问题是是否存在任何行置换p,使得所有列中的带通总数最大化。经过几次争吵后,我们可以获得排列p^f2; 3; 7; 4; 1; 8; 6; 5g.图中的矩阵。 2b根据排列p总共由四个带通组成。将通信矩阵中的信息包封装为带通可以导致降低光通信网络中的成本的机会有关潜在应用的更多详细信息,读者可以参考[2]。BP的数学公式如下:n m-B1最大化ykj带通数,B列中的连续非零元素形成带通。列中的任何非零项只能包含在一个带通中。这意味着,同一列不能有任何公共行。 但并非所有第1页受Mk¼1非零条目必须包括在带通中。带通问题的目的是找到矩阵*通讯作者。电子邮件地址:hakankutucu@karabuk.edu.tr(H.Kutucu)。由Karabuk大学负责进行同行审查。x ik¼1; 8i¼1;. ;m 2k¼1Mx ik¼ 1; 8k¼ 1;. ;m31/1https://doi.org/10.1016/j.jestch.2017.12.0042215-0986/©2017 Karabuk University.出版社:Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。可在ScienceDirect上获得目录列表工程科学与技术国际期刊杂志主页:www.elsevier.com/locate/jestchX¼19220p8>:0 otherwise:... ; n; k¼ 1;. ; mRNA相互作用预测问题,无论允许或不允许伪结样相互作用,是NP难的。在本文中,我们提出了两个新的启发式算法和一个元启发式算法,它采取这些启发式算法的输出这些算法考虑了一些额外的标准来选择要重新定位的行我们提出的约束(2)表示行i必须仅被重定位到一个新位置k的事实,(3)表示仅一行i必须被重定位到每个新位置k。(4)保证没有两个带通可以具有公共元件。(5)保证找到带通的坐标。我们的目标是找到一个最佳的每变异行的矩阵,最大限度地提高了总数对于Babayev等人创建的BP库的问题实例,启发式算法给出了比[2]中给出的先前启发式算法更好的结果,以供研究人员比较他们的算法[12]。该库由90个不同大小的问题(矩阵A的行数、列数和非零元素的密度以及带通数B)组成。这些实例分为图二. (a)二进制矩阵和B^3的带通,(b)根据p重新定位行后的新矩阵。.¼JðÞ第1页JJJ1/1JJPnPA. Gursoy等人 /工程科学与技术,国际期刊20(2017)1531-15391533两组,每组45个实例,一组的最优解已知,另一组的最优解未知。提出的元启发式算法,它使用五种不同的变异和三种交叉方法,改善了新的启发式算法的结果。元启发式算法提高了62%的BP库的实例平均改善约为6%,然而,在某些情况下,改善增加至并对一些实例进行了优化求解。详细的计算结果在第5节中给出。2. Babayev等人的启发式算法。Babayev等人的算法(本文称之为h0)对m×n维的二元矩阵[2]有m步。算法h0的基本思想是在m个步骤中生成重定位行的列表。在每一步中,将添加一行未包含在重定位行列表中的行。然后确定该行对所有列的影响。其目的是重新定位的行的列表形成新的低音带/带通或不改变连续的1。这一想法的实现如下:算法h0使用得分向量,该得分向量是非负整数分量的n维向量,对应于矩阵中的每一列每个组件保持相应列中连续非零元素的总和,从重新定位的行列表的最后一行开始并返回到开始。在算法过程中,每个分量从零开始增加到B。当相应列中的新带通被创建或连续的1被在同一篇论文中,讨论了算法h的一行的值函数在该列中为1。算法H1就是基于这个想法。给定一个m×n的二进制矩阵A,一个带通数B和所有行的集合R。RsRsR,A的选定行的集合,最初是空的。当Rs中的元素数等于行数时,算法终止。对于迭代t,行i和列j,下面描述算法中使用的参数。在某些参数中,算法使用在先前迭代中获得的值M:m维向量;Mi是第i行中非零元素的和。N_i:迭代t中的n维向量;N_j是列j中的n行的非零元素的和。Pj是松弛度的相反程度(给出列j是否是新带通的强候选者的指示)。s= t:迭代t中的n维向量;它是包括连续非零元素的数量的得分向量。sj6B从零增加到B。当sj达到B时,生成新的带通,并且sj为更新为零。当新选择的行在列j中具有零值条目时,它也被分配为零。dj=迭代t中的n维向量;dj是列j的值函数(给出选择非零元素的总优先度)。q:至多n维向量;qk是第一个k的和非递增排序非零元素别说了。C:一个m×n矩阵;cij是dt与pt之和。诅咒一个版本如下:由h0j j取决于在h0开头选择的行。该算法可以执行m次,每次从一个新行开始。这产生了m个候选解,最好的一个可以作为解决方案。在h0中的总迭代次数是3m2n2- 4mnn- 3,这产生On时间。上面提到的h0的版本运行在Om3n中,因为h0被执行m次。3. 新的启发式算法局部搜索是解决组合优化问题的一种有效方法。r:m维向量; ri是C的第i行的和。dk:大于或等于qk的r的集合。b:q k的最大指数,其dk= k。算法h1的一般框架如下:第一步,步骤0,是初始化步骤。在步骤1中,我们在矩阵的顶部或底部找到稀疏行,以最大化带通的数量。因此,选择具有最小Mi的行e。 如果有几个最小值,那么我们选择第一个在步骤2中,我们计算st;Nt的当前值,J J已知的和广泛使用的通用启发式[13]。最选择行e的p_t_n和d_t_n。在步骤3中,我们确定了当前的在算法h0中选择行的重要标准是得分j jvector.然而,可以存在一些不同的标准来选择行,诸如列中的1的数量、算法的任何步骤中的列中剩余1的数量以及可以在所有行或剩余行中获得的带通的数量。这两个建议的启发式算法的基础上的想法,这些标准作为一个整体进行评估,以确定一个合适的行。在该算法中,根据这些准则的重要性来计算要选择的每一行的3.1. 启发式-1(h1):我们将列的松弛度定义为在删除1之后剩余的1的数量,从而形成列中最大可能的带通数量。列的松弛程度越小,意味着我们必须赶紧选择该列中包含1的行。否则,这意味着我们不必选择此列中包含1的行。因此,柱松弛度的贡献应小于租值cij和ri,其中iRRs。在步骤4中,我们估计电流-租值dk和b,则确定新行e并将其添加到所选行的集合Rs中。在步骤5中,如果未选择的行(剩余行)的数量为1,则将该行添加到Rs中,并且算法终止,否则转到步骤2。算法h1:开始步骤0:t1/40,a/n·B,q0/40,M i<$a ij;i<$1;.. . ;m,Ntm a ij;j¼1;. ;n,ptB-NtmodB;j 1;. ; n,s= 0; j = 1;. ;n,d不超过0; j不超过1;.; n.sjJJ北纬8度-1国际法协会 四分之一ðtÞ:JJPJIJ¼·j j¼ð Þð Þð Þ ð Þ ð ÞðÞJJJJJJJJJðtþ1ÞJ1J2JLKpt1JEJJ8>·-J:j jjd¼1534A. Gursoy等人/工程科学与技术,国际期刊20(2017)1531步骤1:很明显,这个度对具有以下特征的矩阵有不同的影响:m1/4 32和m 1/4 128行。这个例子也可以扩展到E1/E2/E3/E4/E5/E6/E7/E8/E9/E10/. ;mRs¼ feg第二步:对于不同的带通数。因此,第二种启发式算法h2使用各种比率来构造值函数:dtma=Bst 1dt 1 1n·a=Mem= pt1n,如果st1>0;0ifst=0:j0否则:如果s不等于100 B,则s不等于100 0; j 1;. ; n新值函数选择新行的优先级如下所示:sj收敛到B要好得多。召回sj是第j列中连续的1的个数B-sj写成J不需要了J不J:Nj,否则:8天后的第一天1;.. . ; n如果s不大于0;在分母中,因为小的B-sj值应该产生大的dj值。Me是选定行中1的个数。行中1的数量较少意味着该行是稀疏的在计算测试中,我们看到当首先选择稀疏行时获得更多的带通pj是松弛度的相反程度当选择一行时,将为uns的每一列计算pj0 ifsj¼0:订购非零数据不递增。 即当选的行。带通发生的概率很高,列j,其具有低pj。h2的时间复杂度与h1相同如果h2执行m次,每次从一个新行开始,那么dt1Pdt1P···Pdt 1P;dj1/4dj···0和q运行时间为Omin3nmin。ki¼1dt 1;k 1;. ;L;其中L是非零元素4. BP神经网络的元启发式算法我不这意味着当sj和pj在当前迭代中最大时,在步骤1中选择的行e是要添加到矩阵中的最佳候选。208年8<月1日 1/4;JðtÞBP的解是给定矩阵的行置换,使得所得矩阵具有最大带通数。遗传算法(GA)的种群结构使其难以获得有效的遗传算法。由于随机性,pj,否则:如果p<1>B,则p<1>1。如果s不等于10且N不等于10B,则p不等于10B不等于1。<第三步:生成的行排列大多会导致低效成本,矩阵[14]。因此,Gur- soy等人在[15]中提出的启发式算法已被修改并集成到GA中。行置换(或染色体)的拟合值是矩阵的带通数。在遗传算法的初始阶段,种群规模为0.05ps,交叉率为0.05cr,变异率为0.05mr,交叉次数为0.0001,CN_n和突变数CN_n_n_n如下确定:(d)如属以下情况,则不作10%的补偿;cJ0,否则:1;.. . ; n和8 i R Rps/n·m=2,cr/n =0:9,ri¼Pncij;8iRRsMR1/4-Cr,第四步:第1页CNCRMN·ps,dk1/4 frijriPq k和iR R sg;k1/4 0;. L.b0;.. . ;Lfqkjdk-gg。在2008 年 , 他 在 一 家 医 院 接 受 了 一 次 治 疗。Rs¼Rs[feg.t1/2 t1/2。第五步:如果R=Rs 1,则将行附加到Rs并停止。否则,请转到步骤2。端启发式算法h1通过从最合理的行开始,然后逐个选择其他行来找到解在h1中的总迭代次数是2m2nmnlognm2 5mnm- 11n,产生Om2n时间。3.2. 启发式-2(h2):在这种启发式中,我们将松弛度的补数(B-sj)添加到值函数中。仅使用准则的数值计算值函数可以忽略作用于值函数的分量的权重。例如,考虑松弛度为5的柱它ps先生。t:代数,P t:个体的总体,N t:后代,ci:交叉指数,mi:突变指数。遗传ci;mi过程分别根据输入参数ci和mi调用Crossover ci和Mutation mi子过程(运算符)。种群的初始集合中的染色体与拟合值非递增地排序。遗传性ci;mit=0时使用算法h1或h2初始化P_(?)t_(?)而(最佳拟合值n·m=2次不变)Crossovercanceri:crossoverPttoyieldNtMutationmi:mutationPttoyieldNt评估N值从Pt和Nt中选择Pt1t=t +1端1;.. . ; nL1nL-2... ; nðÞ¼¼ðÞð Þð Þ●ðÞ××●ðÞ●ðÞ●ðÞ●ðÞ●ðÞ●ðÞ¼¼ðÞ●ðÞ1/1然后ðÞ ðÞðÞCrossov er ciA. Gursoy等人 /工程科学与技术,国际期刊20(2017)1531-15391535最佳拟合值n·m=2倍,这提供了一个很好的近似值。ifciC1else ifci2 thenC2 elseC 3端对问题的认识。5. 计算实验在本节中,我们给出了第3节中描述的我们提出的启发式算法h1和h2、第4节中描述的具有不同交叉和变异算子的遗传算法以及所提出的算法h0的计算实验结果Babayev et al.在第2节中描述。所有的算法突变体ifmi1 1 thenM 1否则ifmi12 thenM 2否则ifmi 3thenM 3否则ifmi4thenM 4否则M5结束该算法采用了三种交叉算子C1、C2和C3C1选择两个父母使用轮盘赌轮选择。C2将最佳cn亲本与随机选择的亲本杂交。然后,新的后代形成了。C3使用上述交叉算子子集的任意排列.这些算子在种群集中重复cn次,形成新的解(后代)。在此基础上,提出了五种变异算子,分别命名为M1突变算子、M2突变算子、M3突变算子、M4突变算子和M5突变算子。M1是两点突变,其中两个随机选择的基因在根据轮盘赌轮选择的染色体中交换。如果子代的适应值(成本)大于父代,则子代保持存活,而父代被摧毁。在文献中,这种方法被称为2-opt[14]。M2是两点突变的另一种类型。随机确定群体中的一个染色体和一个将要发生突变的基因数x,然后随机选择两个基因并交换x次。M3是一个三点突变。在这种突变中,使用轮盘赌选择来选择染色体确定了染色体上的三个不同基因,并通过排列这三个基因获得了五条新染色体具有最大适应值的染色体继续存活,而其他染色体被破坏。这种方法被称为3-opt[14]。在M4中,随机确定来自群体的随机染色体和行长度w,并选择两个行号作为起始点。然后从起始点开始相互交换wM5使用上述变异算子子集的任意排列.变异算子在种群集中重复mn次。在这些交叉和变异操作中的每一个之后,后代被评估并且非递增地插入到群体P t中。使用上述三个交叉和五个变异算子和两个遗传算法(第3节中的h1和h2)的初始化,30(30 = 3交叉5突变2遗传算法)GA实现已创建和测试。此外,GA已经由重复获得在C++中实现,并在具有2.30 GHz处理器和4GB RAM的i5-6200U机器上测试。测试问题取自带通问题库,其最佳解是已知的[12]。所有解决方 案 都 可 以 在 www.example.com 网 页 上 找 到 http://sci.ege.edu 。tr/math/BandpassProblemsLibrary/BP.rar在表1中,m是行数,n是列数,B是带通数,d是矩阵的非零元素的密度,单位为%,opt是问题实例(矩阵)的最优值,NB是通过启发式算法找到的带通数,Apprx示出了最优值的近似率,单位为%。其计算公式为NB=opt×100。我们使用算法h1和h2的结果作为遗传实现的初始种群。为方便读者,h0、h1和h2的最佳值很容易看出,h0没有比h1和h2找到的值更好的值。在表2中,C1 M1; C1 M2,. . 、C3M5示出了通过遗传实现发现的带通的数量。由于我们在使用h1和h2的解作为初始种群的遗传实现中获得了几乎相同的结果,因此我们在表2中列出了h2的结果。在下文中,我们讨论了启发式算法的结果的行数,列数,矩阵的密度,带通数和问题实例的难度。5.1. 启发式算法h0、h1和h2在一般情况下,而算法h0的平均近似率为66%的最优解,我们提出的启发式算法h1和h2有75%和77%,分别为所有的问题实例在图书馆。此外,我们还分析了h和h1的时间复杂度。 图 3,其中x轴表示问题实例,y轴表示所需的迭代次数,我们可以很容易地看到,对于所有问题实例,h 1的复杂度低于h 0。5.1.1. 矩阵的行列数、带通数和密度从图中可以看出。 4,当行数(见图)。 4(a))和列(见图 4(b)),矩阵的密度(见图。 4(c))和带通数(见图4(d))的增加,提出的启发式算法h 1和h 2都给出了比算法h 0更好的解决方案。y轴是对于相同类型的问题实例的结果的最优值5.1.2. 使用实例的难度级别进行比较让我们考虑一下带通问题最难解决的情况。当带通数和列数较大时,由于解空间中存在较多的备选方案,BP算法的求解将变得困难。另一方面,由于高密度将最小化可能的坏的替代品,解决方案将很容易达到。根据表3计算实例在列数、带通数和密度方面的难度水平。例如,一个实例的难度等级是8ðÞ×¼¼1536A. Gursoy等人/工程科学与技术,国际期刊20(2017)1531表1启发式算法的计算结果。H0H1h2矩阵MnBDoptNBApprx时间NBApprx时间NBApprx时间(%)(%)(秒)(%)(秒)(%)(秒)A28B56485252017850.48619950.32819950.015A29B56485353024800.861301000.59329970.001A30B8648825128670.749121000.5311920.031A31B86488351914741.47117890.99917890.031A32B166481625106602.9257702.0287700.093A33B166481635137543.58010772.46510770.141A34B564125253025831.25327900.84227900.047A35B564125354635761.06136780.71838830.39A36B864128252316702.09719831.41919830.078A37B864128353223723.16426812.23125780.889A38B1664121625178470.98710590.68610590.25A39B16641216352212551.71814641.1714640.125A40B564165254429662.34033751.59135800.078A41B564165356545693.25952802.21651780.437A42B864168253321640.94420610.65524730.125A43B864168354627591.08730650.73432700.25A44B16641616252413543.76516672.54315630.718A45B16641616353114452.21018581.54517550.202A46B89688251915790.56617890.37517890.016A47B89688352823824.65325893.2325890.093A48B169681625117646.24810914.33710910.156A49B1696816351610631.17011690.7811690.265A50B896168254227648.03731745.3231741.217A51B8961683561345618.988406612.65245740.608A52B16961616252914483.48517592.40217590.39A53B16961616353820535.41422583.68123611.201A54B8962582573446012.60150688.54953734.648A55B89625835103585612.08465638.14373711.81A56B169625162549244910.39331636.86531632.418A57B16962516356434538.08338595.30440630.843A58B1664816752316701.88117741.29521910.312A59B864128757161865.89566934.07166930.858A60B564165509672751.90776791.27979820.11A61B56425565205160784.229172842.871170831.747A62B86425865137100738.160107783.666107785.695A63B16642516506640616.91544674.72744671.108A64B1696816653022732.69725831.80925830.608A65B1696251650864755110.438515974.92754633.292A66B5968575110104954.4211101003.0271101000.001A67B89688756761916.838671004.618671000.125A68B169616166567487239.807527826.17651760.764A69B596165651871568317.6531638712.168163871.295A70B25961625252511443.73413522.57415601.498A71B89625850148906129.075946419.079102692.137A72B259625253550234643.872275411.95306029.765对于密度为25%的尺寸为64 × 8的矩阵,B8.在确定实例的难度级别之后,我们获得了表1中不同问题实例的范围从5到14的值。本文提出的启发式算法给出了一个更好的近似的最优解的情况下,具有高难度水平。 这可以在图中看到。 其中y轴表示通过算法正确找到的带通的近似百分比,并且DL表示难度水平。5.2. 遗传算法结果的讨论我们使用启发式算法h1和h2的输出作为遗传算法的初始种群。然而,我们得到了几乎相同的结果使用的输出,无论是化学。因此,我们分析了使用算法h2(通常比h1提供更好的解决方案)产生初始输入的15个实现的结果。根据表2,与通过h2获得的解相比,Meta启发式解的平均改进约为6%,然而,在某些情况下其增加到36%的最好的实现是C1M3、C2M1、C2M3、C3M1和C3M3。无论是轮盘赌轮(C1)或最佳亲本选择(C2)策略后的2-opt(M1)或3-opt(M3)变异算子保留染色体中的好基因注意,C3是C1和C2的置换。总之,我们可以说:当二进制矩阵的行数增加时,所有遗传实现都给出更好的结果。当列的数量增加时,所有的实现方式都给出了更好的结果。此外,实现C3M1给出了更好的解决方案比其他人。同样,C2M1、C2M3和C2M5对于具有大量列的实例给出了更好的结果当B增加时,所有实施方案给出更好的结果。此外,实现C3M1给出了比其他更好的结果当非零元素的密度增加时,所有的实现方式都给出更差的结果。虽然难度水平增加,但所有实现都给出了更好的结果。特别是C2M1、C2M3和C3M1给出了比其它更好的结果。●●●●●A. Gursoy等人 /工程科学与技术,国际期刊20(2017)1531-15391537表2遗传算法的计算结果与15个实现矩阵MnBDoptNB的h2C1M1C1M2C1M3C1M4C1M5C2M1C2M2C2M3C2M4C2M5C3M1C3M2C3M3C3M4C3M5时间(秒)A28B564852520192020202020201920201919192019200.57A29B564853530292929303029303030302929293030290.03A30B864882512111212121112121112121211121211120.04A31B8648835191717171717171717171717171717171720.54A32B16648162510777777777778777734.95A33B166481635131010111111111111111111111111111131.98A34B56412525302727272727272827272727272727272748.10A35B56412535463840414140384140424141414041404147.67A36B86412825231920202020202020202020202021202069.56A37B86412835322525262526252526252525252525252544.68A38B1664121625171012111010101210101010131010121194.66A39B1664121635221415151615151716151515191417151795.14A40B56416525443536373636393636383838383637363683.10A41B56416535655155525455555455545353535353545481.43A42B864168253324252526242624262426252424252626142.96A43B864168354632353536353535353534353335353436128.41A44B16641616252415181718181720181818181918161718144.42A45B16641616353117181717171717171818171717181717152.01A46B8968825191718171817171917181718181717171760.03A47B8968835282525262625262626262626262626262648.63A48B169681625111010101010101010101010101010101097.32A49B169681635161111111111121111121313121211111186.45A50B896168254231313232333332323131353232323132470.92A51B896168356145464545454646484648484545464646435.00A52B16961616252917191818171819191918182018181718622.22A53B16961616353823242425242323242424242423272325673.40A54B8962582573536155655559615961576360556056601394.36A55B8962583510373817984808584848784847675847884956.23A56B169625162549313634403337383638353835323635371519.80A57B169625163564404444444444454545444743444644451971.81A58B166481675232121212121212121212121212121212128.08A59B86412875716667666766666767676766666767676751.31A60B56416550967982828282828280827982828082828180.76A61B56425565205170172172176172176172172175173177177173177171176170.21A62B86425865137107107107108107107107107107107109107107109107108217.49A63B16642516506644454444444445464545454544454444513.52A64B169681665302525252525252525252525262525252559.83A65B169625165086545656555554545454545558545654581572.20A66B59685751101101101101101101101101101101101101101101101101100.07A67B896887567676767676767676767676767676767670.12A68B16961616656751535353535353535353535352535253488.01A69B59616565187163168167170168168169163169169170167167168168168368.45A70B25961625252515151518221815161815161915181718679.57A71B896258501481021091071091071091101121111071091121051121081101098.24A72B259625253550303030303030303030303030303030302014.27图三. 算法h0和h1的时间复杂度图。1538A. Gursoy等人/工程科学与技术,国际期刊20(2017)1531图四、根据行数(a)和列数(b)、密度(c)和带通数(d)的启发式算法的性能表3实例难度级别的分数(点)MnB密度%+1便士,如果64+1p如果8+1p如果5+4p如果25+2p如果96+2p如果1216岁时+3便士+4p如果25+2p如果8+3便士,如果12+4p如果16+5便士,如果25如果35岁,则+2p如果50如果50+,则图五.根据实例的难易程度以图形表示表1。在15种实现中,对于所有实例,没有一种交叉和变异操作符的特定组合优于所有其它操作符。6. 结论本文介绍了两种求解带通问题的启发式算法,它们对不同的二元矩阵都有较好的结果。在我们的启发式算法中,我们考虑了许多不同的标准。这些算法中的价值函数是根据这些准则的重要性来计算的。然后,提出的遗传算法,使用不同的交叉和变异算子的一些解决方案进行了改进。确认作者要感谢匿名评审的宝贵意见,这些意见大大改善了论文的呈现。这项工作得到了土耳其科学技术研究委员会-TUBITAK 3001项目(项目编号:114 F073)。引用[1] G. Bell,D.刘文,带通问题,载于:信息年会,2004年10月,美国科罗拉多州丹佛市。[2] D.A. Babayev,G.I.贝尔大学Nuriyev,带通问题:组合优化和问 题 库,J。 Comb.Optim。 18(2009)151-172。●A. Gursoy等人 /工程科学与技术,国际期刊20(2017)1531-15391539[3] U.G. Nuriyev,H.库图库湾李明,带通问题的数学模型和有序计算机游戏,数学。模型53(2011)1282-1288。[4] M.库尔特,H。Kutucu,A.古尔索伊Nuriyev,多带通问题中带通滤波器的优化,Springer , 柏 林 海 德 堡 , 柏 林 , 海 德 堡 , 2014 年 , pp.115-123https://doi.org/10.1007/978-3-642-40078-09网站。[5] G. 关于带通问题,J. Comb. Optim。 22(2011)71-77。[6] Z. Li,G.林,三列带通问题在线性时间内可解,理论计算。Sci. 412(2011)281-299。[7] W. 通 河 , 巴 西 - 地 Goebel , W. 丁 氏 G.Lin , An Improved ApproximationAlgorithm for the Bandpass Problem , Springer , Berlin Heidel
下载后可阅读完整内容,剩余1页未读,立即下载
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![.pdf](https://img-home.csdnimg.cn/images/20210720083646.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)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 藏经阁-应用多活技术白皮书-40.pdf
- 藏经阁-阿里云计算巢加速器:让优秀的软件生于云、长于云-90.pdf
- 藏经阁-玩转AIGC与应用部署-92.pdf
- 藏经阁-程序员面试宝典-193.pdf
- 藏经阁-Hologres 一站式实时数仓客户案例集-223.pdf
- 藏经阁-一站式结构化数据存储Tablestore实战手册-206.pdf
- 藏经阁-阿里云产品九月刊-223.pdf
- 藏经阁-2023云原生实战案例集-179.pdf
- 藏经阁-Nacos架构&原理-326.pdf
- ZTE电联中频一张网配置指导书
- 企业级数据治理之数据安全追溯
- MISRA-C 2012-中文翻译版.pdf
- 藏经阁-《多媒体行业质量成本优化及容灾方案白皮书》-37.pdf
- 藏经阁-浅谈阿里云通用产品线Serverless的小小演化史-23.pdf
- 藏经阁-冬季实战营第一期:从零到一上手玩转云服务器-44.pdf
- 藏经阁-云上自动化运维宝典-248.pdf
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)