基于可視化實驗的Steiner樹問題的全局優(yōu)化算法研究.pdf

1、系統(tǒng)全局最短路徑是非線性組合優(yōu)化中的經(jīng)典問題之一，在實際中有著廣泛的應用，最小 Steiner樹問題是全局最短路徑研究的理論基礎。因此研究最小Steiner樹的全局優(yōu)化算法具有重要的理論意義和廣泛的應用價值。由于最小Steiner樹問題已被證明是NP-hard問題，除非P=NP，否則Steiner樹問題不存在多項式時間算法，因此尋找合適的智能優(yōu)化算法是求解此問題的有效途徑。
　　本文以物理可視化實驗為依托，采用實驗→算法→實驗→工

2、程應用的技術研究路線，對可視化實驗裝置、實驗過程以及實驗結果進行詳細的分析、研究，探索固定點的分布形狀對構造最小 Steiner樹的影響，以及 Steiner虛設點的位置、數(shù)目與給定端點的位置以及分布形狀之間的關系，將最小 Steiner樹問題分為兩種情況進行求解。當固定點集為凸集時，我們直接用 Melzak法構造最小 Steiner樹；當固定點為非凸集時，通過改進的遺傳算法對它進行求解。對于存在障礙物的 Steiner樹問題，本文也進

3、行了一些實驗，并分析了障礙物的形狀和位置與Steiner虛設點的關系。
　　本文設計的遺傳算法采用試探選擇算法來選取初始種群，并且構造出滿足自適應過程的交叉算子。通過采用試探選擇算法來選取初始種群，使得遺傳算法的收斂速度大大提高。而交叉算子滿足自適應過程，有利于遺傳算法得到自身最適合的交叉概率，提高算法的精度和收斂速度。同時通過遺傳算法搜索得到的最優(yōu)解直接以 Steiner虛設點的形式存在，彌補了國際 SteinLib測試數(shù)據(jù)庫中