一種改進(jìn)型蟻群算法在組合優(yōu)化問題中的應(yīng)用.pdf

1、在計(jì)算機(jī)網(wǎng)絡(luò)中，隨著大量新興多媒體實(shí)時(shí)業(yè)務(wù)的應(yīng)用，以及Internet上商業(yè)化應(yīng)用的飛速發(fā)展，網(wǎng)絡(luò)對(duì)QoS(QualityofService，服務(wù)質(zhì)量)需求增長，高效的QoS支持變得越來越重要。而路由機(jī)制是實(shí)現(xiàn)QoS保證的關(guān)鍵之一，應(yīng)將路由選擇和QoS相關(guān)聯(lián)。在多媒體通信等高速包交換計(jì)算機(jī)網(wǎng)絡(luò)中，具有端到端時(shí)延及時(shí)延抖動(dòng)限制的QoS組播路由問題屬于組合優(yōu)化問題，如何保證服務(wù)質(zhì)量要求以及實(shí)現(xiàn)多媒體數(shù)據(jù)的組播通信是多媒體通信發(fā)展的方向。

2、 目前組播路由算法的研究大多都針對(duì)無約束組播路由問題和時(shí)延受限組播路由問題，多采用啟發(fā)式等方法。本論文研究如何將蟻群算法這一新型優(yōu)化算法應(yīng)用到時(shí)延受限QoS組播路由問題中。利用該算法的并行搜索特點(diǎn)，為解決QoS組播路由問題尋找新的途徑。本文主要研究工作如下： 首先對(duì)計(jì)算機(jī)網(wǎng)絡(luò)的組播通信進(jìn)行了綜述。主要介紹組播引入的背景、特點(diǎn)、組播技術(shù)，還敘述了QoS的相關(guān)內(nèi)容、研究現(xiàn)狀、組播路由協(xié)議和應(yīng)用。 然后展開了對(duì)蟻群算法的基

3、本原理和模型實(shí)現(xiàn)的介紹，并闡述了蟻群算法的特點(diǎn)等。在此基礎(chǔ)上研究了如何將蟻群算法應(yīng)用于QoS組播路由問題中。端到端的延遲和延遲抖動(dòng)是兩個(gè)較關(guān)鍵的性能參數(shù)。改進(jìn)了原算法的路徑選擇策略并優(yōu)化信息素更新公式。仿真結(jié)果表明本文的改進(jìn)蟻群算法比基本蟻群算法尋找最優(yōu)解的能力大大提高。 對(duì)蟻群算法進(jìn)行了進(jìn)一步的理論研究。通過實(shí)驗(yàn)分析了算法中幾個(gè)關(guān)鍵參數(shù)的選擇。并且針對(duì)基本蟻群算法的主要缺陷，如收斂速度慢和易于陷入局部最優(yōu)等問題，系統(tǒng)地介紹了用

4、于求解組合優(yōu)化問題的幾種改進(jìn)蟻群算法。 蟻群算法在組合優(yōu)化領(lǐng)域代表問題TSP(TravelingSalesmanProblem，旅行推銷商問題)中的應(yīng)用，其收斂速度一直是人們關(guān)心的問題。針對(duì)蟻群算法的一些不足，論文提出基于最小生成樹的進(jìn)化型蟻群算法。它利用了最小生成樹與最優(yōu)路徑之間的關(guān)系限制了螞蟻在每一個(gè)城市的搜尋范圍，進(jìn)化了尋優(yōu)策略，節(jié)省了在不可能構(gòu)成最優(yōu)路徑的路段上的計(jì)算時(shí)間，提高了運(yùn)算速度，克服了傳統(tǒng)蟻群算法的計(jì)算時(shí)間長、