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

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

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

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

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

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

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

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

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