QoS組播路由的并行遺傳算法研究.pdf

1、隨著Internet中多媒體實時業(yè)務(wù)的廣泛應用，人們對QoS(Quality ofService)組播的需求日益增長，然而研究表明，QoS組播路由帶有多個QoS約束參數(shù)，它是一個NP(Non-deterministic Polynomial)完全問題，對于此類問題傳統(tǒng)的組播協(xié)議和算法已經(jīng)不再適用。而隨著啟發(fā)式算法的興起，使用遺傳算法求解QoS組播路由問題成為研究中的熱點。
　　 使用遺傳算法求解QoS組播路由問題的基本思想是在一

2、個大的空間范圍內(nèi)搜索和產(chǎn)生較優(yōu)個體，這就產(chǎn)生了巨大時間復雜度和空間復雜度，算法的收斂速度也受到較大影響。本文針對遺傳算法的這兩個缺陷，使用以下兩種方式解決：一是提高算法搜索空間的能力；二是用并行化來加快遺傳算法的求解。
　　 首先，針對遺傳算法初始化種群中染色體多樣性不足的缺點，給出了一種改進的生成樹算法來初始化種群，該方法擴展了生成樹算法的延伸方向，使得更多的路徑被搜索到；并且針對算法交叉率變異率不具有適應性的缺點，給出了一種

3、改進適應公式，它可以根據(jù)迭代次數(shù)和適應度值的變化而改變。實驗證明，改進算法比基本遺傳算法空間搜索能力更好，用以解決QoS組播問題得到的解更優(yōu)，速度更快。
　　 其次，針對傳統(tǒng)并行遺傳算法通信時間較長的問題，給出一種改進并行遺傳算法模型。在該模型中，主處理器只需要向各個從處理器傳遞網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖和算法終止信息，并接收從處理器發(fā)送的較優(yōu)解，因此主、從處理器通信的頻率較低，這樣可以有效的減少算法單次迭代的通信時間，從而確保算法的收斂性