本站小編為你精心準備了自適應遺傳算法參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。
[摘要文章以均衡網絡業務為優化目標，提出了一種基于自適應遺傳算法的資源優化路由算法，采用改進的適應度函數和自適應的交叉變異算子。理論分析表明該算法改善了最短路徑路由算法輕易發生阻塞及平安性不好的缺點，和基本遺傳算法相比，它顯著提高了收斂性能，并且具有很強的自適應能力。
[負載均衡；遺傳算法；資源優化利用
1引言
傳統的Internet路由協議默認的總是使用最短路徑轉發數據分組，經常導致網絡上的流量分布不平衡,使得網絡上有些鏈路因為過負荷產生擁塞現象，而另一些鏈路資源卻處于閑置狀態,增加丟包率和惡化資源利用率。流量工程的主要目的就是優化資源利用率，提高網絡性能，增加網絡的健壯性。使在滿足業務質量要求的前提下，使網絡中的資源得到全面合理的利用，盡量避免出現一部分資源被過度利用而另一部分資源卻沒有被充分利用的情況。
在流量工程探究之前，普遍采用的靜態路由配置方法是使用手工配置或簡單的路由算法，如最短路徑算法，但隨著網絡的日益復雜，原先的配置方法已經無法適應現有的網絡環境，而且由于每次只能配置一條LSP，不能使網絡達到全局的優化，由文獻知，在靜態業務下可為多條LSP同時分配網絡資源,使網絡資源達到優化利用。本文將具有強約束條件的網絡資源均衡和優化的新問題轉化為組合優化的最短路新問題，并設計利用一種改進的遺傳算法進行一定迭代數使其以最快速度得到最優解。
2網絡模型假設及衡量指標的數學描述
一個網絡可以數學表示為一個有向圖G（V﹐E），其中V為網絡節點的集合，E表示路由器之間的鏈路集合。假設網絡的鏈路數為n，即=n，鏈路l的帶寬容量是。設所要配置的路徑組為LSP＝（﹐﹐…﹐）,為其中一條要配置的路徑(1
網絡資源優化的一個重要指標是讓網絡中每個鏈路的資源利用率保持在一種趨于平衡的狀態，使得網絡對請求的接受率盡量高。因網絡預留帶寬為，設為第i條LSP的帶寬需求。設為第i條LSP中鏈路l的剩余帶寬（=-），則有鏈路l的資源空閑率摘要：
=
假如1，則表示鏈路幾乎被占滿，此鏈路不平安。當%26lt;%26lt;1時，說明鏈路l還有很多剩余帶寬可供使用，這條鏈路是平安的。當%26gt;1時，此鏈路不能滿足要求。
通過可以求出網絡中鏈路的資源空閑率的均值，即摘要：
=
該文用網絡負載平衡度來表征網絡各鏈路的資源空閑率相對于均值的偏離程度，記為DU,顯然有DU的值越小，負載越均衡。所以網絡資源優化的新問題轉換為在消耗網絡資源較少情況下，盡量使網絡負載保持均衡即DU最小，其數學公式描述如下摘要：
DU=
3基于自適應遺傳算法的網絡資源優化路由算法
遺傳算法是通過模擬自然進化過程搜索最優解的方法。它將新問題的求解表示成“染色體”的適者生存過程,通過“染色體”群的一代代不斷進化,包括復制、交叉和變異等操作,直到滿足一定性能指標和收斂條件終止,從而求得新問題的最優解或滿足解。對于基本遺傳算法，在搜索過程的起始階段，群體中經常有極少的個體相對于大多數個體而言適應度非常好，在比例選擇下這幾個非常好的個體就可能會控制整個選擇過程，使得進一步進化成為不可能，從而導致所謂得“早熟”現象；另一方面，在搜索過程得后期，群體中可能還存在足夠得多樣性，然而群體的平均適應度可能會接近群體中的最優適應度，這時在后繼代中具有平均適應度的個體和最好的個體就幾乎會得到相同的復制數目，導致群體進化困難，降低了收斂速度?；谶@一新問題，本文擬通過一種自適應的比例變換方式來改進遺傳算法，使群體能夠以最快速度向最優解進化，提高收斂速度，并且避免早熟。
3.1染色體編碼
這里將對應終端節點對（,,）的所有滿足約束條件的路由組成的集合稱為(1
例如，假如要建立4條LSP，每條LSP有3條備選路徑，則個體1234(即=(1224))表示LSP1選擇第1條備選路徑，LSP2選擇第2條備選路徑，LSP3選擇第2條備選路徑，LSP4選擇第4條備選路徑。編碼確定后，隨機產生一組個體組成初始群體。
3.2適應度函數的選擇
首先求出每個個體的適應度函數f(x)=DU,再利用公式F(x)=f(x)-β。
其中f(x)變換前的適應度；
變換前的適應度的最小值；F(x)變換后的適應度；
β———自適應控制參數；β＝0.9-(-)/；
其中———變換前適應度的最大值。
當群體種個體差異很大時，即(-)/%26gt;0.9時，β為負數，此時個體適應度增大，并且相對于適應度小的個體來說，其增長的幅度較大，從而保證差的個體也有機會進化；當群體種的個體差異很小時，即(-)/0時，此時β0.9，導致所有的個體適應度下降，整個群體的平均適應度也下降，并且拉大了個體之間的差異，有利于向更優的解進行
3.3選擇算子
選擇的基礎是對群體中個體適應度的評價。采用比例選擇法結合最優個體保存策略。比例選擇法,也稱輪盤賭選擇法。在該辦法中，各個個體的選擇概率和其適應度值成比例。設群體規模大小為S，個體x的適應度為F(x)，則個體x被選中的概率用如下公式計算。
適應度越高的個體被選中的概率也越大,反之亦然.由于這種方法是基于概率選擇,存在統計誤差.因此結合最優保存策略,來保證當前適應度最好的個體能夠進化到下一代,不被遺傳操作的隨機性破壞掉,保證算法的收斂性.
3.4自適應交叉算子和變異算子
設計交叉和變異算子的兩個原則是摘要：
3.4.1不要太多地破壞群體中表示優良性狀的優良模式，以保證算法的收斂性；
3.4.2能夠有效地產生出一些新的個體模式，保持群體的多樣性，避免陷入局部最優解。根據和調整適應度同樣的思想，也可以對交叉率和變異率進行自適應調整。取=(0.9-β),的取值范圍為[0,1。由計算公式知當個體差異較大時，Pc取值較大，這是因為較優的個體比重大，從而經交叉后產生更好的解可機率也大，以加快尋優過程；而差異小時，則減少交叉率，避免多余的計算。而取變異率=0.01*(0.1+β),的取值范圍為[0,0.05。變異的功能在于保持群體的多樣性，由公式知當個體差異較大時，較小，可保持群體多樣性；而當個體差異小時，較大，以向更廣的解空間進行搜索，避免落入局部極少點。這種隨適應度自適應變化的交叉變異算子一方面能保持群體整體朝適應度高的方向進化，提高算法收斂效率，另一方面，當群體中的個體差異不大時，增大變異率，避免早熟。
4算法復雜性分析和正確性驗證
上面算法的關鍵步驟是利用Dijkstra算法找出滿足帶寬約束的從源節點s到目的節點d對之間的最短路徑、第二最短路徑、…、第k最短路徑。由文獻知，網絡中計算最短路徑的復雜度是O()，計算第二最短路徑的復雜度是O(),…，計算第k最短路徑的復雜度是O()。根據網絡的帶寬需求和實際的預留帶寬，該算法的計算復雜度取決于算法實現中所確定的需要計算的第k條最短路徑的復雜度即O()。為避免算法復雜度過高，可以根據實際需要和時延的限制，指定k的取值范圍。
算法正確性的驗證摘要：該算法是應用負載平衡度作為衡量鏈路負載指標，其所選路徑盡量讓負載分布均衡，遠離擁擠區域。在盡量減小網絡資源消耗的基礎上，充分考慮了網絡的負載平衡，達到了優化網絡資源的目的。
5總結
本文利用文獻所提出的算法基本思想，對其進行改進，設計一種自適應的遺傳算法來實現網絡的資源優化利用。該算法簡單，高效。和最短路徑算法和基本遺傳算法相比，性能更穩定，并且提高了算法效率以及優化性能，因此該算法將在網絡資源優化利用中具有一定的理論和實際意義。