英语原文共 29 页

二次分配问题元启发式的比较研究

5.1 引文

二次分配问题（QAP）被称为NP-hard组合问题，没有一个启发式算法能够在最短时间内解决其大维问题。通过二/三次有效启发式的杂交，找到了一种较好的求解方法，以获得最优或近似最优解。QAP问题可以根据工业概念分解为多种类别，例如，单元制造、设施布局、机器布局、印刷电路板和机场门分配问题都是QAP的类别，此外，流水作业问题也可以视为QAP。因此，QAP的性质是多样的，它主要存在于现实生活中的问题中，特别是在生产设施中。有大量文献报道了QAP的不同类别，由于它是NP-hard问题，研究者和实践者仍在寻找更好的方法来解决这类问题。已经有许多有效的方法被用于解决QAP问题，特别是ACO、PSO、TS和SA被反复混合以解决QAP的大型问题。在前面的章节中，我们已经展示了所提出的TBO如何处理一些实际的工程问题，因此，在本章中，TBO也同样应用于QAP。利用TBO所得到的结果与文献中其他方法的结果相比起来更好。

5.2. QAP公式

基于二次分配问题的概念，可以进行设施布局问题的求解。设施布局的主要目标是找到一种工作的分配，使分配和操作的总成本最小化。为了有效地降低总成本，设施布局的制定必须考虑所有的方面，如材料流动、距离和数量。因此，一个设施布局问题可以用一个ntimes;n矩阵的矩阵来建模。让我们把a_i,j看作是从位置（i）到（j）的流量，让b_i,k是从位置（i）到位置（k）的距离，c_j,l是从位置（j）到位置（l）的成本。QAP由包括分配的所有方面的Koopmans-Beckmann相关性处理，其数学表示如下：

(5.1)

式中，Rn是整数1,2，hellip;，n的排列，每个项a_i,j b_{psi;（i）psi;（k}）是从位置psi;_i设施i到到位置psi;（k）处设施k的分配成本，ci _psi;（i）是在位置psi;（i）处建立设施i的总成本加上安装在psi;（1）、psi;（2）、hellip;，psi;（n）处的其他设施j的分配成本，整数i、j、k、l的长度为1，2，hellip;，n。

5.3. 建立实验

在本节中，对设施布局进行了实验，这些布局属于二次分配问题，可在http://anjos.mgi.polymtl.ca/qaplib/inst.html（QAPLIB）中找到。QAPLIB中的例子表示随机生成的或来自现实制造系统的设施布局类型。在本实验中，我们结合PSO、ABC、BBO和ACO算法，研究了该方法在ESCxx、Nugxx、Chrxx和Hadxx实例中的性能。在这些例子中，ESCxx被归为印刷电路问题，它是为计算机科学而产生的。nugxx问题通常用于二次分配问题，此外chrxx和hadxx也被认为是QAP的简单实例。PSO、ACO、ABC和BBO的计算代码取自http://yarpiz.com/。然而，所有方法的调谐参数都在表5.1中报告，其中，根据[43]考虑PSO参数，对于ACO、ABC和BBO分别参考[39]和[116]、[117]。因此，这些代码在Matlab2016a中运行，并在Dell XPS、Windows 8、Core Duo处理器和4 RAM中执行。每个单独问题的运行次数执行10次，每个运行在1000次迭代中执行。为了进行比较，该方法与其他算法一起运行，因此统计结果将显示在下一段中。APD由（）确定，Z是10次运行中获得的平均百分比偏差，是最著名的解决方案。

表5.1：ABC、ACO、PSO、BBO和TBO的调整参数，其中I和E分别是转移率和转移率。c1，c2是认知因素。

5.4.结果与讨论

首先，QAPLIB中对上述例子应用了TBO，所得统计结果见表5.2和表5.3。在印刷电路板实例（ESCxx）中，TBO发现12个最佳解，7个解得到近似最佳解，如表5.2所示。从统计结果可以看出，TBO作为大多数问题的标准差是稳定的。同时，在其成功性方面，它能够在7个ESCxx实例上显示，在表5.2中的13个问题中100%成功。在hadxx实例上，tbo得到的结果与5个实例的结果是相同的，在10次运行中重复（3）次得到2个最优值。然而，其余三个实例的求解接近最优，与表5.2中描述的最著名解（BKS）的偏差为（0.01-0.05）。在表5.3中，报告了nugxx和chrxx实例的结果，这些实例是为研究人员在测试其算法时经常使用的设施布局问题而设计的。nugxx实例的结果并没有达到最佳值，只有一个实例nug12的解为最广为接受的解，而其余的nug14-nug30则接近于最佳值，如表5.3所示。这些结果证实了寻找组合问题最优解的难度，正如文献中所指出的那样，大多数最优解是通过杂交技术得到的。此外，对于nugxx，也可以使用tbo一起求解chrxx实例，其结果在表5.3中集中描述，在chrxx实例中，只有chr12b实例获得最优解，但其余的都接近于表5.3中所示的近似最优解。

