【摘要】：最小斯坦納樹問題是圖論中經(jīng)典的NP-hard問題,它是諸多領(lǐng)域的基本問題之一。如組播路由問題在很多的研究中都被構(gòu)建為最小代價(jià)組播樹問題,即為最小斯坦納樹問題;超大規(guī)模集成電路的布線問題實(shí)質(zhì)上也是最小斯坦納樹問題,等等。因此,對最小斯坦納樹問題的研究求解就顯得尤為重要。對于NP-hard問題,解決問題所需的復(fù)雜度隨著問題規(guī)模地增大而呈指數(shù)增長,人們無法保證在多項(xiàng)式時(shí)間內(nèi)獲得問題的精確解,而近似算法是在相對較低的計(jì)算成本下獲得近似最優(yōu)解的可行方式。蟻群算法是一種仿生學(xué)優(yōu)化算法,其魯棒性較強(qiáng),具有隱含的并行搜索能力。國內(nèi)外學(xué)者對于蟻群算法在最小斯坦納樹問題上的應(yīng)用已經(jīng)做了一定的研究,但是傳統(tǒng)上的串行蟻群算法在速度上已經(jīng)無法適應(yīng)求解規(guī)模日益增大的斯坦納樹問題。因此,在蟻群算法基本原理已經(jīng)明確的條件下,利用并行的平臺和算法解決斯坦納樹問題是一個有潛力的研究方向。本文提出了一種蟻群優(yōu)化算法來求解最小斯坦納樹,并利用局部搜索來優(yōu)化求解結(jié)果。然后通過分析算法的特性,利用Gunrock圖處理庫對算法進(jìn)行了并行化處理。蟻群算法的相關(guān)參數(shù)對算法的性能有很重要的影響,因此在對算法的測試中,本文首先通過對參數(shù)的粗調(diào)和微調(diào)分析了參數(shù)對于算法結(jié)果的影響,并給出了最優(yōu)的參數(shù)組合。在最優(yōu)參數(shù)組合下,對Stein Lib中用例的測試中,所有測試用例的平均解的平均誤差率為1.09%,最優(yōu)解的平均誤差率為0.43%。對所有的測試結(jié)果,大部分結(jié)果的誤差率都在2%以下,所有測試用例的結(jié)果誤差率都在3.5%以內(nèi)。通過與其它的蟻群算法相比較,本文提出的算法的求解質(zhì)量要優(yōu)于其它的蟻群算法,并且在保證近似率的情況下,本文的并行算法的求解速度比對應(yīng)的串行算法平均快了1個數(shù)量級。通過與KMB算法相比較,本文提出的并行算法的求解質(zhì)量比KMB算法平均提高了8%,在運(yùn)行時(shí)間上比KMB算法平均快了2倍左右。
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：TP18;O157.5
【圖文】：

圖 4-2 網(wǎng)格圖模型似最小斯坦納樹算法應(yīng)用于 VLSI 的多測試用例中給出了真實(shí)的 VLSI 多端線圖中的一部分，圖中大的方形結(jié)點(diǎn)是需道的交叉結(jié)點(diǎn)，空白區(qū)域?yàn)椴豢勺呔�的來的多端線網(wǎng)布線問題可以定義為斯坦樹上的連接線的總長最短，即是尋找圖納樹問題不同的是，多端線網(wǎng)布線是直個方向，每個節(jié)點(diǎn)的度數(shù)最大為 4。

發(fā)函數(shù)因子 等這些取值范圍較大的參數(shù)，即參數(shù)的粗調(diào)；然后，我們根據(jù)上一步的參數(shù)設(shè)置再調(diào)整先驗(yàn)知識參數(shù)0q 和衰減系數(shù) 等取值范圍小的參數(shù)，即參數(shù)的微調(diào)。通過實(shí)驗(yàn)結(jié)果，我們可以反復(fù)的調(diào)整參數(shù)的大小，以達(dá)到最優(yōu)的組合效果。在這里，我們采用 D 類拓?fù)鋱D進(jìn)行仿真實(shí)驗(yàn)。對于每一個不同的參數(shù)取值，仿真實(shí)驗(yàn)都測試了 D 類拓?fù)鋱D中的 20 個測試用例。在測試結(jié)果中，平均誤差率和平均迭代次數(shù)分別為 20 個測試用例的誤差率總和以及迭代次數(shù)總和的平均值。為了避免不必要的誤差，單個測試用例的結(jié)果都做了 5 次測試，然后取平均值。通過測試結(jié)果，我們可以得出每個參數(shù)的不同取值對算法結(jié)果以及收斂性的影響，進(jìn)而設(shè)置最優(yōu)的參數(shù)組合。4.4.2 信息素啟發(fā)因子和期望啟發(fā)因子的影響信息素啟發(fā)因子 反映了螞蟻運(yùn)動過程中累積的信息素的相對重要性（即，信息素殘留ij ），期望啟發(fā)式因子 反映了啟發(fā)信息在螞蟻運(yùn)動過程中的相對重要性（即期望值ij ）。

大小是兩者相對而言的，因此，我們將參數(shù) 的值恒定為 1，即 1，通過只改變 的取值來研究參數(shù)對算法的影響。同樣的，為了保證測試的有效性，在改變一個參數(shù)取值的情況下，其他參數(shù)的值不變。從圖 4-4 中我們可以看出，算法的收斂速度和求解質(zhì)量受到期望啟發(fā)式因子參數(shù) 的取值大小的影響非常大。隨著 的不斷增大，算法能夠更加快速的收斂到最優(yōu)解。在本文的測試中，當(dāng) 10時(shí)，蟻群算法的綜合性能較好，此時(shí)信息素啟發(fā)因子參數(shù) 的值為 1。因此，我們只有正確的選擇 和 的取值，才能加快算法地收斂，并且避免算法陷入局部最優(yōu)的情況。4.4.3 信息素衰減因子的影響 的取值大小決定了路徑上信息素值衰減的速度。當(dāng)取值過小時(shí)，信息素值會過快地?fù)]發(fā)，對后續(xù)螞蟻的行動失去了吸引力，算法的隨機(jī)性和全局搜索能力雖然得到了增強(qiáng)，但是算法的收斂速度降低了；反之，當(dāng) 的取值過大時(shí)，路徑上信息素迅速的積累，使得螞蟻更傾向于搜索走過的路徑，算法的收斂速度加快，但是會影響到算法的隨機(jī)性和全局搜索能力。

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

1 杜衡吉;李勇;;蟻群算法中參數(shù)設(shè)置對其性能影響的研究[J];現(xiàn)代計(jì)算機(jī)(專業(yè)版);2012年13期

相關(guān)博士學(xué)位論文 前1條

1 董晨;粒子群優(yōu)化的超大規(guī)模集成電路全局布線策略[D];武漢大學(xué);2011年

本文編號：2781518