1、 分類號(hào) 密級(jí) UDC 編號(hào) 碩 士 學(xué) 位 論 文 基于可視化實(shí)驗(yàn)的 Steiner 樹(shù)問(wèn)題的全局優(yōu)化算法研究 學(xué) 位 申 請(qǐng) 人： 葉坤 指 導(dǎo) 教 師： 楊宗霄 教授 學(xué) 科 專 業(yè)： 業(yè)：

2、 計(jì)算機(jī)應(yīng)用技術(shù) 學(xué) 位 類 別： 別： 工學(xué) 2012 年 3 月 摘要 論文題目： 論文題目：基于可視化實(shí)驗(yàn)的 基于可視化實(shí)驗(yàn)的 Steiner 樹(shù)問(wèn)題的全局優(yōu)化算法研究 樹(shù)問(wèn)題的全局優(yōu)化算法研究 專 業(yè)： 業(yè)：計(jì)算機(jī)應(yīng)用技術(shù) 計(jì)算機(jī)應(yīng)用技術(shù) 研 究 生： 生：葉坤 葉坤 指導(dǎo)教

3、師： 指導(dǎo)教師：楊宗霄 楊宗霄 教授 教授 摘 要 系統(tǒng)全局最短路徑是非線性組合優(yōu)化中的經(jīng)典問(wèn)題之一，在實(shí)際中有著廣泛的應(yīng)用，最小 Steiner 樹(shù)問(wèn)題是全局最短路徑研究的理論基礎(chǔ)。因此研究最小Steiner 樹(shù)的全局優(yōu)化算法具有重要的理論意義和廣泛的應(yīng)用價(jià)值。由于最小Steiner 樹(shù)問(wèn)題已被證明是 NP-hard 問(wèn)題，除非 P=NP，否則 Steiner 樹(shù)問(wèn)題不存在多項(xiàng)式時(shí)間算法，因此尋找合適的智能優(yōu)化算法是求解此問(wèn)題的

4、有效途徑。 本文以物理可視化實(shí)驗(yàn)為依托，采用實(shí)驗(yàn)→算法→實(shí)驗(yàn)→工程應(yīng)用的技術(shù)研究路線，對(duì)可視化實(shí)驗(yàn)裝置、實(shí)驗(yàn)過(guò)程以及實(shí)驗(yàn)結(jié)果進(jìn)行詳細(xì)的分析、研究，探索固定點(diǎn)的分布形狀對(duì)構(gòu)造最小 Steiner 樹(shù)的影響，以及 Steiner 虛設(shè)點(diǎn)的位置、數(shù)目與給定端點(diǎn)的位置以及分布形狀之間的關(guān)系，將最小 Steiner 樹(shù)問(wèn)題分為兩種情況進(jìn)行求解。當(dāng)固定點(diǎn)集為凸集時(shí)，我們直接用 Melzak 法構(gòu)造最小 Steiner樹(shù)；當(dāng)固定點(diǎn)為非凸集時(shí)，通過(guò)改進(jìn)

5、的遺傳算法對(duì)它進(jìn)行求解。對(duì)于存在障礙物的 Steiner 樹(shù)問(wèn)題，本文也進(jìn)行了一些實(shí)驗(yàn)，并分析了障礙物的形狀和位置與Steiner 虛設(shè)點(diǎn)的關(guān)系。 本文設(shè)計(jì)的遺傳算法采用試探選擇算法來(lái)選取初始種群，并且構(gòu)造出滿足自適應(yīng)過(guò)程的交叉算子。通過(guò)采用試探選擇算法來(lái)選取初始種群，使得遺傳算法的收斂速度大大提高。而交叉算子滿足自適應(yīng)過(guò)程，有利于遺傳算法得到自身最適合的交叉概率，提高算法的精度和收斂速度。同時(shí)通過(guò)遺傳算法搜索得到的最優(yōu)解直接以 Ste

6、iner 虛設(shè)點(diǎn)的形式存在，彌補(bǔ)了國(guó)際 SteinLib 測(cè)試數(shù)據(jù)庫(kù)中目標(biāo)函數(shù)未計(jì)入 Steiner 虛設(shè)點(diǎn)的不足。 本文通過(guò)簡(jiǎn)單的圖形實(shí)例驗(yàn)證了本算法的可行性，并通過(guò)幾個(gè)具體實(shí)例，如某高校教職工住宅區(qū)供熱管道規(guī)劃實(shí)例，五省一市選址實(shí)例，輸電網(wǎng)線路規(guī)劃實(shí)例等，對(duì)遺傳算法與可視化實(shí)驗(yàn)得到的結(jié)果進(jìn)行對(duì)比分析，證明了算法的實(shí)用性與有效性。大量的實(shí)例證明本算法能夠與可視化實(shí)驗(yàn)配套使用來(lái)解決工程實(shí)際問(wèn)題，并為下一步的實(shí)驗(yàn)方法的改進(jìn)和完善奠定基礎(chǔ)。