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

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

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

1引言

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

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

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

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

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

=

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

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

=

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

DU=

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

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

3.1染色體編碼

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

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

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

首先求出每個(gè)個(gè)體的適應(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)度的最大值。

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

3.3選擇算子

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

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

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

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

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

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

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

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

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

5總結(jié)

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