基于蚁群算法的并行最小斯坦纳树算法的研究

发布时间：2020-08-05 11:57

【摘要】：最小斯坦纳树问题是图论中经典的NP-hard问题,它是诸多领域的基本问题之一。如组播路由问题在很多的研究中都被构建为最小代价组播树问题,即为最小斯坦纳树问题;超大规模集成电路的布线问题实质上也是最小斯坦纳树问题,等等。因此,对最小斯坦纳树问题的研究求解就显得尤为重要。对于NP-hard问题,解决问题所需的复杂度随着问题规模地增大而呈指数增长,人们无法保证在多项式时间内获得问题的精确解,而近似算法是在相对较低的计算成本下获得近似最优解的可行方式。蚁群算法是一种仿生学优化算法,其鲁棒性较强,具有隐含的并行搜索能力。国内外学者对于蚁群算法在最小斯坦纳树问题上的应用已经做了一定的研究,但是传统上的串行蚁群算法在速度上已经无法适应求解规模日益增大的斯坦纳树问题。因此,在蚁群算法基本原理已经明确的条件下,利用并行的平台和算法解决斯坦纳树问题是一个有潜力的研究方向。本文提出了一种蚁群优化算法来求解最小斯坦纳树,并利用局部搜索来优化求解结果。然后通过分析算法的特性,利用Gunrock图处理库对算法进行了并行化处理。蚁群算法的相关参数对算法的性能有很重要的影响,因此在对算法的测试中,本文首先通过对参数的粗调和微调分析了参数对于算法结果的影响,并给出了最优的参数组合。在最优参数组合下,对Stein Lib中用例的测试中,所有测试用例的平均解的平均误差率为1.09%,最优解的平均误差率为0.43%。对所有的测试结果,大部分结果的误差率都在2%以下,所有测试用例的结果误差率都在3.5%以内。通过与其它的蚁群算法相比较,本文提出的算法的求解质量要优于其它的蚁群算法,并且在保证近似率的情况下,本文的并行算法的求解速度比对应的串行算法平均快了1个数量级。通过与KMB算法相比较,本文提出的并行算法的求解质量比KMB算法平均提高了8%,在运行时间上比KMB算法平均快了2倍左右。
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP18;O157.5
【图文】：

实例图,网格图,实例

图 4-2 网格图模型似最小斯坦纳树算法应用于 VLSI 的多测试用例中给出了真实的 VLSI 多端线图中的一部分，图中大的方形结点是需道的交叉结点，空白区域为不可走线的来的多端线网布线问题可以定义为斯坦树上的连接线的总长最短，即是寻找图纳树问题不同的是，多端线网布线是直个方向，每个节点的度数最大为 4。

拓扑图,信息素,测试用例,相对重要性

发函数因子等这些取值范围较大的参数，即参数的粗调；然后，我们根据上一步的参数设置再调整先验知识参数0q 和衰减系数等取值范围小的参数，即参数的微调。通过实验结果，我们可以反复的调整参数的大小，以达到最优的组合效果。在这里，我们采用 D 类拓扑图进行仿真实验。对于每一个不同的参数取值，仿真实验都测试了 D 类拓扑图中的 20 个测试用例。在测试结果中，平均误差率和平均迭代次数分别为 20 个测试用例的误差率总和以及迭代次数总和的平均值。为了避免不必要的误差，单个测试用例的结果都做了 5 次测试，然后取平均值。通过测试结果，我们可以得出每个参数的不同取值对算法结果以及收敛性的影响，进而设置最优的参数组合。4.4.2 信息素启发因子和期望启发因子的影响信息素启发因子反映了蚂蚁运动过程中累积的信息素的相对重要性（即，信息素残留ij ），期望启发式因子反映了启发信息在蚂蚁运动过程中的相对重要性（即期望值ij ）。

信息素,衰减因子,取值

大小是两者相对而言的，因此，我们将参数的值恒定为 1，即 1，通过只改变的取值来研究参数对算法的影响。同样的，为了保证测试的有效性，在改变一个参数取值的情况下，其他参数的值不变。从图 4-4 中我们可以看出，算法的收敛速度和求解质量受到期望启发式因子参数的取值大小的影响非常大。随着的不断增大，算法能够更加快速的收敛到最优解。在本文的测试中，当 10时，蚁群算法的综合性能较好，此时信息素启发因子参数的值为 1。因此，我们只有正确的选择和的取值，才能加快算法地收敛，并且避免算法陷入局部最优的情况。4.4.3 信息素衰减因子的影响的取值大小决定了路径上信息素值衰减的速度。当取值过小时，信息素值会过快地挥发，对后续蚂蚁的行动失去了吸引力，算法的随机性和全局搜索能力虽然得到了增强，但是算法的收敛速度降低了；反之，当的取值过大时，路径上信息素迅速的积累，使得蚂蚁更倾向于搜索走过的路径，算法的收敛速度加快，但是会影响到算法的随机性和全局搜索能力。

【参考文献】