光網(wǎng)絡規(guī)劃問題的智能優(yōu)化算法研究.pdf

1、隨著網(wǎng)絡通信流量的急劇增大，光網(wǎng)絡規(guī)劃與建設的相關研究得到了越來越多的重視。由于與網(wǎng)絡建設運營成本直接相關，光網(wǎng)絡流量疏導規(guī)劃成為光網(wǎng)絡通信領域的核心問題之一。光網(wǎng)絡流量疏導的幾個子問題已被證明為NP難，且這些問題并沒有與其完全對應的傳統(tǒng)NP難問題，因此光網(wǎng)絡流量疏導相關問題不論是在學術科研領域還是在實際生產(chǎn)工業(yè)界都是重要的具有挑戰(zhàn)性的課題。
　　由于光網(wǎng)絡流量疏導相關問題的復雜性極高，即使是小規(guī)模算例也很難使用精確算法在短時間內(nèi)

2、進行求解。因此使用啟發(fā)式算法，或啟發(fā)式與精確算法的結合算法是求解該問題的唯一有效方法。元啟發(fā)式算法被廣泛用于求解復雜組合優(yōu)化問題，是求解NP難問題的有力工具之一。本文的研究重點是設計高效的元啟發(fā)式算法用于求解光網(wǎng)絡流量疏導相關問題。同時，本文對所述算法的重要特性進行了分析與說明。本文的主要貢獻有
　　1.針對帶流量疏導的網(wǎng)絡設計問題以及帶簡單路約束的流量疏導與路由問題這兩個真實工業(yè)運用上急需解決的問題，本文首次給出了它們的一般化數(shù)

3、學模型，為問題研究奠定了基礎。
　　2.提出了用于求解帶流量疏導的網(wǎng)絡設計問題的混合精確禁忌算法（HETS）。算法具有以下特點。
　　2.1 算法將線性規(guī)劃算法及整數(shù)線性規(guī)劃算法作為子過程嵌入迭代的禁忌搜索算法。結合了規(guī)劃算法的精確性以及禁忌搜索算法的高效性。
　　2.2 為該問題的子問題——流量疏導問題——給出了擁有良好松弛下界的整數(shù)線性規(guī)劃模型。該模型求解速度快，且線性松弛解與整數(shù)解差異極小。
　　2.3 提

4、出了基于邊旋轉鄰域結構。該鄰域結構通過選擇適當?shù)倪呥M行操作以減少算法計算量，提高了搜索的有效性。同時針對該鄰域結構提出了相應的快速評估技術，提高了搜索效率。該技術使用算法模型的線性松弛模型對鄰域解進行估算。
　　2.4 使用帶流量疏導的網(wǎng)絡設計問題的22公共算例對HETS算法進行了測試，HETS改進了22個公共算例中21個算例的最優(yōu)解，1個算例的解與當前最好解持平。且與文獻引用算法對比，HETS的計算時間優(yōu)勢巨大。
　　3.

5、提出了用于求解帶簡單路約束的流量疏導與路由問題的自適應隨機貪心算法（GRASP）。算法具有以下特點：
　　3.1 算法主構架由貪心構造過程與局部搜索優(yōu)化過程迭代組成。其中局部搜索優(yōu)化過程為多個局部搜索算法嵌套構成的復合局部搜索算法。
　　3.2 為算法上層局部搜索過程設計了帶權復合信息目標函數(shù)，保證了子過程之間切換的連續(xù)性，使得它們之間的合作更為有效，提高了算法的求解優(yōu)度和效率。
　　3.3 使用基于實際工程特性的隨機

6、算例集對算法進行了測試。與公共通用優(yōu)化求解軟件CPLEX和LocalSolver的結果進行對比，GRASP算法性能及優(yōu)度遠超通用求解軟件，且GRASP算法能夠求解通用求解器所不能求解的大規(guī)模算例。
　　4.針對路由與波長分配問題，提出了多鄰域迭代禁忌算法（MN-ITS）。算法具有以下特點：
　　4.1 為該算法提出了三種不同鄰域結構以搜索不同的解空間，有效增大了算法的搜索范圍。同時，為這三種鄰域結構設計了統(tǒng)一的增量更新評估方

7、案，使得算法能夠平滑地在各鄰域間進行切換。
　　4.2 使用路由與波長分配問題的88個公共算例對算法進行測試，并與其它文獻中優(yōu)秀算法進行了對比。MN-ITS能夠求得W算例集中所有算例的最優(yōu)解，以及42個Y算例的歷史最優(yōu)解。同時MN-ITS算法更新了Y算例集中5個算例的歷史最優(yōu)解。
　　5.使用邏輯證明以及對比實驗對本文所提算法進行了分析，解釋說明了本文所提算法特性的思想原理，同時驗證了這些特性的有效性與高效性。
　　本

8、文的研究為網(wǎng)絡結構問題的數(shù)學建模給出了指導。同時本文為復雜優(yōu)化問題的啟發(fā)式求解算法設計指明了方向，其中包括如何對復雜問題進行鄰域結構設計；如何有效對復雜鄰域結構進行評估；如何對復雜問題進行拆分求解；如何協(xié)調(diào)各鄰域結構使其有效合作；以及如何將精確算法與啟發(fā)式算法相結合以獲取這兩種算法的優(yōu)勢。同時本文所述算法技術具有普適性，可嘗試將其應用到其它類型相似結構的NP難優(yōu)化問題中，以期望得到類似的改進效果。融合本文所述各算法可以開發(fā)出解決光網(wǎng)絡流