XX工程科学与技术，国际期刊21（2018）843完整文章基于GPU的二次分配问题的并行多起点模拟Emrullah Sonuca，Mr.，Baha Senb，Safak Bayiraa土耳其卡拉布克大学计算机工程系b土耳其耶尔德勒姆大学计算机工程系阿提奇莱因福奥文章历史记录：2018年5月9日收到2018年8月1日修订2018年8月1日接受在线提供2018年8月14日保留字：组合优化CUDAGPU多起点模拟退火并行算法二次分配问题A B S T R A C TGPU硬件和CUDA架构为并行算法的开发提供了强大的平台。启发式和元启发式算法在GPU上的实现在文献中是有限的。在GPU上开发并行算法已成为当前研究的热点。本文讨论了组合优化问题之一的NP-Hard二次指派问题（QAP）。采用CUDA结构开发了并行多开始模拟退火算法（PMSA）来求解QAP.通过提供多线程启动技术和线程间的协作，实现了一种高效的方法。在相同和不同块中的线程都发生了合作。本文着重于加速和解决方案的质量。在许多二次分配问题库（QAPLIB）实例上进行的计算实验。实验结果表明，PMSA的运行速度比单核CPU快29倍，并在许多基准数据集上在短时间内获得最佳已知解。©2018 Karabuk University. Elsevier B.V.的出版服务。这是CCBY-NC-ND许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍二次分配问题（QAP）是Koopsman和Beckman于1957年提出的一个数学模型，并应用于经济活动领域[1]。QAP是NP难的组合优化问题之一。 该问题的目的是分配n数量的设施，以最小的成本的n个位置。当问题解决完成后，每个设施将被分配到一个位置，任何设施都不应该是空的。 作为一个置换问题，QAP可以用数学公式表示如下：QAP被用于确定背板布线组件之间的连接数量[2]，调度问题[3]，打字机键盘的设计，以及考古学[5]和数值分析[6]领域的控制面板[4]。与它们一起，其最常见的使用领域被视为设施布局问题。Dickey和Hopkins在大学校园建筑物的沉降中使用了QAP[7]，Elshafei在医院的布局规划中使用了QAP[8]，Bos在与森林公园分区相关的问题中使用了QAP[9]。从各种NP难问题的求解方法中可以看出，在QAP求解中，精确方法不能在合理的时间内找到最优或接近最优的结果，nn问题的大小增加。提供的精确解方法成本计算1/1第1页其中D是保持位置之间的距离的N × N维矩阵，F是保持设施之间的流成本的N × N维矩阵。其目的是寻找使代价函数最小的置换阵。*通讯作者。电子邮件地址：esonuc@karabuk.edu.tr（E.Sonuc），bsen@ybu.edu.tr（B.Sen），safakbayir@karabuk.edu.tr（S. Bayir）。由Karabuk大学负责进行同行审查文献研究中的QAP适用于数据集大小为n630的问题。因此，启发式和元启发式方法应用于QAP。模拟退火、禁忌搜索、遗传算法、蚁群算法、离散搜索、粒子群算法和模因算法可以给出的例子中使用的元启发式方法在解决QAP。与它们一起出现的还有杂交研究不同的超启发式方法被一起使用。根据对QAP的研究，目前应用最广泛的算法有模拟退火算法、禁忌搜索算法和蚁群算法。更详细的信息在关于QAP的调查中给出[10，11]。https://doi.org/10.1016/j.jestch.2018.08.0022215-0986/©2018 Karabuk University.出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表工程科学与技术国际期刊杂志主页：www.elsevier.com/locate/jestch不844E. 索努茨和 其他/工程 科学 技术，国际 期刊21（2018）843由于元启发式方法是计算昂贵的，并行算法必须设计。各种元启发式方法在CPU或GPU上并行化在对GPU的研究中，CUDA（计算统一设备架构）体系结构被用于不同的领域。CUDA是NVI-DIA公司开发的并行计算平台和编程模型它是在GPU硬件上开发的，具有高容量计算能力[12]。多起点技术允许开始解决问题的串行和并行研究中使用的不同的开始排列，目的是提高元启发式方法的效率。这些研究的总体目标是开发一种使用多启动技术的方法，以在合理的时间内获得高质量的结果。本文利用CUDA平台，将模拟退火算法它的目的是通过确保线程以不同的排列数组（多重开始）开始来获得最佳的更快结果。其目的是开发一种有效的方法，在该方法中，线程之间的块内和块间的通信都可以实现。在第2中考虑了基于GPU的QAP优化算法和元算法的相关工作;在第3中给出了有关开发方法的信息;在第4节中给出了方法在GPU上的实现;在第5中显示和解释了本研究中获得的结果;最后，第6陈述了一些结论和未来的工作。2. 相关工作Dokeroglu和Cosar[13]开发了一种名为Multistart超启发式算法的方法，该算法在CPU上并行运行，并将该方法应用于QAP。在他们的研究中，遗传算法在第一阶段在网格上运行，然后使用几种启发式机制来提高解的质量。他们通过强调多起点方法突出了结果的性能。根据他们的实验，当使用多启动机构时，平均偏差的改善为%27。Ferreiro等人[14]提出了一种基于模拟退火方法的CUDA并行算法。他们在研究中提出了异步并行和同步并行两种版本。通过对数学测试函数的实验表明，同步版本在精度和计算量方面具有更好的性能。Sonuc等人提出了一种求解0-1背包问题的并行模拟退火算法[15]和目标分配问题[16]。这两项研究都是在GPU上开发的，根据结果，对于0/1背包问题，加速比达到7倍到16倍，对于背包-目标分配问题，加速比达到92倍到250倍。筒井和藤本[17]在CUDA上应用蚁群算法和禁忌搜索算法，提出了一种称为移动成本调整线程分配的混合算法。在他们的研究中，加速被用来比较GPU和CPU。Paul[18]在GPU上使用CUDA提出了模拟退火的并行版本，并应用于QAP公式。在本研究中，仅在加速度方面进行比较。根据他们的实验，他们发现在加速方面比非并行版本好100倍。James等人。[19]提出了QAP的合作并行禁忌搜索（CPTS），并专注于平均百分比偏差。根据他们的实验，CPTS显示出达到或超过文献中许多方法的平均溶液质量。查皮恩斯基[20]提出了一项研究，使用CUDA上的并行多起点禁忌搜索（PMTS）方法进行QAP，并使用加速度和相对百分比偏差作为比较标准。根据他们的实验，PMTS的运行速度比单核CPUChaparala等人[21]使用并行算法求解QAP他们的解决方案提供了有效的加速，并在准确性方面给出了一个小的惩罚。Novoa等人。[22]开发了一种并行禁忌搜索算法来解决GPU上的QAP，并将结果与他们过去使用运行时间和间隙的研究进行了关于GPU上应用的QAP优化算法的调查可以在[23]中找到。3. 该方法在本节中，将介绍在GPU上实现模拟退火方法的相关阶段。序贯模拟退火方法在3.1节中有简短的介绍;该方法的并行实现在3.2节中给出并示意性描述。3.1. 序贯模拟退火模拟退火是由Kirkpatrick和Vecchi[24]在1983年开发的，目的是找到属于具有多个局部最小值或最大值点的问题的函数的全局最小值或最大值点。地位使用物理系统来解决方法问题。将固体物质熔化并加热至特定的加热温度。然后，进行缓慢冷却。在此退火过程中，目的是确保物质达到最佳形式，并顺利结晶。物质的能量表示问题的成本函数。Metropolis[25]标准用于接受或拒绝邻居解决方案。如果两个能量之间的差异被视为DE，则验收标准定义如下：P¼ex p.-DE2其中T是属于该方法的当前迭代的潜在温度，P是退火过程中每个相邻解的接受概率。通过冷却因子将温度降低到目标温度。当其达到目标温度时，停止该方法。除此之外，还可以使用模拟退火的迭代次数或时间相关终止方法。1984年Burkard和Rendl[26]与此同时，已经进行了各种研究，其中模拟退火方法用于解决QAP[27模拟退火算法的伪代码如下（见图1）。①的人。3.2. 并行多开始模拟退火算法在元启发式方法上使用多起点技术为解决组合问题提供了高质量的结果[30]。与元启发式方法一样，多起点技术也用于模拟退火算法[20，31]。此外，图2所示的多起点是并行算法的一种非常有效的技术，并且在文献[20]中常用。每个线程都以自己的序列开始解决问题，并在此过程中定期进行通信以共享结果。在共享结果之后，线程开始新的迭代，其中新的序列取自具有最佳质量结果的线程在PMSA中，GPU上的块中的线程首先与其块中的线程进行通信。CUDA平台中线程之间的同步机制仅发生在使用共享内存的同一块中的线程之间。根据E. Sonuc et al. / Engineering Science and Technology，an International Journal 21（2018）843-849845Fig. 1. 模拟退火算法对于该机制，可以确保在同一块中完成所有线程的操作。在PMSA方法中，每个迭代结果可以由块中具有最佳结果的线程确定。为了找到这个线程，使用了归约方法。这样的话，时间复杂度为O（logn），而不是O（n）。用最小成本（1）缩减方法得到的符号直观图如图所示. 3.第三章。在GPU上，每个块具有有限数量的线程。由于不存在与块间通信相关的机制，因此使用允许块间通信的方法。块间通信的基本方式是终止内核在GPU上的运行。在GPU激活后重新启动内核，以允许所有线程同步由于这种方法增加了CPU和GPU之间的数据交换，并且访问全局内存的速度太慢，因此在运行时方面效率不高因此，Xiao和Feng提交的方法允许不同块中的线程之间进行通信[32]。这个方法依赖于这样的原则，即glo- bal变量上的线程等待，直到获得目标值根据该方法，在块间等待期间用于实现死锁的块的数量受到流多处理器（SM）的数量的限制。在确定块中具有最佳质量结果的线程之后，使用所提出的方法通信的每个块中的这些线程和属于所有块中的最佳质量结果的这个置换数组通过一个全局变量与所有线程共享，下一次迭代以此序列开始在PMSA中，每个线程所采取的步骤如下：步骤（1）：在开始第一次迭代之前创建特定于线程的随机排列数组（多亏了这一点，方法实现）;图二. 并行多开始模拟退火。图三. 用约简法求最小值。步骤（2）：用创建的置换数组开始解题;步骤（3）：计算两个随机确定的数字的交换操作可能产生的成本差异（通过使用delta函数）;步骤⑷：如果delta函数值小于0或根据metropolis准则计算的概率值大于随机确定的数（0和1之间），则接受交换操作;P.BC公司简介东846号 索努茨和 其他/工程 科学 技术，国际 期刊21（2018）843步骤（5）、如果delta函数值小于0，则接受并保留作为交换操作的结果而创建的新置换数组;步骤（6）：重复步骤（3）-步骤（5），直至达到目标温度;步骤（7）：通过计算在多次迭代之后创建的成本函数值，在共享变量;步骤（8）：等待同一块中的其他线程完成步骤（7）;步骤（9）：提供与在块中的线程步骤（10）：将每个块中最佳线程的值分配给全局变量所需的参与。见图4。交换操作。线程以自己的起始序列串行运行模拟退火 交换操作（参见图 4）用于邻域搜索法。在 PMSA 中 构 造 块 内 通 信 时 ， 需 要 一 个 置 换 数 组（shared_permutation_array[]）与数据集的大小相等，该置换属于线程之间的最佳结果。此数组定义为步骤（11）：等待直到所有线程执行共享的操作。块中使用的线程数已确定直到步骤（10）;步骤（12）：参与在所有块中找到属于最优结果的线程所需的协作。等待，直到确定所有线程都完成了操作步骤（13）：将最优结果分配给最佳全局结果。 确保属于此结果的线程的置换数组 在下一次迭代中共享所有线程的点上，将其分配给全局变量。等待，直到确定操作由所有线程完成;步骤（14）：在进行下一次迭代之前，从全局变量中取出属于最优结果的置换数组，并从步骤（3）继续，直到完成确定的迭代次数。步骤（15）：终止操作，直到达到目标迭代次数。4. GPU上的实现在CUDA上实现该方法的阶段使用了共享内存，通过考虑数据集的大小来执行更快的计算与此同时，共享的数据库用于块内通信。此外，还需要每个线程特定的以下permutation[size_of_dataset]（迭代时的置换数组），best_cost（到那一刻为止找到的最佳值），temperature（模拟退火的温度参数），● delta_cost（属于QAP的delta值为了找到两个成本之间的差异，使用Burkard和Rendl提供的delta函数[26]。这个函数的复杂度为O（n）如果属于p数组的r和s索引中的交换成本被定义为D_p;r;s_p，则公式如下：Dp;r;sdrr.fpsps-fprpr德水库fpspr-fprps作为1024（GPU使用的上限）。变量定义为共享该方法的优点如下：shared_cost [number_of_threads_in_a_block]，（属于线程的成本thread_id_in_a_block [number_of_threads_in_a_block]（线程数），shared_permutation_array [size_of_dataset]（属于最佳排列的数组）。在 shared_cost[] 数 组 上 执 行 约 简 方 法 ， 并 且 在 操 作 结 束 时 在shared_cost[0]中获得最佳结果。每个线程在一个块上都有一个数字，这表 示 为 thread_id_in_a_block[] 。 在 计 算 之 后 ， 该 线 程 通 过shared_permuta- tion_array[]与所有线程共享其置换数组。内核中的所有线程都读取全局内存。全局变量用于执行块间通信的目的在线程获得块内最佳结果之后，该结果被分配给全局变量数组（global_cost[]）。分配的线程在在执行此操作时，其他线程使用用于块间通信的方法进行等待。获得最佳结果的线程将其自己的置换数组分配给全局数组，以便与其他线程共享其他线程在此过程中也会等待，并从相关数组中获取此排列，以便在下一次迭代中使用如图5所示，PMSA中有两种通信机制。在第一种方法中，每个线程独立地运行SA，使用共享内存与其块中的所有线程进行通信，以计算块的最小代价并共享最佳序列。在第二种方法中，块中的第一线程使用全局算法相互通信，此方法定义为全局的变量如下：global_cost[number_of_blocks]，（属于线程的成本值），● thread_id[number_of_blocks]（线程数德海峡fprps-fpsprds s。fprpr-fpspsglobal_permutation_array[dataset_size]（属于最佳排列的数组），● ain[number_of_blocks]（用于块间通信），n-10dkr.fpkps-fpkpr1Bdk s.fpkpr-fpkpsCð3Þ● aout[number_of_blocks]（用于块间通信）。5. 计算实验和结果k<$0;k-r;sBdrk.fpspk-fprpkCdskfprpk-fpspkPMSA在属于QAPLIB的132个基准数据集上进行了测试[33]I'm sorry. QAPLIB数据集分为两类，对称实例和非对称实例。本文中使用的数据集大小在10到100之间。●●●●●●●●1/4·%氯化钠E. Sonuc et al. / Engineering Science and Technology，an International Journal 21（2018）843-849847图五. PMSA的算法实验结果在Windows 8.1操作系统中使用NVIDIA Geforce GTXTitan X GPU（12 GB内存，24个多处理器）在Intel（R）Xeon（R）CPU E5-2630 v3@2.40 GHz 16核处理器上进行了测试。串行和并行程序均采用C++编程语言开发。众所周知，模拟退火算法的性能主要取决于属于该方法的参数。在此背景下，进行研究的目的是选择参数值。通过考虑数据集的大小来选择参数，确定了两种不同的参数配置。对于数据集在0和39之间变化的大 小 ， 参 数 值 确 定 为 TINITIAL= 1000 ， TFINAL= 0.1 ， Cooling_factor=0.999，对于大小在40和100之间变化的数据集，参数值确定为TINITIAL=10000，TFINAL= 0.1，Cooling_ factor= 0.99999。根据这两种参数配置，方法进行了评估与两个不同的迭代次数：1和5。在操作中线程之间没有执行任何协作一次迭代法（PMSA I）。在五次迭代的方法中，通过执行与PMSA（PMSA II）迭代次数相同的线程间通信来实现协作。由于第五次迭代之后的迭代对结果的质量贡献不足，因此最大迭代次数优选为五次。采用加速比准则来评价速度差在CPU和GPU上开发的方法与对称情况相比，非对称情况下的循环计算是对称情况下的2倍。加速比如下所述：CPU时间见图6。 属于不同大小数据集的加速图。对称或非对称实例。当评估PMSA I和PMSA II方法时，根据两种不同的迭代结果，加速值彼此接近。用于比较的相对偏差百分比（RPD）由以下公式定义：RPDcostp-costpω1005成本补偿加速时间GPUð4Þ其中，costp表示使用PMSA找到的结果，costpωðÞðÞ表示最佳已知解（BKS）。根据获得的结果，可以看出，在对称实例中，加速值高达13倍，在非对称实例中高达29倍（图6）。根据结果，加速比也随着数据集大小的增加而增加最高的加速值出现在大型数据集（n= 100）中，表1呈现了属于Sko*（非对称实例）数据集的结果。可以看出，运行时间随着迭代次数的增加而增加，并且获得了比Sko* 实例更好的结果PMSA不执行固定次数的迭代。因此，对于具有相同大小的数据集，运行时是不相等的848E. 索努茨和 其他/工程 科学 技术，国际 期刊21（2018）843PMSA获得了BKS 73的83个对称实例和40的49个非对称实例。在发现BKS的113个数据集中，有99个是在不到一分钟的运行时间内获得的。平均而言，PMSA I方法比BKS差0.09%，PMSA II方法比BKS差0.07%PMSA发现BKS即使是最大的在QAPLIB中，只有14个实例PMSA没有得到最佳解决Tai*a实例是PMSA面临的最棘手的问题。表2和表3显示了根据以下算法的PMSAII准确度和性能的比较2-opt[21]：2-opt算法的GPU实现以解决QAP。Tabu[22]：Tabu搜索算法的GPU实现，以解决QAP。表3Sko* 数据集的计算结果。PMTS[20]：GPU实现的多开始禁忌搜索算法-解决QAP问题的方法。表2显示，禁忌搜索[22]在14个实例中的7个实例中具有更好的准确性。PMSA在14个实例中的4个中具有更好的准确性。禁忌搜索[22]在14个实例中的5个中获得了BKS。PMSA在14例中的6例中获得了BKSTabu Search的运行时间PMSA的运行时间远小于禁忌搜索[22]，范围从0.0210.92分钟。PMSA的准确性不如Tabu Search[22]的原因之一可能是Tabu Search[22]的运行时间。可以说，Tabu Search[22]比PMSA执行更多的函数评估。如果增加PMSA的迭代次数，则可能获得更好的结果。表1Sko* 数据集的PMSA计算结果。数据集BKSPMSA IPMSA IIRPD（%）时间（s）RPD（%） 时间（秒）sko4215,8120.000 61.30.000306.445sko4923,3860.000 71.20.000357.529sko5634,4580.000 80.60.000406.167sko6448,498123.10.000618.002sko7266,2560.006 103.10.000516.289sko8190,998111.00.000555.844sko90115,5340.042 122.60.029613.545sko100a152,0020.022 136.70.000680.828sko100b153,890137.00.000680.073sko100c147,8620.008 136.00.003682.146sko100d149,5760.027 135.80.013682.638斯科100 e149,1500.020 135.40.009679.874sko100f149,0360.043 136.20.038682.042平均0.014 112.90.007573.956表2一些QAPLIB数据集的计算结果[22]第22话：我的世界RPD时间（秒）RPD时间（秒）RPD时间（秒）tai30a1.103.840.00107.621.150.76tai30b0.003.780.00107.560.000.76tai40a1.5511.830.07906.750.00179.16tai40b0.0211.680.00906.600.00167.13tai50a1.7829.400.39971.480.95210.60tai50b0.1529.170.05971.250.00187.89tai60a2.5062.150.643897.381.19254.15tai60b0.2361.190.063678.450.00240.80tai80a2.48202.110.8310607.201.52445.77tai80b0.52199.200.0914714.800.10484.84tai100a2.35501.650.7221773.401.57434.10tai100b0.89493.620.3916234.900.38413.06lipa70a0.77117.080.007214.000.00522.60Lipa90a0.64327.190.0020594.600.53654.90表3显示，PMT[20]在12个实例中的9个中获得了BKS。PMSA在12例中的7例中获得了BKS。PMTS[20]的运行时间范围从0.15到16.9分钟。PMSA的运行时间范围从5.1到11.3分钟。根据结果，PMTS和PMSA都是Sko* 实例的可用方法。6. 结论和今后的工作本文利用CUDA平台在GPU上开发了并行多开始模拟退火算法PMSA（Parallel Multitstart Simulated Annealing）来求解二次分配问题QAP（Quadratic Assignment Problem）。减少了CPU和GPU之间的数据交换，从而实现了线程之间的高效此外，还采用了多线程启动技术，使每个线程的启动顺序不同。该文件侧重于加速和质量的解决方案。根据结果，PMSA运行速度高达13倍（对称实例），比单核CPU快29倍（非对称实例）可以说，PMSA方法在短时间内获得了各种数据集中的最佳已知解或接近最佳已知解。在未来，PMSA可以使用不同的邻居搜索机制和不同的线程之间的通信机制进行改进PMSA不仅可以应用于优化问题，还可以应用于现实世界的问题，如各种光电架构[34]。可以使用SA算法的变体来代替纯SA算法。PMSA可以在多个GPU上进行测试，以观察该方法的收敛性如何变化。确认作者感谢各位专家的宝贵意见和建议。这项工作得到了Karabuk大学科学研究协调小组的支持，资助号为KBU-BAP-15/2-DR-027。引用[1] T.C. Koopmans ， M. Beckmann ， Assignment Problems and the Location ofEconomic Activities，Econometrica J. Econometric Soc. 1957，53-76。[2] L. Steinberg，背板布线问题：布局算法，SIAM Rev. 3（1961）37[3] A.M. Geoffrion，G.格雷夫斯，调度并行生产线与转换成本：二次分配/LP方法的实际应用，操作。Res. 24（1976）595-610。[4] M. Pollatschek，H.Gershoni，Y.李文，电脑模拟打字机键盘之最佳化，应用资讯（1976）438-439。[5] J. Krarup，P.M.P r u z a n ，Mathematical Programming in Use，Springer，1978。[6] M.J. Alberco，S. Stahl，使用二次分配方法生成对称邻近矩阵的最小二乘一维缩放的初始置换，J. Classif. 17（2000）197-223。●●●问题PMTS[20]PMSARPD时间（秒）RPD时间（秒）sko420.0009.000.000306.45sko490.00017.000.000357.53sko560.00042.000.000406.17sko640.00036.000.000618.00sko720.000170.000.000516.29sko810.000287.000.000555.84sko900.000381.000.029613.55sko100a0.000525.000.000680.83sko100b0.0001015.000.000680.07sko100c0.0011008.000.003682.15sko100d0.000742.000.013682.64斯科100 e0.004963.000.009679.87sko100f0.023669.000.038682.04E. Sonuc et al. / Engineering Science and Technology，an International Journal 21（2018）843-849849[7] J. Dickey，J. Hopkins，Campus building arrangement using TOPAZ，Transp. Res.6（1972）59-68。[8] A.N. Elshafei，医院布局作为二次分配问题，Oper。Res. Q. （1977）167-179.[9] J. Bos ， Zoning in Forest Management ： A Quadratic Assignment ProblemSolvedby Simulated Annealing，J. Environ.管理。37（1993）127-145。[10] E.M. Loiola，新墨西哥州de Abreu，P.O. Boaventura-Netto，P. Hahn，T. Querido，二次分配问题综述，Eur。J. Oper.第176（2007）号决议第657-690段。[11] 新罕布什尔Zaied，L.A.E.-F. Shawky，二次分配问题的调查，Int. J. Comput. 101（2014）。[12] NVIDIA，Programming Guide：CUDA Toolkit Documentation v7.5，2017.可用网址：http://docs.nvidia.com/cuda/cuda-c-programming-guide/[13] T. Dokeroglu，A.Cosar，一种新的网格上二次分配问题的多起点超启发式算法，Eng. Appl. Artif 内特尔 52（2016）10-25。[14] A. Ferreiro，J. García，J.G.洛佩斯-萨拉斯角Vázquez，一个高效的实现并行模拟退火算法在GPU中的应用，J. Global Optim. 57（2013）863-890。[15] E. 索 努 克 湾 Sen ， Bayir ， A parallel approach for solving 0/1 knapsackproblemusing simulated annealing algorithm on CUDA platform ， Int. J.Comput. Sci. 信息安全14（12）（2016）1096-1101。[16] E.索努克湾Sen，S.张文，一种求解多目标分配问题的并行模拟退火算法。Sci. 8（4）（2017）87-92。[17] S. Tsutsui，N.Fujimoto，ACO在GPU上使用禁忌搜索，使用移动成本调整线程分配解决QAP，在：第13届遗传和进化计算年会论文集，第13页。1547[18] G. Paul，A GPU implementation of the Simulated Annealing Heuristic forthe Quadratic Assignment Problem ， arXiv preprint arXiv ： 1208.2675 ，2012.[19] T. 詹姆斯角，澳-地Rego，F. Glover，二次分配问题的协同并行禁忌搜索算法，Eur。J. 操作员Res. 195（2009）810-826。[20] M.Czapin'ski，一种有效的并行多起点禁忌搜索算法在CUDA平台上的二次分配问题，J.并行分布。 Comput. 73（2013）1461-1468。[21] A.查帕拉拉角Novoa，A. Qasem，带GPU加速的二次分配问题的SIMD解决方案，2014年会议论文集极端科学和工程发现环境年会，pp。2014年1月[22] C. Novoa，A. Qasem，A. Chaparala，A SIMD tabu search implementation forsolving the quadratic assignment problem with GPU acceleration ， in ：Proceedings of the 2015 XSEDE Conference：Scientific Advancements Enabledby Enhanced Cyberinfrastructure，p. 13，2015.[23] O.阿卜杜勒卡勒湖Idoumghar，J. Lepagnot，应用于图形处理单元QAP的元分析方法的调查，并行处理。Lett. 26（03）（2016）1650013.[24] S. Kirkpatrick，MP陈文辉，模拟退火优化，科学220（1983）671-680。[25] N.大都会，A.W. Rosenbluth，M.N. Rosenbluth，A.H. Teller，E. Teller，用快速计算机计算状态方程，J. Chem. Phys. 21（1953）1087-1092。[26] R.E. Burkard，F. Rendl，组合优化问题的一种基于启发式的模拟方法，Eur。J. Oper.第17（1984）号决议第169-174段。[27] M.R.威廉，T.L.王文，以模拟退火法求解二次指派问题，国立成功大学硕士论文，1987。[28] T. Connolly，QAP的改进退火方案，Eur. J. Oper. Res. 46（1990）93-100。[29] A.张文，一种求解二次分配问题的元启发式算法，北京大学出版社，2001。内特尔15（2004）753-759。[30] R. Martí，M.G. Resistance，C.C. Ribeiro，组合优化的多起点方法，Eur。 J. 操作员Res. 226（2013）1-8。[31] J. -- C.王，二次分配问题的多起始模拟退火算法，在：生物启发计算和应用创新（IBICA），第三届国际会议，第10页。2012年19[32] S. 肖 文 C.Feng ， Inter-blockGPUcommunicationviafastbarriersynchronization ， Parallel Distributed Processing （ IPDPS ） ， 2010 IEEEInternational Symposium，pp. 2010年1[33] R.E. Burkard，S. Karisch，F.一个二次分配问题库，Eur。J. 操作员Res. 55（1991）115-119。[34] A. Al-Adwan，文学士Mauriszah，A.谢文龙，基于并行重复最近邻算法的OTIS-Hypercube和OTIS-Mesh 光电结构求解旅行商问题，J。超 级 计算机 74（1）（2018）1-36。
我的内容管理
展开
