網絡可靠性優(yōu)化

網絡可靠性優(yōu)化方法總結概述：目前較流行的智能優(yōu)化方法包括遺傳算法以及群智能算法。這兩種優(yōu)化算法的共同特點就是模擬生物行為方式，進行全局隨機搜索，在單目標或多目標問題中找到最優(yōu)解。應用到網絡中比如用于網絡路由的自適應調整，解決QoS組播路由問題，在費用最低情況下求解使整個網絡可靠性最有拓撲等等遺傳算法（GA）遺傳算法(GA)是一種借鑒生物界自然選擇思想和遺傳機制的全局隨機搜索算法。它把問題的可能解組成種群，把每一個可能解看作種群的個體，運行時，算法在整個種群空間內隨機搜索，按一定的評估策略對每一個體進行評價，不斷使用選擇、交叉、變異這3種遺傳算子，使問題的解不斷進化，直至產生最優(yōu)解。GA基本內容包括編碼結構、種群初始化、選擇操作、遺傳操作(交叉和變異)、目標函數以及適應度函數設計、終止條件選擇等。其中，選擇、交叉和變異三種操作是遺傳算法的核心，選擇操作是根據父代中個體適應度函數值大小進行選擇或淘汰，保證了算法的最優(yōu)搜索方向；交叉操作是產生新個體的主要方法，它決定GA的全局搜索能力；變異操作是產生新個體的輔助方法，它決定GA的局部搜索能力。GA控制參數主要包括：種群規(guī)模、交叉率、變異率以及其它一些GA參數(如最大迭代次數等)。GA參數的選擇對于算法的最終優(yōu)化效果至關重要，目前，多以大量試驗測試的方法來確定這些參數。(1)編碼。遺傳算法不能直接處理解空間的數據，因此需要通過編碼把問題的解表示成遺傳空間里的染色體。(2)群體初始化。需要考慮兩個問題：1、群體的規(guī)模2、群體個體產生方法：(a)在遺傳空間中直接產生，即在遺傳空間中隨機地產生染色體。(b)編碼產生。（3）適應度評估選擇操作是以染色體的適應度為依據進行的，適應度通過適應度函數計算得到。染色體的適應度應該要能準確地描述染色體所對應的解的性能好壞：染色體的適應度越大，表明解的質量越高，該個體被選擇成為父代進而產生后代的的概率越大。通常，在設計適應度函數時，要遵循以下原則：(1)單值性。(2)非負性。(3)計算量小。適應度函數對遺傳算法的影響主要體現在三個方面：(1)適應度函數和選擇算子共同決定了群體中各個染色體產生后代的概率。適應度越大的個體產生后代的概率越大。(2)遺傳算法的終止條件受到適應度函數的影響。(3)問題的約束條件在適應度函數中考慮。（4）選擇算子從當前群體中挑選出優(yōu)良的個體直接遺傳到下一代或通過交叉操作產生新個體，從而將解的優(yōu)良性狀遺傳給子代。越優(yōu)良的個體，被選成父代進行遺傳操作的機會越大。保證了方法的最有搜索方向。幾種常見的選擇算子:1、輪盤賭選擇法2、錦標賽選擇法為了能夠清楚的理解螞蟻系統(tǒng)的數學模型，仍以求解平面上n個城市的旅行商問題（TravelingSalesmanProblem，TSP）為例說明在網絡方面的主要應用網絡路由問題：蟻群算法在動態(tài)組合優(yōu)化問題研究中的應用主要集中在通訊網絡方面.隨著Internet上廣泛的分布式多媒體應用對服務質量（QualityofService，QoS）需求的增長，各種服務應用對網絡所能提供的QoS提出了不同的要求，而路由是實現QoS的關鍵之一．將蟻群算法用于解決受限路由問題，目前可以解決包括帶寬、延時、包丟失率和最小花費等約束條件在內的QoS組播路由問題，比現有的鏈路狀態(tài)路由算法具有明顯的優(yōu)越性，應用蟻群算法求解更復雜的QoS問題還需要深入討論．無線傳感器網絡路由協議問題：作為一種新的信息獲取方式和處理模式，無線傳感器網絡(Wirelesssensornetwork，WSN)目前已經成為國內外備受關注的研究熱點．WSN是由眾多具有通信和計算能力的傳感器節(jié)點，以多跳通信、自組織方式形成的網絡．節(jié)點傳感器電池供電，電源能量、通信能力計算能力都是有限的．WSN路由協議研究中的一個重要問題是路由的選擇要結合節(jié)點的能量信息，使得節(jié)點的能量消耗能夠均衡，延長網絡生命周期．蟻群優(yōu)化算法求解模式將問題求解的快速性、全局優(yōu)化特征以及高度的自組織性等特點合理結合，與無線傳感網低能耗、自組織的大規(guī)模網絡路由快速建立要求極其相似，有助于建立面向數據為中心的路由協議．目前，已有許多學者研究蟻群優(yōu)化算法在WSN路由協議中的應用．粒子群算法(PSO)粒子群優(yōu)化(ParticleSwarmOptimization，PSO)算法是另一種群智能算法。在粒子群算法中引用了鳥群的概念。PSO也是一種基于群體的優(yōu)化工具，同時也是一種基于迭代的優(yōu)化工具。PSO算法原理PSO首先生成初始種群，即在可行解空間中隨機初始化一群粒子，每個粒子都是優(yōu)化問題的一個可行解，并根據目標函數構造一個適應度函數（fitnessfunction）。以該適應度函數作為評價標準。每個粒子在解空間中運動，該粒子運動的速度由個體的飛行經驗和群體的飛行經驗進行動態(tài)的調整，并經逐代搜索最后得到最優(yōu)解。在每一代中，粒子將跟蹤兩個極值，一個是粒子本身迄今找到的最優(yōu)解,另一個是整個種群中迄今找到的最優(yōu)解.PSO算法流程PSO的算法流程如下：（1）初始化一群隨機粒子，包括粒子的隨機位置和速度；（2）計算每個粒子的適應度值；（3）對于每個粒子，將其適應度值與其經歷過的最優(yōu)位置Pbest進行比較，如較好，則將其作為當前的最優(yōu)位置Pbest；（4）對于每個粒子，將其適應度值與全局所經歷過的最優(yōu)位置gbest進行比較，如較好，則重新設置gbest的索引號；（5）根據PSO算法的兩個計算公式變化粒子的速度和位置；（6）如果得到的適應度值足夠好或達到預設的最大迭代次數GAP，則返回第2步。網絡方面的主要應用：無線傳感器網路，近年來，將群智能算法應用于無線傳感器網絡問題引起了眾多研究者的關注．網絡節(jié)點位置優(yōu)化是無線傳感網絡研究的核心問題之一．由于無線傳感網絡中移動節(jié)點的位置優(yōu)化可以抽象為以移動節(jié)點位置構成的非整數向量為輸入參數，網絡有效覆蓋區(qū)域面積大小為優(yōu)化目標的優(yōu)化問題．對于此類問題，微粒群優(yōu)化算法相比其它算法具有更高的收斂速度、更強的全局搜索能力此外，微粒群算法在無線傳感器網絡路由協議中的應用也表現出了良好的優(yōu)化性能。人工魚群算法人工魚群算法是李小磊等在對動物群體智能行為研究的基礎上提出的一種新型仿生優(yōu)化算法。與傳統(tǒng)人工智能系統(tǒng)的自上而下的設計思路相比,該算法采用了自下而上的設計方法。所以,首先應著重構造魚群自治體的模型,具體模型描述如下:(1)覓食行為:平時我們會看到魚在水中游來游去,這一般可視為一種隨機移動。當魚群發(fā)現食物時,會向著食物逐漸增多的方向快速游去。(2)聚群行為:魚在游動過程中為了保證群體的生存和躲避危害而形成了一種生活習性——會自然地聚集成群。在這個群體中,每條魚都需要遵循一些局部相互作用的規(guī)則:①分隔規(guī)則:盡量避免與臨近伙伴過于擁擠;②內聚規(guī)則:盡量朝臨近伙伴的中心移動;③對準規(guī)則:盡量與臨近伙伴的平均方向一致。(3)追尾行為:在魚群的游動過程中,當其中一條或幾條食物時,其臨近的伙伴會尾隨其后快速到達食物點。(4)約束行為:在尋優(yōu)過程中,由于群聚行為、隨機行為等操作的作用,容易使人工魚的狀態(tài)變得不可行,此時就需要加入相應的約束對其進行歸整化,使它們由無效狀態(tài)或不可行狀態(tài)轉變?yōu)榭尚械摹?5)公告板:公告板用來記錄最優(yōu)人工魚的狀態(tài)。各人工魚在尋優(yōu)過程中,每次行動完畢就比較自身狀態(tài)與公告板的狀態(tài),若自身狀態(tài)優(yōu)于公告板狀態(tài),就將公告板狀態(tài)改寫為自身狀態(tài),這樣公告板記錄下的