遺傳算法在網絡優(yōu)化問題中的應用.pdf

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

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

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