基于遺傳算法的選播路由算法研究.pdf

1、選播(Anycast)是IPv6中的一種標準通信模型，可以實現(xiàn)一臺主機與一組具有相同選播地址的目的主機中“最近”的一臺主機進行通信(這組目的主機提供相同的服務(wù))。選播服務(wù)的主要功能是允許用戶根據(jù)需要做出合適的選擇，因此路由問題是選播技術(shù)的關(guān)鍵問題，它直接決定了網(wǎng)絡(luò)服務(wù)的可用性和效率的高低。 具有時延約束和代價要求的選播路由問題是一個NP完全問題，遺傳算法通常用于解決此類問題?！霸缡臁笔諗渴沁z傳算法在實際應(yīng)用中常見的一個疑難問題，

2、主要表現(xiàn)為種群中最優(yōu)個體的適應(yīng)度值得不到提高，種群在經(jīng)過若干迭代后仍找不到最優(yōu)解，而造成“早熟”的主要原因是群體多樣性的過早缺失。 本文在深入分析和研究選播服務(wù)模型和選播路由算法的基礎(chǔ)上，針對上述問題，給出了一種基于改進的遺傳算法的選播QoS路由算法。該算法可以解決具有時延約束的條件下要求代價最小的選播路由問題。 本算法把遺傳算法應(yīng)用于選播QoS路由問題中，發(fā)揮其并行性和群體尋優(yōu)的特點；引入相異度的思想改進交叉算子和變異

3、算子來增加群體的多樣性；利用模擬退火理論調(diào)整和改進適應(yīng)度函數(shù)，使得種群中個體的適應(yīng)度值在進化過程中得到明顯提高；改進了初始種群的生成方法，使其生成多樣化且“起點”較高的初始種群。從而抑制“早熟”收斂的發(fā)生。 為了驗證算法的有效性和收斂性，本文有針對性地設(shè)計一個仿真實驗平臺，并實現(xiàn)了該算法的仿真。大量仿真實驗表明，本算法能夠從多個選播成員中找到滿足選播QoS請求(滿足時延限制，且代價最小)的最優(yōu)路徑為用戶提供服務(wù)，且算法是有效和收