本站小編為你精心準備了自適應(yīng)遺傳算法參考范文，愿這些范文能點燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

[摘要文章以均衡網(wǎng)絡(luò)業(yè)務(wù)為優(yōu)化目標，提出了一種基于自適應(yīng)遺傳算法的資源優(yōu)化路由算法，采用改進的適應(yīng)度函數(shù)和自適應(yīng)的交叉變異算子。理論分析表明該算法改善了最短路徑路由算法輕易發(fā)生阻塞及平安性不好的缺點，和基本遺傳算法相比，它顯著提高了收斂性能，并且具有很強的自適應(yīng)能力。

[負載均衡；遺傳算法；資源優(yōu)化利用

1引言

傳統(tǒng)的Internet路由協(xié)議默認的總是使用最短路徑轉(zhuǎn)發(fā)數(shù)據(jù)分組，經(jīng)常導(dǎo)致網(wǎng)絡(luò)上的流量分布不平衡,使得網(wǎng)絡(luò)上有些鏈路因為過負荷產(chǎn)生擁塞現(xiàn)象，而另一些鏈路資源卻處于閑置狀態(tài),增加丟包率和惡化資源利用率。流量工程的主要目的就是優(yōu)化資源利用率，提高網(wǎng)絡(luò)性能，增加網(wǎng)絡(luò)的健壯性。使在滿足業(yè)務(wù)質(zhì)量要求的前提下，使網(wǎng)絡(luò)中的資源得到全面合理的利用，盡量避免出現(xiàn)一部分資源被過度利用而另一部分資源卻沒有被充分利用的情況。

在流量工程探究之前，普遍采用的靜態(tài)路由配置方法是使用手工配置或簡單的路由算法，如最短路徑算法，但隨著網(wǎng)絡(luò)的日益復(fù)雜，原先的配置方法已經(jīng)無法適應(yīng)現(xiàn)有的網(wǎng)絡(luò)環(huán)境，而且由于每次只能配置一條LSP，不能使網(wǎng)絡(luò)達到全局的優(yōu)化，由文獻知，在靜態(tài)業(yè)務(wù)下可為多條LSP同時分配網(wǎng)絡(luò)資源,使網(wǎng)絡(luò)資源達到優(yōu)化利用。本文將具有強約束條件的網(wǎng)絡(luò)資源均衡和優(yōu)化的新問題轉(zhuǎn)化為組合優(yōu)化的最短路新問題，并設(shè)計利用一種改進的遺傳算法進行一定迭代數(shù)使其以最快速度得到最優(yōu)解。

2網(wǎng)絡(luò)模型假設(shè)及衡量指標的數(shù)學(xué)描述

一個網(wǎng)絡(luò)可以數(shù)學(xué)表示為一個有向圖G（V﹐E），其中V為網(wǎng)絡(luò)節(jié)點的集合，E表示路由器之間的鏈路集合。假設(shè)網(wǎng)絡(luò)的鏈路數(shù)為n，即=n，鏈路l的帶寬容量是。設(shè)所要配置的路徑組為LSP＝（﹐﹐…﹐）,為其中一條要配置的路徑(1

網(wǎng)絡(luò)資源優(yōu)化的一個重要指標是讓網(wǎng)絡(luò)中每個鏈路的資源利用率保持在一種趨于平衡的狀態(tài)，使得網(wǎng)絡(luò)對請求的接受率盡量高。因網(wǎng)絡(luò)預(yù)留帶寬為，設(shè)為第i條LSP的帶寬需求。設(shè)為第i條LSP中鏈路l的剩余帶寬（=-），則有鏈路l的資源空閑率摘要：

=

假如1，則表示鏈路幾乎被占滿，此鏈路不平安。當%26lt;%26lt;1時，說明鏈路l還有很多剩余帶寬可供使用，這條鏈路是平安的。當%26gt;1時，此鏈路不能滿足要求。

通過可以求出網(wǎng)絡(luò)中鏈路的資源空閑率的均值，即摘要：

=

該文用網(wǎng)絡(luò)負載平衡度來表征網(wǎng)絡(luò)各鏈路的資源空閑率相對于均值的偏離程度，記為DU,顯然有DU的值越小，負載越均衡。所以網(wǎng)絡(luò)資源優(yōu)化的新問題轉(zhuǎn)換為在消耗網(wǎng)絡(luò)資源較少情況下，盡量使網(wǎng)絡(luò)負載保持均衡即DU最小，其數(shù)學(xué)公式描述如下摘要：

DU=

3基于自適應(yīng)遺傳算法的網(wǎng)絡(luò)資源優(yōu)化路由算法

遺傳算法是通過模擬自然進化過程搜索最優(yōu)解的方法。它將新問題的求解表示成“染色體”的適者生存過程,通過“染色體”群的一代代不斷進化,包括復(fù)制、交叉和變異等操作,直到滿足一定性能指標和收斂條件終止,從而求得新問題的最優(yōu)解或滿足解。對于基本遺傳算法，在搜索過程的起始階段，群體中經(jīng)常有極少的個體相對于大多數(shù)個體而言適應(yīng)度非常好，在比例選擇下這幾個非常好的個體就可能會控制整個選擇過程，使得進一步進化成為不可能，從而導(dǎo)致所謂得“早熟”現(xiàn)象；另一方面，在搜索過程得后期，群體中可能還存在足夠得多樣性，然而群體的平均適應(yīng)度可能會接近群體中的最優(yōu)適應(yīng)度，這時在后繼代中具有平均適應(yīng)度的個體和最好的個體就幾乎會得到相同的復(fù)制數(shù)目，導(dǎo)致群體進化困難，降低了收斂速度?；谶@一新問題，本文擬通過一種自適應(yīng)的比例變換方式來改進遺傳算法，使群體能夠以最快速度向最優(yōu)解進化，提高收斂速度，并且避免早熟。

3.1染色體編碼

這里將對應(yīng)終端節(jié)點對（,,）的所有滿足約束條件的路由組成的集合稱為(1

例如，假如要建立4條LSP，每條LSP有3條備選路徑，則個體1234(即=(1224))表示LSP1選擇第1條備選路徑，LSP2選擇第2條備選路徑，LSP3選擇第2條備選路徑，LSP4選擇第4條備選路徑。編碼確定后，隨機產(chǎn)生一組個體組成初始群體。

3.2適應(yīng)度函數(shù)的選擇

首先求出每個個體的適應(yīng)度函數(shù)f(x)=DU,再利用公式F(x)=f(x)-β。

其中f(x)變換前的適應(yīng)度；

變換前的適應(yīng)度的最小值；F(x)變換后的適應(yīng)度；

β———自適應(yīng)控制參數(shù)；β＝0.9-(-)/；

其中———變換前適應(yīng)度的最大值。

當群體種個體差異很大時，即(-)/%26gt;0.9時，β為負數(shù)，此時個體適應(yīng)度增大，并且相對于適應(yīng)度小的個體來說，其增長的幅度較大，從而保證差的個體也有機會進化；當群體種的個體差異很小時，即(-)/0時，此時β0.9，導(dǎo)致所有的個體適應(yīng)度下降，整個群體的平均適應(yīng)度也下降，并且拉大了個體之間的差異，有利于向更優(yōu)的解進行

3.3選擇算子

選擇的基礎(chǔ)是對群體中個體適應(yīng)度的評價。采用比例選擇法結(jié)合最優(yōu)個體保存策略。比例選擇法,也稱輪盤賭選擇法。在該辦法中，各個個體的選擇概率和其適應(yīng)度值成比例。設(shè)群體規(guī)模大小為S，個體x的適應(yīng)度為F(x)，則個體x被選中的概率用如下公式計算。

適應(yīng)度越高的個體被選中的概率也越大,反之亦然.由于這種方法是基于概率選擇,存在統(tǒng)計誤差.因此結(jié)合最優(yōu)保存策略,來保證當前適應(yīng)度最好的個體能夠進化到下一代,不被遺傳操作的隨機性破壞掉,保證算法的收斂性.

3.4自適應(yīng)交叉算子和變異算子

設(shè)計交叉和變異算子的兩個原則是摘要：

3.4.1不要太多地破壞群體中表示優(yōu)良性狀的優(yōu)良模式，以保證算法的收斂性；

3.4.2能夠有效地產(chǎn)生出一些新的個體模式，保持群體的多樣性，避免陷入局部最優(yōu)解。根據(jù)和調(diào)整適應(yīng)度同樣的思想，也可以對交叉率和變異率進行自適應(yīng)調(diào)整。取=(0.9-β),的取值范圍為[0,1。由計算公式知當個體差異較大時，Pc取值較大，這是因為較優(yōu)的個體比重大，從而經(jīng)交叉后產(chǎn)生更好的解可機率也大，以加快尋優(yōu)過程；而差異小時，則減少交叉率，避免多余的計算。而取變異率=0.01*(0.1+β),的取值范圍為[0,0.05。變異的功能在于保持群體的多樣性，由公式知當個體差異較大時，較小，可保持群體多樣性；而當個體差異小時，較大，以向更廣的解空間進行搜索，避免落入局部極少點。這種隨適應(yīng)度自適應(yīng)變化的交叉變異算子一方面能保持群體整體朝適應(yīng)度高的方向進化，提高算法收斂效率，另一方面，當群體中的個體差異不大時，增大變異率，避免早熟。

4算法復(fù)雜性分析和正確性驗證

上面算法的關(guān)鍵步驟是利用Dijkstra算法找出滿足帶寬約束的從源節(jié)點s到目的節(jié)點d對之間的最短路徑、第二最短路徑、…、第k最短路徑。由文獻知，網(wǎng)絡(luò)中計算最短路徑的復(fù)雜度是O()，計算第二最短路徑的復(fù)雜度是O(),…，計算第k最短路徑的復(fù)雜度是O()。根據(jù)網(wǎng)絡(luò)的帶寬需求和實際的預(yù)留帶寬，該算法的計算復(fù)雜度取決于算法實現(xiàn)中所確定的需要計算的第k條最短路徑的復(fù)雜度即O()。為避免算法復(fù)雜度過高，可以根據(jù)實際需要和時延的限制，指定k的取值范圍。

算法正確性的驗證摘要：該算法是應(yīng)用負載平衡度作為衡量鏈路負載指標，其所選路徑盡量讓負載分布均衡，遠離擁擠區(qū)域。在盡量減小網(wǎng)絡(luò)資源消耗的基礎(chǔ)上，充分考慮了網(wǎng)絡(luò)的負載平衡，達到了優(yōu)化網(wǎng)絡(luò)資源的目的。

5總結(jié)

本文利用文獻所提出的算法基本思想，對其進行改進，設(shè)計一種自適應(yīng)的遺傳算法來實現(xiàn)網(wǎng)絡(luò)的資源優(yōu)化利用。該算法簡單，高效。和最短路徑算法和基本遺傳算法相比，性能更穩(wěn)定，并且提高了算法效率以及優(yōu)化性能，因此該算法將在網(wǎng)絡(luò)資源優(yōu)化利用中具有一定的理論和實際意義。