遺傳算法在網(wǎng)絡(luò)優(yōu)化問題中的應(yīng)用.pdf

1、許多網(wǎng)絡(luò)優(yōu)化問題都是NP-hard問題，這些問題的求解時間隨著問題規(guī)模增大而呈指數(shù)增長，因此往往需要采用近似算法進(jìn)行求解。遺傳算法(Genetic Algorithm, GA)作為一種全局優(yōu)化搜索算法，由于其具有自學(xué)習(xí)、隱并行性等特點(diǎn)，所以能較快的求解NP-hard問題，最終得到較好的近似最優(yōu)解。本文討論了遺傳算法在chord環(huán)查詢映射系統(tǒng)優(yōu)化、IP網(wǎng)絡(luò)域內(nèi)流量規(guī)劃和LISP網(wǎng)絡(luò)域內(nèi)流量規(guī)劃這三個典型的網(wǎng)絡(luò)優(yōu)化問題中的應(yīng)用。
　　

2、Chord環(huán)查詢映射系統(tǒng)優(yōu)化是要找到一種虛節(jié)點(diǎn)和物理節(jié)點(diǎn)的映射關(guān)系，使得每次訪問的平均查詢延遲最短。針對該問題，本文第二章提出了GAOQCS算法來進(jìn)行優(yōu)化求解。在GAOQCS算法中，先對不同的映射關(guān)系進(jìn)行編碼，并設(shè)計雜交算子保證算法子代個體的可行性，通過仿真分析確定算法的遺傳參數(shù)。使用隨機(jī)網(wǎng)絡(luò)拓?fù)浜蜆I(yè)務(wù)量矩陣所作的實(shí)驗(yàn)表明，相比隨機(jī)產(chǎn)生節(jié)點(diǎn)映射關(guān)系的情況，GAOQCS的性能平均提高了30％左右。
　　IP網(wǎng)絡(luò)域內(nèi)流量規(guī)劃是要尋找一

3、套鏈路權(quán)重，使得全網(wǎng)流量負(fù)載均衡(即最大鏈路利用率最小)。與傳統(tǒng)鄰域搜索算法不同，第三章提出新的方法來精確調(diào)整鏈路權(quán)重，該方法從搬移業(yè)務(wù)的角度出發(fā)，根據(jù)搬移的業(yè)務(wù)量來確定某條鏈路的權(quán)值增加量，以達(dá)到期望的網(wǎng)絡(luò)流量分布。本章最后提出了IGAOSPF算法，將上述方法作為性能提高模塊嵌套在遺傳算法框架中。實(shí)驗(yàn)表明，IGAOSPF算法較以前的遺傳算法性能提高了3%左右。
　　不同于IP網(wǎng)絡(luò)域內(nèi)流量規(guī)劃，LISP網(wǎng)絡(luò)域內(nèi)流量規(guī)劃包括入口路由