資源描述：
《基于蟻群算法的并行最小斯坦納樹(shù)算法的研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、碩士學(xué)位論文基于蟻群算法的并行最小斯坦納樹(shù)算法的研究RESEARCHONPARALLELMINIMUMSTEINERTREEALGORITHMBASEDONANTCOLONYALGORITHM賈經(jīng)緯哈爾濱工業(yè)大學(xué)2018年6月國(guó)內(nèi)圖書(shū)分類號(hào)：TN47學(xué)校代碼：10213國(guó)際圖書(shū)分類號(hào)：621.3密級(jí)：公開(kāi)工程碩士學(xué)位論文基于蟻群算法的并行最小斯坦納樹(shù)算法的研究碩士研究生：賈經(jīng)緯導(dǎo)師：王非副教授申請(qǐng)學(xué)位：工程碩士學(xué)科：集成電路工程所在單位：深圳研究生院答辯日期：2018年6月授予學(xué)位單位：哈爾濱工業(yè)大學(xué)ClassifiedIndex:TN47U.D.C:621.3Disser
2、tationfortheMasterDegreeinEngineeringRESEARCHONPARALLELMINIMUMSTEINERTREEALGORITHMBASEDONANTCOLONYALGORITHMCandidate：JiaJingweiSupervisor：AssociateProf.WangFeiAcademicDegreeAppliedfor：MasterofEngineeringSpeciality：IntegratedCircuitEngineeringAffiliation：ShenzhenGraduateSchoolDateofDefence：
3、June,2018Degree-Conferring-Institution：HarbinInstituteofTechnology哈爾濱工業(yè)大學(xué)工程碩士學(xué)位論文摘要最小斯坦納樹(shù)問(wèn)題是圖論中經(jīng)典的NP-hard問(wèn)題，它是諸多領(lǐng)域的基本問(wèn)題之一。如組播路由問(wèn)題在很多的研究中都被構(gòu)建為最小代價(jià)組播樹(shù)問(wèn)題，即為最小斯坦納樹(shù)問(wèn)題；超大規(guī)模集成電路的布線問(wèn)題實(shí)質(zhì)上也是最小斯坦納樹(shù)問(wèn)題，等等。因此，對(duì)最小斯坦納樹(shù)問(wèn)題的研究求解就顯得尤為重要。對(duì)于NP-hard問(wèn)題，解決問(wèn)題所需的復(fù)雜度隨著問(wèn)題規(guī)模地增大而呈指數(shù)增長(zhǎng)，人們無(wú)法保證在多項(xiàng)式時(shí)間內(nèi)獲得問(wèn)題的精確解，而近似算法是在相對(duì)較低的計(jì)
4、算成本下獲得近似最優(yōu)解的可行方式。蟻群算法是一種仿生學(xué)優(yōu)化算法，其魯棒性較強(qiáng)，具有隱含的并行搜索能力。國(guó)內(nèi)外學(xué)者對(duì)于蟻群算法在最小斯坦納樹(shù)問(wèn)題上的應(yīng)用已經(jīng)做了一定的研究，但是傳統(tǒng)上的串行蟻群算法在速度上已經(jīng)無(wú)法適應(yīng)求解規(guī)模日益增大的斯坦納樹(shù)問(wèn)題。因此，在蟻群算法基本原理已經(jīng)明確的條件下，利用并行的平臺(tái)和算法解決斯坦納樹(shù)問(wèn)題是一個(gè)有潛力的研究方向。本文提出了一種蟻群優(yōu)化算法來(lái)求解最小斯坦納樹(shù)，并利用局部搜索來(lái)優(yōu)化求解結(jié)果。然后通過(guò)分析算法的特性，利用Gunrock圖處理庫(kù)對(duì)算法進(jìn)行了并行化處理。蟻群算法的相關(guān)參數(shù)對(duì)算法的性能有很重要的影響，因此在對(duì)算法的測(cè)試中，本文首先通過(guò)對(duì)
5、參數(shù)的粗調(diào)和微調(diào)分析了參數(shù)對(duì)于算法結(jié)果的影響，并給出了最優(yōu)的參數(shù)組合。在最優(yōu)參數(shù)組合下，對(duì)SteinLib中用例的測(cè)試中，所有測(cè)試用例的平均解的平均誤差率為1.09%，最優(yōu)解的平均誤差率為0.43%。對(duì)所有的測(cè)試結(jié)果，大部分結(jié)果的誤差率都在2%以下，所有測(cè)試用例的結(jié)果誤差率都在3.5%以內(nèi)。通過(guò)與其它的蟻群算法相比較，本文提出的算法的求解質(zhì)量要優(yōu)于其它的蟻群算法，并且在保證近似率的情況下，本文的并行算法的求解速度比對(duì)應(yīng)的串行算法平均快了1個(gè)數(shù)量級(jí)。通過(guò)與KMB算法相比較，本文提出的并行算法的求解質(zhì)量比KMB算法平均提高了8%，在運(yùn)行時(shí)間上比KMB算法平均快了2倍左右。關(guān)鍵詞
6、：最小斯坦納樹(shù)；蟻群優(yōu)化算法；局部搜索；圖形處理器；超大規(guī)模集成電路-I-哈爾濱工業(yè)大學(xué)工程碩士學(xué)位論文AbstractTheminimalsteinertreeproblemisaclassicalNP-hardproblemingraphtheory,anditisoneofthebasicproblemsinmanyfields.Forexample,themulticastroutingproblemhasbeenconstructedastheleast-costmulticasttreeprobleminmanystudies,namely,theminimum
7、steinertreeproblem;theverylargescaleintegrationwiringproblemisessentiallytheminimumsteinertreeproblemandsoon.Therefore,thestudyoftheminimumsteinertreeproblemisparticularlyimportant.FortheNP-hardproblem,thecomplexityrequiredtosolvetheproblemincreasesexponential
