埃及信息学杂志18（2017）221全文离散蝙蝠算法中改进的均匀交叉和2-交换邻域机制求解二次分配问题Mohammed Essaid Riffia，Yassine Sajia，Mohammed Barkatouba摩洛哥贾迪达24000本马舒路Chouaïb Doukkali大学理学院计算机科学系LAROSERI实验室bChouaïb Doukkali大学，数学系，理学院，Route Ben Maachou，24000 El Jadida，摩洛哥阿提奇莱因福奥文章历史记录：2016年1月21日收到2016年11月13日修订2017年2月22日接受在线提供2017年保留字：蝙蝠算法二次指派问题NP-难问题组合优化问题A B S T R A C T蝙蝠算法是最近的自然启发式算法之一，它已成为一个强大的搜索方法，解决连续以及离散问题。二次分配问题是组合优化中一个著名的NP-难问题。该问题的目标是将n个设施分配到n个位置，以使分配成本最小化。为此，本文提出了一种新的离散蝙蝠算法来处理这一组合优化问题。在QAPLIB库中的一组基准实例上对该算法进行了评估，并将其性能与其他算法进行了比较。详尽的实验的实证结果是有希望的，并说明了所建议的方法的有效性©2017制作和主办由Elsevier B.V.代表开罗大学计算机和信息学院这是一篇CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍元分析是解决工业、经济和科学领域中大量复杂组合问题的一个重要途径。这些问题中的大多数是非确定性多项式时间困难的NP-hard[1，2]，即，没有多项式时间算法来求解它们。解决这样的组合优化问题需要涉及在有限搜索空间中的解的集合中搜索最优解。长期以来，自然界一直是许多科学家的丰富源泉。从自然界最成功的过程中汲取灵感，研究人员开发了一类元算法，即自然启发算法。受自然启发的算法提供了比经典算法更多的优势[3]，并且它们还寻求在合理的时间内找到可接受的结果，而不是保证最佳性能的能力。*通讯作者。电子邮件地址：yassine. gmail.com（Y。Saji）。开罗大学计算机和信息系负责同行审查。或次优解决方案。此外，大多数元启发式算法是基于群体智能，生物系统，物理和化学系统[4]。特别是，群智能算法已经显示出其有前途的性能，并且它们在解决许多工程优化问题中获得了很大的普及;例如粒子群优化[5]，蜘蛛猴[6]，布谷鸟搜索[7]，蜂群优化[8]，萤火虫算法[9]以及近年来的蝙蝠启发算法[10，11]。二次分配问题（QAP）被证明是最难的组合优化问题之一[12]，并且没有多项式时间算法可以精确地解决大型实例的问题，有时甚至小型实例也可能需要相当长的计算时间。在组合优化的文献中，研究人员已经应用了不同的方法，从算法或元算法直到混合方法，来找到QAP问题的最优或接近最优的解决方案QAP问题最广泛使用的启发式算法是模拟退火[13]、禁忌搜索[14]、神经网络[15]、蚁群[16]、模因算法[17]、遗传算法[18]、迭代局部搜索[19]、混合算法[20]、超大规模邻域搜索[21]、粒子群优化[22]、蝙蝠算法[23]和蜜蜂算法[24]。蝙蝠启发算法（BA）是一种基于种群的随机优化技术，最近已被应用于http://dx.doi.org/10.1016/j.eij.2017.02.0031110-8665/©2017制作和主办Elsevier B. V.代表开罗大学计算机和信息学院这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表埃及信息学杂志杂志主页：www.sciencedirect.com222法医Riffi等人/Egyptian Informatics Journal 18（2017）221许多应用程序。该算法是为处理连续优化问题而发展起来的，特别是BA算法在解决离散优化问题时也被证明是有效的。由于精确和启发式方法的QAP的复杂性，这个问题是一个合适的测试平台，新的优化技术。因此，QAP的改进方法的设计仍然是许多研究人员面临的挑战。本研究探讨BA的适用性，以提供一个很好的解决方案的质量和执行时间之间的妥协。 为此，本文引入了一种新的离散版本的BA命名为离散蝙蝠算法（DBA）通过涉及一些修改的原始算法。首先，这些修改涉及位置表示及其更新方程，以及速度表示及其更新方程。其次，我们将一个修改的均匀交叉算子的运动方程。这个想法旨在加强BA的搜索策略。第三，我们使用2-交换邻域机制来改进BA的局部搜索。最后，我们调整了一些合适的参数值，以平衡BA的集约化和多样化能力。我们将我们提出的方法的性能与当前文献中的五种算法进行了比较：蜜蜂算法（BeA）[24]，修改的蝙蝠算法（MBA）[23]，具有顺序构造性交叉的遗传算法（SCX）[25]，混合蚁群系统与QAP（HAS-QAP）[16]和分层粒子群优化（HPSO）[22]。本文的其余部分组织如下：第二部分介绍了BA的文献综述。第三节介绍了BA的起源。 第4节描述了二次分配问题。第5节讨论了我们的离散方法，并详细介绍了其主要组成部分。计算实验和讨论的结果在第6节中给出。最后，在第七部分给出了研究结论和研究展望.2. 相关工作BA是一种基于微蝙蝠在搜索猎物时的回声行为的群体智能算法最初，这种算法已经被开发用于优化连续非线性函数[10，26].实际上，该算法在应用于解决各种优化问题时显示出良好的效率[27]。在目前的文献中，BA的许多变体已经被引入，以增强或实现原始算法来解决不同类型的问题。Gandomi和Yang在BA中集成了混沌机制，以提高基本算法的全局搜索移动性，并有效地优化了一组基准问题[28]。Cai等人引入了带有BA的高斯行走以增强局部搜索能力，并且他们修改了速度方程以确保搜索空间的良好利用[29]。Khan等人介绍了BA的模糊修改，用于公司工作场所的聚类[30]。Yılmaz和Küçüksille在结构中嵌入了两个修改，以增强局部和全局搜索，他们还使用标准测试函数和约束现实问题来验证所提出方法的有效性[11]。Nguyen等人将基于通信策略的BA和人工蜂群算法混合用于群智能算法，图1.一、二次分配问题的说明性示例，其中置换p1/4 = 2;4; 3;1/4对应于最优解。法医Riffi等人/Egyptian Informatics Journal 18（2017）221223不我我我我我我我我我我我提高两种算法的收敛性和准确性[31]。Fister等人在原始BA算法中引入了两种机制以获得混合自适应BA，第一种是控制参数的自适应，第二种是使用四种DE策略作为局部搜索算法的自适应BA的混合[32]。Mirjalili等人使用sigmoid函数提出了BA的二进制版本来解决单峰，多峰，其中0表示根本没有脉冲，1表示脉冲发射的最大速率。3. 响度从大（正）A0变化到最小恒定值Amin。算法1中总结了BA在其原始论文中提出的基本伪码。timodal和复合函数[33]。Chen等人雇用多普勒效应，以提高BA在解决优化问题中的效率[34]。虽然BA被广泛用于解决连续问题，但在2012年之前，基本BA的应用尚未被有效地开发用于解决离散问题。Nakamura等人提出的第一个二进制版本[35]在2012年解决分类和特征选择问题。 它们保持了原始算法的相同结构，同时通过使用sigmoid函数转换了全局和局部位置更新。近年来，许多研究都集中在用BA来解决一些离散问题。例如，Xie等人提出了一种差分Lévy-flights BA来优化置换流水车间问题[36]。Luo等人将一种密集的虚拟种群邻域搜索集成到所提出的DBA中，以解决最优置换流水车间调度问题[37]。 Sabba和Chikhi提出了一种基于sigmoid函数的离散二进制BA，用于解决多维背包问题[38]。Büyüksaatça使用BA解决单行设施布局问题[39]。Fister等人介绍了一种改进的蝙蝠算法，用于规划运动训练课程[40]。Dekhici和Belkadi将BA的离散版本与广义进化行走算法混合，以解决单处理器两阶段柔性流水车间[41]。Hasançebi和Carbas介绍了一种用于最小重量钢框架结构优化的BA，他们使用了三个实际尺寸的大型钢框架来验证其方法的性能[42，43]。Eslam等人使用离散BA来寻找社交网络中的社区结构[44]。Saji等人介绍算法1：蝙蝠算法1. 目标函数f（x），x=（x1，. . ，xd）T2. 初始化蝙蝠种群xi（i=1，2，. . . ，n）和vi3. 定义xi处的脉冲频率fi4. 初始化脉搏率ri和响度Ai5. while（t最大迭代）6. 对于i=1到m7. 通过调整频率生成新的解决方案8. 以及更新速度和位置/解/方程（1）、（2）和（3）9. if（i）10. 从当前迭代的最佳解决方案中选择一个解决方案11. 围绕选定的最佳解决方案生成本地解决方案12. end if13. 通过随机飞行生成新的解决方案14. 如果（randAif（xi）f（x<$））//xi是当前解且x<$是全球最佳解决方案15. 接受新的解决方案16. 增加ri并减少Ai//等式（5）和（6）17. end if18. 端19. 对蝙蝠进行排名并找到当前全球最佳的蝙蝠20. end while21. 后处理结果和可视化BA的两个离散变体来解决欧几里德旅行销售-人的问题[45，46]等等。正如我们之前提到BA已经被应用于许多离散优化问题，无论如何，它很少被应用于任何分配问题[23]。在本文中，我们提出了一种新的离散版本的BA，在BA中，在迭代t处，人工蝙蝠xi由位置向量xi、速度向量vt、频率向量fi和脉搏率rt和响度At，它们在研究过程将二次分配问题作为NP-hard问题求解[12]i i在组合优化中。3. 蝙蝠算法找到最好的解决方案，如Eqs。（1）（3）：fi¼fmin最小值f max-f min最小值b;vt<$vt-1xt-1-xωfi; 22010年由杨新社首次提出[10]。该算法通过模拟微型蝙蝠xt¼xt-1vt;3当寻找它们的猎物时，甚至在完全黑暗的情况下，通过改变发射和响度的脉冲速率来区分不同类型的昆虫。回声定位指导蝙蝠的狩猎策略，因为这些最后往往会根据它们的接近程度降低音量并增加发射超声波的速率。其中b 2 [0，1]是从均匀分布生成的随机向量，并且其中x/是在比较所有m个蝙蝠中的所有解之后定位的当前全局最佳解。对于局部搜索，将通过使用随机游走在当前最佳解周围接受新的解目标基于蝙蝠的回声定位行为，杨在[10]中x新1/4旧 苯丙氨酸甲酰胺使用以下三个理想化规则描述了BA的基本步骤1. 所有的蝙蝠都使用回声定位来感知距离，它们也2. 蝙蝠以速度vi在位置xi随机飞行，频率固定，频率fmin，改变波长k和响度A0来搜索猎物 它们可以自动调整波长（或频率），其中e2[-1，1]是随机数，而At1/4hAti是当前时间步长处所有蝙蝠的平均响度在飞行过程中，每当接受新的最佳解时，响度Ai和脉冲发射率ri将响度和脉冲发射率更新如下：At1¼aAt; 5我我频率），并调整脉冲的速率发射r在[0，1]的范围内，取决于接近度rt1<$r0½1-exp-ct];6蝙蝠启发式算法是一种元启发式搜索优化算法224法医Riffi等人/Egyptian Informatics Journal 18（2017）221图二. 排序功能的图示。图三. 修改的均匀交叉（UX）示例。其中a，c是两个常数，通常a=c，A0和r0是随机选择的。 这些参数目标是最大限度地减少设施分配到各个地点的成本，同时考虑到距离乘以我我需要一些实验，并取决于解决的问题。4. 二次分配问题QAP是组合优化问题中的一个重要问题。这个问题最初是由Koopmans和Beckmann在1957年提出的[47]，并被归类为NP难问题[12]。QAP被描述为一个问题，以分配一组n个设施的一组n个位置的方式，每个位置被指定为正好一个设施，反之亦然。对于每一对设施与地点的分配成本是已知的。的所有设施之间的相应流量。表1问题的参数参数值人口规模：m15排放率ri0.5，ri2½0：0;1：0]响度Ai0.5，Ai2½0：0;1：0]最小频率fmin1最大频率fmax2最大迭代次数tmax200法医Riffi等人/Egyptian Informatics Journal 18（2017）2212252fg2fg联系我们ðÞðÞÞ20B1CBB@CAB是距离矩阵公司简介01@A在形式上，QAP可以表述为给定n个设施，n个位置，以及两个矩阵A<$aij j<$n×n和B<$aijk l<$n×n，其中aij是设施i和j之间的流量，对于所有i，j 1; 2;. kl是位置k和l之间的距离，对于所有k，l1; 2;.. ;n.目标的这问题是到找到的置换pωp1;p2;.;pn（所有可能排列的P个集合），其最小化成本函数C：021 3201 2¼1103;323 0除了设施选址问题外，QAP还可用于解决各种科学和工业问题，如打字机键盘的设计、计算机中的背板布线、计算机中的布线和电子，平衡涡轮机转轮，布局设计，数据分配，nnCpωmQinXXaijbpipj7联系我们时间表，还有很多其他的。 QAP可以转化为许多经典的组合优化问题，如旅行推销员[48]，图分割问题[48]，最大-让我们考虑一下将四个设施分配给四个设施的问题两个矩阵A和B。在图1中，一对设施之间的虚线表示设施之间需要流量，并且为了计算置换的分配成本，需要位置之间的距离。一种可能的分配是将设施点1放置到位置3，设施点2到位置4，设施3到位置1，设施4到位置2.这分配可以被书面作为置换但它不一定是最优的。022 0一个2011A是流量矩阵210 3013 0mum团[48]，数据分配问题[49]，武器目标分配[50]。5. QAP的离散蝙蝠算法基本上，标准BA是为优化连续非线性函数而开发的连续优化算法[10，26];然而，该算法不能直接用于解决离散问题。本文在原有BA的基础上设计了一个DBA为了将DBA应用于QAP，对基本方程进行了一些修改：第一次修改涉及位置和速度表示;第二次修改涉及位置更新方程。见图4。 当r为1时，char 25a、nug 30、tai20a、sko 42、wil 50和sko 81的最佳解为： A i 在0和1之间变化。p2226法医Riffi等人/Egyptian Informatics Journal 18（2017）221XQQ.Σ2QQ！2nQQ¼82ð Þð Þ ð Þ我图五. 当r为1时，chr25a、nug30、tai20a、sko42、wil50和sko81的最佳解均为 A i 等于0.5。另外，对于组合问题，通常采用邻域搜索的方法来提高解的质量。本文研究了2-交换邻域函数在对称的情况下，公式（8）更简单并且可以重写如下：n是一种适用于QAP的邻域搜索方法。 此函数的详细信息将在下面介绍分段。Dcp;i;jk¼1;ka0ik-a0jk5.1. 2-Exchange社区在QAP的上下文中，我们记得，目标是找到一个置换p的n个元素，最大限度地减少方程。（7），其中p2P.2-交换邻域p0由置换集得到哪里A0<$a0ij<$n×n=a0ij<$aij<$aj i;i;j<$1;2;。 . . ;n;i- j ; a 0 ii <$a i i ; i<$1; 2 ;.如果A是非对称流矩阵，则n是新的对称流矩阵（更多细节参见[51]）。本文中使用的局部搜索算法的概要在算法2中示出。算法2：局部搜索算法这可以通过应用下面的成对交换来实现ing邻域函数N ：2它定义了p2p，N2的一组相邻解fp0jp02;其中，是置换p和p0之间的汉明距离。 相邻置换（解）p02N2<$p<$由p通过应用交换移动v<$p;i;j<$：×N×N得到！，在当前的第i个和第j个元素之间溶液 p，的意味p0ipj，p0jpi，p0k pk，k1;2... ;n;k-i; k-j，记为p 0 <$p v <$p ; i ; j <$p。选择一对交换元素的准则所有可能的对等于n<$n-1 <$n由以下公式计算：Dcp;i;jaii-ajjbpjpj-bpipjaij-ajibpjpi-bpipj1. 过程local_search2. 重复3.生成相邻解p02N2p;4.if（Cp0<$Cp<$）5.p p0;6.end if7. 直到（p0N2p;Cp0 PC （p）8. 结束程序5.2. 位置和速度方程在Yang[10]开发的基本BA中，每个虚拟蝙蝠在n维搜索空间中的运动（n是问题的大小k¼X1;kaik-ajk由两个向量表示位置和速度在搜索过程中，蝙蝠倾向于飞向最佳位置（solu-t），通过更新它们的速度v tþðaki-akjÞðbpðk Þp ðj Þ-bp ðk Þp ði ÞÞð8Þ其中aii，bii= 0，i= 1，2，.. .，n.我以及在时间步长t处的位置xt。因此，在QAP的情况下，由第i个蝙蝠找到的n个分配的解由n表示，法医Riffi等人/Egyptian Informatics Journal 18（2017）221227我我我我我我¼ðÞ我维向量xi1;xi2;. . . ;xi n. 速度v i被视为一组置换pi^fp1;p2;. . ;png，其允许接近全局最佳解xωxω1;xω2;.. ;xωn.标准位置更新和速度方程将被重新定义如下：vt1¼wxt;xω;fi10在这种情况下，方程中的函数w （10）是具有三个参数的交叉函数，并返回一组排列pt。频率f i是一个整数（介于fmin和fmax之间），表示从x ω或x t复制的段的大小 到的后代（此提出功能是更中详述图 3）。方程中的函数r （11）用于对位置进行排序我我分配在x测试中 在尊重pt这个模板xt1rxt;vt1 11表2来自QAPLIB[59]的一些实例的DBA算法的结果。例如BKV最好最糟糕SD%davg%d最佳tav gsbur26a5,426,6705,426,6705,426,6700.000.000.001.10bur26b3,817,8523,817,8523,817,8520.000.000.000.80BUR26C5,426,7955,426,7955,426,7950.000.000.000.75BUR26D3,821,2253,821,2253,821,2250.000.000.000.90BUR26E5,386,8795,386,8795,386,8790.000.000.000.82BUR26F3,782,0443,782,0443,782,0440.000.000.000.43布尔26g10,117,17210,117,17210,117,1720.000.000.000.21BUR26H7,098,6587,098,6587,098,6580.000.000.000.35chr12a9552955295520.000.000.000.09chr15b7990799079900.000.000.000.86chr18a11,09811,09811,682227.201.060.000.05chr20c14,14214,14214,1420.000.000.000.30chr25a379637964410190.958.320.005.96els1917,212,54817,212,54817,212,5480.000.000.000.08esc16a6868680.000.000.000.00esc16b2922922920.000.000.000.00esc16c1601601600.000.000.000.00esc16d1616160.000.000.000.00esc16e2828280.000.000.000.00esc16f0000.000.000.000.00esc32a1301301300.000.000.000.02esc32e2220.000.000.000.03esc32g6660.000.000.000.02esc64a1161161660.000.000.000.18wil5048,81648,84448,95427.770.140.05115.67nug202570257025700.000.000.000.88nug212438243824380.000.000.000.12kra30a88,90088,90090,670678.820.380.000.26kra30b91,42091,42091,69097.570.110.002.12nug3061246124617619.050.210.004.9rou20725,522725,662731,7981904.80.360.017tai12a224,416224,416224,4160.000.000.000.00tai12b39,464,92539,464,92539,464,9250.000.000.000.01tai15a388,214388,214388,2140.000.000.000.50tai15b51,765,26851,765,26851,765,2680.000.000.000.09tai17a491,812491,812491,8120.000.000.000.39tai20a703,482703,482712,6002891.90.850.000.18tai20b122,455,319122,455,319122,455,3190.000.000.000.11tai25a1,167,2561,172,7541,192,0306642.31.510.4712.10tai25b344,355,646344,355,646344,355,6460.000.000.001.72tai30a1,818,1461,831,2721,854,6408066.61.340.7220.25tai30b637,117,113637,117,113637,917,440291418.90.020.003.30tai35a2,422,0022,438,4402,477,55410798.691.790.6735.43tai35b283,315,445283,315,445284,457,830290275.70.190.0020.01tai40a3,139,3703,139,3703,217,01810679.32.021.351.12tai40b637,250,948637,250,948637,376,82538744.10.000.0014.86tai50a4,938,7965,042,6545,080,43010982.32.692.10100tai50b458,821,517458,830,119461,082,283663488.40.110.00126.34tai60a7,205,9627,387,4827,411,0006163.052.732.5166.23tai60b608,215,054608,414,385609,014,871155656.20.090.03221.65tai64c1,855,9281,855,9281,855,9280.000.000.000.26tai80a13,499,18413,810,13013,891,05421496.42.672.30420.62tai80b818,415,043819,367,807825,968,5252386128.50.560.11532.41tai100a21,052,46621,541,32621,632,42824712.62.52.31045.27tai100b118599613711881687531190873912906873.10.290.181126.25sko4215,81215,81215,91628.170.300.0042.87sko4923,38623,42123,57037.970.340.1497.71sko5634,45834,52434,70056.160.460.19159.8sko6448,49848,65648,80242.940.440.32265.63sko7266,25666,42266,65877.790.460.25361.59sko8190,99891,25291,828151.650.450.27512.73sko90115,534115,874116,378121.300.480.29653.61粗体显示的值表示每个实例都达到了最佳解决方案。函数在图中给出。 二、228法医Riffi等人/Egyptian Informatics Journal 18（2017）2215.3. 交叉操作在遗传算法中首次引入交叉操作产生新的种群。交叉背后的想法是在生产新一代时从每个父母那里受益最好的特征。在文献中，提出了多种交叉算子来解决二次分配问题，例如有序交叉（OX）[52]、循环交叉（CX）[17]、多父交叉（MPX）[53]、交换路径交叉（SPX）[54]、部分映 射交叉（ PMX）[55] 、内 聚交叉（ COHX）[56] 、一 点交叉（OPX）[57]和均匀交叉（UX）[58]。为了增加种群的多样性并避免过早收敛到搜索空间中的不期望区域，我们提出了对均匀交叉（UX）的一些修改[58]。本文采用改进的均匀交叉算子（UX）来增强BA的搜索策略与标准的交叉（UX）过程一样，扫描每个父代的顺序是从左到右，并且在两个父代个体中分配到相同位置的所有项目都被复制到后代中的这个位置未分配的项将被分组在大小为f（频率）的片段第一个片段从父元素之一复制到子元素;其余元素（第二个片段）如果尚未包含在子元素中，则从另一个父元素复制否则，如果在子节点中仍然有任何未分配的位置，则可以从第一个或第二个父节点中取出缺失的项目，以使其不会在子节点中出现两次这种交叉过程的一个例子如图所示。3.第三章。5.4. 离散bat算法在DBA中，控制参数如表1中所述初始化，预期初始解xi为每个蝙蝠随机生成 在搜索过程中，蝙蝠使用一种算法来交流它们之间的最佳全局解决方案。为了生成一个新的解决方案，每个蝙蝠调整其频率并更新其当前的速度和位置（等式2 ）。（ 1 ）、（ 10 ）和（11））。然后，根据脉冲发射率ri从最佳解中选择一个解。然后，通过使用算法2以改进当前解和迄今为止找到的最佳全局解的方式局部地改变所选择的解。然后，表3BeA[24]和DBA解决QAPLIB[59]中一些实例的比较结果。例如BKVBeaDBA最好我最好t（ms）%d最佳最好我最好t（ms）%d最佳chr12a955295522893750.009552816.200.00chr15b799079902224520.0079902049.370.00esc16a686825140.006810.000.00had1637203720244680.003720871.290.00chr18a11,09811,1181705300.1811,09815519.730.00chr20c14,14214,1425436090.0014,1429774.910.00rou20725,522727,3227005900.25725,52288116.600.00tai20a703,482724,4724466712.98703,48217351.800.00nug21243824426037470.1624389798.820.00chr25a3796379697411560.003796126108.720.00bur26a5,426,6705,431,6408328260.095,426,67065130.580.00bur26b3,817,8523,817,9483357960.003,817,85239168.930.00esc32a130144902109210.77130192164.460.00wil5048,81650,21699123712.8748,844320507.360.05esc64a11611634030270.0011610.000.00tai80a13,499,18414,784,38073740879.5213,810,1303453208.332.30粗体显示的值表示每个实例都达到了最佳解决方案。表4MBA[23]和DBA解决QAPLIB[59]中一些实例的比较结果。例如BKVMBADBA最好最糟糕平均%davg最好最糟糕平均%davgbur26a5,426,6705,519,1085,537,9735,530,8251.905,426,6705,426,6705,426,6700.00bur26b3,817,8523,895,5073,905,0483,898,4022.103,817,8523,817,8523,817,8520.00BUR26C5,426,7955,520,2895,526,2005,523,9701.795,426,7955,426,7955,426,7950.00BUR26D3,821,2253,879,8143,897,0393,887,2161.723,821,2253,821,2253,821,2250.00BUR26E5,386,8795,491,088550,6335,500,4602.105,386,8795,386,8795,386,8790.00BUR26F3,782,0443,830,6143,861,2403,850,6921.803,782,0443,782,0443,782,0440.00布尔26g10,117,17210,320,12010,342,56010,328,6992.0910,117,17210,117,17210,117,1720.00BUR26H7,098,6587,251,0467,278,1827,267,3932.377,098,6587,098,6587,098,6580.00esc32e22220.002220.00esc32g66660.006660.00esc16a686868680.006868680.00esc16b2922922922920.002922922920.00esc16c1601601601600.001601601600.00esc16d161616160.001616160.00esc16e282828280.002828280.00esc16f00000.000000.00lipa20a36833821382938243.83683368336830.00lipa30a13,17813,61413,62513,6183.313,17813,17813,1780.00粗体显示的值表示每个实例都达到了最佳解决方案。法医Riffi等人/Egyptian Informatics Journal 18（2017）221229半]Cωp>1400新的解决方案的适应性根据Eq.（7）并生成随机解基于由响度值Ai计算的接受率，接受最后评估的解，如果改进最佳全局解。最后，最佳的全球解决方案被传达到下一代和搜索过程的进展，直到达到最大数量的迭代。用于优化QAP的伪代码中的整个DBA被总结在算法3中。不成功的解决方案。基于图5，实验表明，当脉冲发射率和响度的值在0.4和0.6之间时，DBA可以提供良好的结果。为了微调这两个参数并实现所需性能，这些值固定为0.5。此外，表2总结了DBA算法在50次独立运行中针对62个实例的数值结果第一列第二列中所示的BKV代表了由以下文献报告的最佳已知溶液值：QAPLIB库和第三列中描述的“最佳”值算法3：离散蝙蝠算法1. 目标函数f（x），x=（x1，.、.、xd）T2. 初始化蝙蝠种群的大小3. 为每个蝙蝠生成一个随机的起始解xi4. 初始化发射速率ri2½0：0;1：0]和响度Ai2½0：0;1：0]。5. 将脉冲频率f min和f max定义为范围1; 2.6. while（t最大迭代）是DBA在50次运行中找到的最佳值。列“最差”表示DBA找到的最差解决方案。“SD”列表示标准偏差。其余各栏分别表示下列业绩计量：通过以下公式计算50次运行中发现的最佳值与最佳已知值的百分比偏差C最佳-Cω7. 对于i=1到m8. 通过调整频率生成新的解决方案%d最佳¼C×100 ð12Þ9. 以及更新速度和位置/解/方程（1）、（10）和（11）10. if（i）11. 从当前迭代的最佳解决方案中选择一个解决方案12. 通过使用局部搜索算法在所选择的最佳解周围生成局部解。13. end if14. 根据等式（7）评估新的解（适应度i=C（xi15. 通过随机飞行生成新的解决方案16. 如果（randAifitnessiC（x<$））//x<$is全局最优解17. 接受新的解决方案18. 增加ri并减少Ai//等式（5）和（6）19. end if20. 端21. 对蝙蝠进行排名并找到当前全球最佳的蝙蝠22. end while23. 后处理结果和可视化其中Cbest是在50次运行中发现的最佳目标值，Cω是从QAPLIB中获得的最著名的值。通过下式计算50次运行中平均溶液与最佳已知溶液值的百分比偏差：% davg ¼Cavg-Cω×100 13其中Cavg是50次运行的平均目标函数值最后一列此外，表3除了前面提到的性能测量之外，在表3中，列列在表4中，列“平均”表示找到的在表6中，列年龄百分比偏差，即成本超过BKV的百分比）。表7显示了每一个以上的平均等级6. 计算结果和讨论6.1. 结果整 个 算 法 在 MATLAB R2010 a 中 实 现 ， 并 在 Intel （ R ） Core（TM）2 Duo CPU T4300@2.1GHZ 800 MHz和2.00 GB RAM下进行仿真。测试实例取自标准QAPLIB[59]。测试实例的大小从12到100不等，并在名称中提到的实例。例如，在名为nug30的实例中，数字30表示提供的设施的数量。表1总结了DBA算法的参数值。这些参数值的选择是基于使用QAPLIB基准的子集的初步实验。此外，脉冲发射率和响度是DBA和标准BA的两个重要参数，调整合适的值对解决方案的质量有着至关重要的影响。图4指示当ri和Ai在 0 和 1 之间变化时 chr25a 、 nug30 、 tai20a 、 sko42 、 wil50 和sko81的最佳解。图5呈现了当 ri和 Ai等于0.5时chr25a、nug30、tai20a、sko42、wil50和sko81的最佳解。图4中的预实验表明，小的响度值类似于大的发射率值，引起快速收敛每个配对的常见问题实例（DBA与SCX的16个问题实例，DBA与MBA的18个问题实例DBA与HAS-QAP的23个问题实例和DBA与HPSO的44个问题实例）。为了确定DBA和其他算法之间的显著差异，我们应用Wilcoxon符号秩检验[60]（a= 0.05水平）作为常用的非参数统计检验。在该比较中，我们使用DBA作为控制方法，并考虑使用Holm-Bonferroni逐步下降法[61]在α= 0.05水平下控制全族错误率[62]Holm-Bonferroni逐步下降程序类似于用于多个假设检验的经典Bonferroni校正。为了描述Holm-Bonferroni步骤-下程序，让p16p26...6pm是m个单独测试的有序p值，H1;H2;...;Hm对应的有序假设设k为验证一Km1-k如果不存在这样的k，则拒绝所有的零假设，否则零假设H1，.;Hk-1被拒绝，
我的内容管理
展开