表5.2:TBO从QAPLIB获得的印刷电路板问题（ESCxx）和HADXx实例的结果。delta;是从已知解（bks）中得到的TBO值的百分比偏差。计算时间以秒为单位。括号中的值是每个问题成功运行的次数，n是问题的维数。

表5.3:TBO从QAPLIB获得的nugxx实例结果。delta;（%）是TBO值与已知最佳溶液（BKS）的百分比偏差。计算时间以秒为单位，n是问题的维数。

表5.4:TBO在CHRXX上获得的结果。来自QAPLIB的实例。delta;（%）是TBO值与已知最佳溶液（BKS）的百分比偏差。计算时间以秒为单位，n是问题的维数。

5.4.1.统计数据分析

在本节中，讨论了比较分析，分析了各种元启发式算法得到的结果，并得出了结论。在表5.4和5.5中，对前面讨论的所有设施布局实例给出了PSO、ABC、ACO、BBO和TBO的比较结果。因此，表5.4给出了在ESCxx实例上，tbo与pso、aco、abc、bbo之间的最佳解与已知解的百分比偏差的比较结果，可以看出，在各种优化器获得的最佳解的水平上，abc、pso和tbo比aco和bbo具有竞争力，因为它们在19个实例中得到了13个最优解。同时，BBO和ACO在19个ESCxx实例中分别得到了11个和9个最优解。在成功率方面，ABC从ESCxx实例的其他优化器中排名第一，因为它在所有10次运行中都获得了10个最优解，而TBO排名第二，它在ESCxx实例的所有10次运行中都成功获得了7个最优解。而ACO、PSO和BBO则在排在第三、第四和最后，因为它们在10次运行中相应地获得了5、4和3个最优解。一般来说，与ESCxx实例相比，优化器在解决这些问题方面显示出了它们的有效性，如表5.4所示，尽管它们的性能略有不同。在其他情况下，即nugxx、chrxx和hadxx，表5.5显示了与已知解的百分比偏差的比较结果。可以看出，tbo得到了4个最优解，abc得到了3个，而pso和bbo都达到了2个最优解。因此，优化法tbo、abc、pso、bbo和aco可根据其与最知名解决方案的最佳百分比偏差（如表5.5所示）排名为1、2、3、4和5。此外，关于nugxx实例，表5.6中报告了与最著名解决方案的平均百分比偏差（apd%）的结果。如表5.6所示，与PSO、ACO、ABC和BBO相比，表底部给出了平均百分比偏差总数，其中TBO能够获得11个百分比偏差，而PSO、ACO、ABC和BBO的总和分别为0、0、1和3。

表5.5：各种优化器对QAPLIB印刷电路板问题的结果。括号中的值是对单个问题成功运行的次数，n是问题的维数。每个算法中的值（delta;）是与文献中已知解（BKS）的偏差。粗体值是通过单个算法获得的最佳结果。

表5.6:nugxx上各种算法与已知解（BKS）的偏差百分比比较，来自QAPLIB的实例。括号中的值是成功获得最佳值的个数。粗体值是单个算法与BKS的最佳偏差结果。

表5.7:chrxx.和QAPLIB的Hadxx实例的各种算法与已知解（BKS）的偏差百分比比较。括号中的值是成功获得最佳值的个数。粗体值是单个算法与BKS的最佳偏差结果。在表的底部，通过各种方法的比较，给出了总的最佳偏差解。

表5.8：在nugxx实例上比较TBO获得的APD和其他状态的arts算法获得的APD。每一列都表示来自单个方法的最著名解决方案的APD。表的底部显示了APD的总数。加粗的脸意味着在比较水平上最好的APD。

5.4.2. 计算时间

