基於鄰域免疫克隆選擇的多智能體組播路由方法
2023-08-06 11:09:16
專利名稱：基於鄰域免疫克隆選擇的多智能體組播路由方法
技術領域：
本發明屬於網絡通信技術領域，涉及多智能體技術在組播路由問題中的應用，用於求解服務質量(Q0Q組播路由問題，通過該方法獲得的較優組播樹，更加合理的配置網絡資源。
背景技術：
隨著計算機網絡飛速發展，網絡功能日益強大。網絡的作用從簡單信息傳送發展到遠程教學、視頻會議、數據分發和網路遊戲等，用戶的數據要從一個終端發送到另一個終端，首先要確定傳輸路由，不同的通信方式，其確定路由的方式也不同。如今網絡的通信方式主要有以下幾種1)點到點的單播通信方式；2)由一個源節點向多個目標節點發送信息的組播通信方式；3)由多點到一點發送信息的匯播通信方式；4)由多點到多點發送信息的群播通信方式；5)由源節點到所有節點發送信息的廣播通信方式。實時多媒體通信需求的增長，使得滿足服務質量Qos約束的組播路由方法成為當前研究的熱點，QoS約束主要包括時延、費用、帶寬、跳數等。組播問題的關鍵在於建立以根為源節點，覆蓋所有目的節點，且滿足約束要求的多播樹，使信息以並行方式沿著樹枝發送到不同的組播成員，降低信息傳遞的時延，節省網絡帶寬資源，減少擁塞。由於QoS組播路由問題的複雜性，引入人工智慧方法是很合理的。多智能體系統是近二十年來蓬勃興起的嶄新計算機學科，儘管這是個相對年輕的領域，但憑藉其強勁的發展勢頭，已經成為了目前計算機科學發展最快的領域之一。多智能體系統是一種分布式自主系統，其研究的目標是將大的、複雜的系統改造成小的、協調的、 易於管理的且能夠彼此相互通訊的系統。免疫系統的克隆選擇學說是免疫學中佔主導地位的學說，克隆選擇學說的提出不僅是免疫學發展的裡程碑，而且給人工免疫系統領域的研究者以很大的啟發，從而使人工智慧領域出現了基於抗體種群進化的克隆選擇算法。相關研究已經表明，基於QoS約束的最小代價組播路由問題是NP-complete問題， 將免疫克隆策略和多智能體系統思想相結合以解決QoS組播路由問題，國內外學者提出了很多不同的方法，但均存在不同的問題。鍾偉才在《組合優化多智能體進化算法》中提出了搜索空間動態擴展的多智能體進化方法，該方法通過設計智能體的鄰域競爭行為和自組織臨界行為以實現全局優化的目的，該方法只適合特定的網絡，常限於局部最優，很難得到代價最小的組播樹，而且該方法很難並行實現。劉淵等人在《基於免疫克隆計算的Multi_ Agent組播路由算法》中提出MAICSA方法，該方法首先構建一網絡模型以尋找一條滿足各種QoS要求的最優傳輸路徑，它將單個智能體作為網絡模型的節點，而每代產生的智能體在網格中的位置不固定，需要很高的迭代次數才能獲得代價最小的組播樹，不能很好滿足決策者合理配置網絡資源的要求。
發明內容
本發明的目的在於克服上述已有技術的不足，提出一種基於鄰域免疫克隆選擇的多智能體組播路由方法，將智能體網格結構引入抗體種群之中，並賦予抗體感知和反作用於周圍環境的智能特性，以更小迭代次數獲得更優的組播樹，滿足決策者合理配置網絡資源的要求。本發明的技術方案是將杜海峰等人提出的免疫克隆策略和多智能體系統思想相結合，在智能體鄰域競爭前先對其鄰域個體進行免疫克隆操作，並針對使用的編碼方案，設計動態疫苗提取策略，具體實現步驟如下(1)在網絡平面上產生給定規模的矩形網格，隨機產生一些網絡節點，並使網絡節點分布在矩形網格上，對這些網絡節按點鏈路概率公式樹《力=進行連接，形
aL
成組播路由的網絡模型，式中d(u，ν)表示節點u到節點ν的歐式距離，L是任意兩節點間的最大距離，α 表示網絡中最短邊與最長邊長度之比，β為控制網絡所有節點平均度數的參數，它的值為網絡所有節點平均度數的0. 1倍，α取值為0. 26, β取值為0. 4 ；(2)對已建立的智能網格，隨機指定一點作為信源節點S，並隨機產生目標節點， 將對組播路由問題的求解轉化為求從信源節點出發，覆蓋所有目標節點的最優組播樹，並初始化抗體種群P以及記憶單元種群Μ,給定變異概率Pm = 0. 6，種群規模S = 16，抗體種群克隆規模Nc = 6，記憶單元規模m' = 4，設定種群進化的終止條件為最優抗體種群連續 20次不變或種群迭代次數達到上限100，令進化代數k = 1，(3)計算抗體種群P中的抗體Pi的親合度/(A) = ~^，並選擇到達每個目
COSt(P1)
標節點的最優路徑作為疫苗，其中COSt(Pi)為抗體Pi所代表組播樹的代價；(4)根據步驟( 所設定的終止條件，判斷種群迭代是否達到終止條件，若是則輸出當前記憶單元中的最優組播樹以及到達每個目標節點的最優路徑；否則轉步驟(5)；
ICP1, CP2,
(5)對當前種群P中所有個體執行免疫克隆操作
(5a)對當前種群P中的個體Pi按其親和度的大小進行克隆，產生克隆種群CP = …，CPJ，對個體Pi克隆qi個個體，qi的計算公式如下
權利要求
1. 一種基於鄰域免疫克隆選擇的多智能體組播路由方法，包括如下步驟(1)在網絡平面上產生給定規模的矩形網格，隨機產生一些網絡節點，並使網絡節點分布在矩形網格上，對這些網絡節按點鏈路概率公式=進行連接，形成組aL播路由的網絡模型，式中d(u，ν)表示節點u到節點ν的歐式距離，L是任意兩節點間的最大距離，α表示網絡中最短邊與最長邊長度之比，β為控制網絡所有節點平均度數的參數，它的值為網絡所有節點平均度數的0. 1倍，α取值為0. 26, β取值為0. 4 ；(2)對已建立的智能網格，隨機指定一點作為信源節點s，並隨機產生目標節點，將對組播路由問題的求解轉化為求從信源節點出發，覆蓋所有目標節點的最優組播樹，並初始化抗體種群P以及記憶單元種群Μ,給定變異概率Rn = 0. 6，種群規模S = 16，抗體種群克隆規模Nc = 6，記憶單元規模m' = 4，設定種群進化的終止條件為最優抗體種群連續20次不變或種群迭代次數達到上限100，令進化代數k = 1，(3)計算抗體種群P中的抗體Pi的親合度=，並選擇到達每個目標節點的最優路徑作為疫苗，其中Cost(Pi)為抗體Pi所代表組播樹的代價；(4)根據步驟( 所設定的終止條件，判斷種群迭代是否達到終止條件，若是則輸出當前記憶單元中的最優組播樹以及到達每個目標節點的最優路徑；否則轉步驟(5)；(5)對當前種群P中所有個體執行免疫克隆操作(5a)對當前種群P中的個體Pi按其親和度的大小進行克隆，產生克隆種群CP= ICP1, ，CPJ，對個體Pi克隆qi個個體，qi的計算公式如下CP,qi = IntNc · κρηΣ f(Pj)(i = 1，2…，η)其中Nc是整個抗體種群所克隆的個體數目總和，f(Pi)為抗體Pi的親和度；(5b)對克隆種群CP執行免疫基因操作，得到免疫基因後的種群CP' =ICP1'， CP2'，…，CPn' }；(5c)對免疫基因後的種群CP'執行克隆選擇操作，得到克隆選擇後的種群P'；(6)對克隆選擇後的種群P'執行鄰域競爭操作，得到鄰域競爭後的種群P"；(7)將鄰域競爭後種群P"中的個體按組播樹代價從小到大進行排序，選出前m'個體更新記憶單元，並找出記憶單元中最優個體，即代價最小的組播樹，用P"更新當前種群P， k = k+Ι，返回步驟0)。
2.根據權利要求1所述的基於鄰域免疫克隆選擇的多智能體組播路由方法，其中步驟 (5b)所述的對克隆種群CP執行免疫基因操作，按以下步驟執行Oa)對克隆種群CP中的所有抗體進行疫苗接種，得到疫苗接種後的種群C' ={C' 1； C' 2，...，C' i，...，C' J, C' i表示對CPi中抗體進行疫苗接種後的抗體種群，其中i = 1，2，· · ·，η ；(2b)疫苗接種後的種群C'中包含Nc可組播樹，每顆組播樹包含m個目標節點，每個目標節點對應一條路徑，對所述種群C'中的抗體執行如下啟發式單點變異，得到變異後的種群 CP' ={CP' 1 CP' 2，...，CP' i，...，CP' J, CP' i 表示對 C' 抗體執行啟發式單點變異後的抗體種群，其中i = 1，2，. . .，n，首先，求疫苗接種後的種群C'中Nc顆組播樹的公共路徑，得到k個目標節點對應的k 條的路徑集合 RS = C' ！ I C' 2 I... I C' n；接著，令餘下不存在公共路徑的s = m-k個目標節點所對應的的路徑都為空； 最後，以概率Rn選擇Nc顆組播樹中的一顆，對選中的組播樹，隨機選擇上步所述s條路徑中的一條，假設該條路徑所對應的目標節點為d，則從目標節點d的備選路徑中隨機選擇一條替換該路徑。
3.根據權利要求1所述的基於鄰域免疫克隆選擇的多智能體組播路由方法，其中步驟 (6)所述的對抗體種群P執行鄰域競爭操作，按以下步驟執行(6a)將P中的抗體Pij = (adl, ad2, ... , adk, . . . , Bdm)放到智能矩形網格坐標值為(i， j)的格點上，P。.表示一顆組播樹，其中k= l，2，...，m，m為組播樹ρ。.中目標節點的個數， adk為組播樹Pu中第k條路徑的代價；(6b)求得矩形網格中組播樹Pij周圍格點上代價最小的組播樹Hiinij — (tdl，td2，· · ·，tdk，· · ·，tdm)，其中k= 1，2，...，m，m為組播樹Hiinij中目標節點的個數，tdk為組播樹Hiinij中第k 條路徑的代價；(6c)將組播樹中m條路徑的代價和作為組播樹的代價，若組播樹的代價小於組播樹minu的代價，則為競爭的勝者，它將繼續存活在其格點上，否則其空出的格點位置由組播樹Hiinij按照概率I^s生成一顆新的組播樹Wij = (gdl，gd2，. . . gdk，. . . , gdffl)取代組播樹PU，Ps的計算公式如下
全文摘要
本發明公開了一種基於鄰域免疫克隆選擇的多智能體組播路由方法，主要解決現有方法在求解組播路由問題時收斂速度慢及搜索性差的缺點，其實現步驟為1、生成網絡模型；2、初始化抗體種群、記憶單元種群以及優化的運行參數；3、計算所有抗體的親合度，找出最優抗體並提取疫苗；4、判斷是否滿足終止條件，如果滿足結束條件則輸出最優個體，否則轉第5步；5、對當前種群中所有個體執行免疫克隆操作6、對第5步得到的種群執行智能體鄰域競爭操作，並更新當前種群；7、從第6步中得到的抗體種群中提取較優的抗體更新記憶單元，並找出最優個體，返回第4步。本發明具有的收斂速度快以及搜索能力強的優點，可用來求解時延受限的組播路由問題。
文檔編號H04L12/56GK102158413SQ201110088399
公開日2011年8月17日 申請日期2011年4月11日 優先權日2011年4月11日
發明者於昕, 劉芳, 劉靜樂, 孫暉, 尚榮華, 戚玉濤, 李陽陽, 焦李成, 郝紅俠, 馬文萍, 馬晶晶 申請人:西安電子科技大學