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

《基于蚁群算法的并行最小斯坦纳树算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文基于蚁群算法的并行最小斯坦纳树算法的研究RESEARCHONPARALLELMINIMUMSTEINERTREEALGORITHMBASEDONANTCOLONYALGORITHM贾经纬哈尔滨工业大学2018年6月国内图书分类号：TN47学校代码：10213国际图书分类号：621.3密级：公开工程硕士学位论文基于蚁群算法的并行最小斯坦纳树算法的研究硕士研究生：贾经纬导师：王非副教授申请学位：工程硕士学科：集成电路工程所在单位：深圳研究生院答辩日期：2018年6月授予学位单位：哈尔滨工业大学ClassifiedIndex:TN47U.D.C:621.3Disser

2、tationfortheMasterDegreeinEngineeringRESEARCHONPARALLELMINIMUMSTEINERTREEALGORITHMBASEDONANTCOLONYALGORITHMCandidate：JiaJingweiSupervisor：AssociateProf.WangFeiAcademicDegreeAppliedfor：MasterofEngineeringSpeciality：IntegratedCircuitEngineeringAffiliation：ShenzhenGraduateSchoolDateofDefence：

3、June,2018Degree-Conferring-Institution：HarbinInstituteofTechnology哈尔滨工业大学工程硕士学位论文摘要最小斯坦纳树问题是图论中经典的NP-hard问题，它是诸多领域的基本问题之一。如组播路由问题在很多的研究中都被构建为最小代价组播树问题，即为最小斯坦纳树问题；超大规模集成电路的布线问题实质上也是最小斯坦纳树问题，等等。因此，对最小斯坦纳树问题的研究求解就显得尤为重要。对于NP-hard问题，解决问题所需的复杂度随着问题规模地增大而呈指数增长，人们无法保证在多项式时间内获得问题的精确解，而近似算法是在相对较低的计

4、算成本下获得近似最优解的可行方式。蚁群算法是一种仿生学优化算法，其鲁棒性较强，具有隐含的并行搜索能力。国内外学者对于蚁群算法在最小斯坦纳树问题上的应用已经做了一定的研究，但是传统上的串行蚁群算法在速度上已经无法适应求解规模日益增大的斯坦纳树问题。因此，在蚁群算法基本原理已经明确的条件下，利用并行的平台和算法解决斯坦纳树问题是一个有潜力的研究方向。本文提出了一种蚁群优化算法来求解最小斯坦纳树，并利用局部搜索来优化求解结果。然后通过分析算法的特性，利用Gunrock图处理库对算法进行了并行化处理。蚁群算法的相关参数对算法的性能有很重要的影响，因此在对算法的测试中，本文首先通过对

5、参数的粗调和微调分析了参数对于算法结果的影响，并给出了最优的参数组合。在最优参数组合下，对SteinLib中用例的测试中，所有测试用例的平均解的平均误差率为1.09%，最优解的平均误差率为0.43%。对所有的测试结果，大部分结果的误差率都在2%以下，所有测试用例的结果误差率都在3.5%以内。通过与其它的蚁群算法相比较，本文提出的算法的求解质量要优于其它的蚁群算法，并且在保证近似率的情况下，本文的并行算法的求解速度比对应的串行算法平均快了1个数量级。通过与KMB算法相比较，本文提出的并行算法的求解质量比KMB算法平均提高了8%，在运行时间上比KMB算法平均快了2倍左右。关键词

6、：最小斯坦纳树；蚁群优化算法；局部搜索；图形处理器；超大规模集成电路-I-哈尔滨工业大学工程硕士学位论文AbstractTheminimalsteinertreeproblemisaclassicalNP-hardproblemingraphtheory,anditisoneofthebasicproblemsinmanyfields.Forexample,themulticastroutingproblemhasbeenconstructedastheleast-costmulticasttreeprobleminmanystudies,namely,theminimum

7、steinertreeproblem;theverylargescaleintegrationwiringproblemisessentiallytheminimumsteinertreeproblemandsoon.Therefore,thestudyoftheminimumsteinertreeproblemisparticularlyimportant.FortheNP-hardproblem,thecomplexityrequiredtosolvetheproblemincreasesexponential