计算时间定义为在元启发式的一次运行中完成的函数计算的持续时间，或者可以定义为算法以打印出的结果结束的时间。因此，这里显示了在运行元启发式解决问题时记录的计算时间。在所有设施布局问题中，所有问题的平均完成时间如表5.9所示，这些时间在一个问题的算法单次运行的1000次迭代中记录。从表中可以看出，与分别为44.1、44.48、59和286.93的PSO、ABC、BBO和ACO相比，TBO完成所有设施布局实例的计算时间较少（38.46）。一般来说，一个算法的计算时间受函数评估的影响，就像基于群体的元启发式一样，大量的群体增加了探索范式，这可以导致算法的有效收敛，尽管时间是折中的。如表5.9所示，与其他算法相比，ACO的计算时间很长，因为蚂蚁的数量设置大于ABC、BBO和TBO的数量，以便快速收敛，但是，与其他方法相比，蚁群算法中涉及的开发技术并没有克服这些方法。其他方法的平均计算时间彼此接近。

表5.9：完成设施布局问题所有实例模拟的所有方法的平均计算时间记录。每列表示完成所有各自实例的算法的平均完成时间。在表的底部指定了算法的总平均时间。

5.4.3. 收敛性分析

在进化计算的背景下，收敛性定义为优化程序为达到优化问题的全局最优/局部最优而消耗的迭代次数。因此，当优化器的搜索技术在勘探和开发模式中达到平衡时，优化方法就实现了良好的收敛性。然而，组合问题的收敛性一直被视为一个值得关注的问题，因为它呈指数增长，特别是在大型NP-hard问题中，如QAP中。因此，如图5.1-5.8所示，分析了优化方法（即TBO和ABC、ACO、BBO、PSO）的收敛性。在这些收敛图中，有四个关于印刷电路板问题的图，称为ESCxx，其中两个图（分别是ESC32E和ESC32G，图5.1和5.2）快速收敛到全局最优，而另两个图（分别是ESC32D和ESC32H，图5.3和5.4）则因算法没有实现而受到优化方法的挑战。没有收敛到问题的全局最优。

图5.5-5.8描述了四个chrxx实例上所有优化方法的收敛性，在这些问题中，所有方法都没有收敛到全局最优。然而，这些算法能够达到接近最优解。在图5.5中，CHR18A描述了收敛性，其全局最优值为11098。可以看出，TBO的收敛速度比其他最先进的算法要快，不过，其他四种方法之间有细微的差别。在图5.6中可以注意到，PSO的收敛速度略快于TBO和其他方法。同时，在图5.7中，TBO比其他优化方法显示出更好的收敛性。最后，在图5.8中，TBO的收敛性略好于PSO和PSO，远好于ABC和ACO。然而，将这些组合问题收敛到全局最优对所有优化方法来说都是一个挑战，尽管优化方法与另一优化方法之间的差别很小。因此，在两个/三个优化方法之间进行杂交可以更好地收敛这些组合问题。

图5.1.PSO、ABC、BBO、ACO和TBO在印制板电路问题（ESC32E）上的收敛性。该问题的全局最优解为2。

图5.2.PSO、ABC、BBO、ACO和TBO在印制板电路问题（ESC32G）上的收敛性。问题的全局最优值是6。

图5.3.PSO、ABC、BBO、ACO和TBO在印制板电路问题（ESC32D）上的收敛性。该问题的全局最优点的位置用适合值为200的箭头表示。

图5.4.PSO、ABC、BBO、ACO和TBO在印制板电路问题（ESC32H）上的收敛速度。该问题的全局最优位置用438适应度值的箭头表示。

图5.5.CHR18A上PSO、ABC、BBO、ACO和TBO的收敛速度，问题的全局最优位置用11098适应值的箭头表示。

图5.6.chr20a上的PSO、ABC、BBO、ACO和TBO的收敛速度，问题的全局最优位置用适合度为2192的箭头表示。

图5.7.chr22a上的PSO、ABC、BBO、ACO和TBO的收敛速度，问题的全局最优位置用适合值为6156的箭头表示。

图5.8.chr25上的PSO、ABC、BBO、ACO和TBO的收敛速度。该问题的全局最优位置由3796适应度值的箭头表示。

5.5.总结

本章对TBO算法与文献中其他最先进算法的QAP问题进行了比较研究。所有优化方法的性能都是根据每个算法得到的统计结果来衡量的，因此，对所有算法的统计结果、计算时间和收敛速度进行了深入的分析。首先，将TBO应用于解决QAPLIB中的escxx、hadxx、chrxx和nugxx实例。在ESCxx实例上，TBO能够在19个问题中找到12个全局最优值，也能从HADX实例中找到

资料编号：[4017]