【正文】 and J. M. Pasteels Unit of Behavioural Ecology, . 231, Universit6 Libre de Bruxelles, B 1050 Bruxelles 7 Fig. 1. A colony of I humilis selecting the short branches on both modules of the bridge a) one module of the bridge b) and c): photos taken 4 and 8 min after placement of the bridge 8 雙橋?qū)嶒灁?shù)學模型 ()()( ) ( )hAA hhABmkPmm k m k??? ? ?假設條件： 非對稱橋上的信息量與過去一個時間段內(nèi)經(jīng)過該橋的螞蟻數(shù)目成正比； 某一時刻螞蟻按照橋上殘留的信息量多少來選擇其中某座橋 經(jīng)過該橋的螞蟻數(shù)目越多則橋上的殘留信息量就越大 設短橋為 A，長橋為 B， mA和 mB分別表示經(jīng)過橋 A和橋 B的螞蟻數(shù)目 mA + mB = m 當所有 m只螞蟻都經(jīng)過兩座橋之后，第 m+1只螞蟻選擇橋 A的概率為： 而選擇橋 B的概率為： ( ) 1 ( )BAP m P m??9 ? 參數(shù) h 和 k用以匹配真實實驗數(shù)據(jù) ? 第 m+1只螞蟻首先計算 ? 然后生成一個在區(qū)間 [0,1]上均勻分布的隨機數(shù) ? 若 ，則選擇橋 A，否則選擇橋 B ()APm()APm???()APm? ?10 基本蟻群算法的數(shù)學模型 11 P、 NP、 NPC、 NPhard問題 ? P類問題 –所有可用 DTM (Deterministic onetape Turing Machine) 在多項式時間內(nèi)求解的判定問題 Π的集合。即螞蟻是反應型適應性主體 –在個體水平上，每只螞蟻僅根據(jù)環(huán)境做出獨立選擇；在群體水平上，單只螞蟻的行為是隨機的，但蟻群可通過自組織過程形成高度有序的群體行為。在 t時刻螞蟻 k由元素（城市） i轉移到元素（城市） j的狀態(tài)轉移概率： [ ( ) ] [ ( ) ], i f [ ( ) ] [ ( ) ]( ) ( 1 )0 el sewi sekij ikkkis isijs a ll o w e dttj a l l o w e dttpt?????????? ???? ?? ?????20 ? 其中 allowedk={Ctabuk}表示螞蟻 k下一步允許選擇的城市；α為信息啟發(fā)式因子，表示軌跡的相對重要性，反映了螞蟻在運動過程中積累的信息在螞蟻運動時所起的作用，其值越大，則該螞蟻越傾向于選擇其它螞蟻經(jīng)過的路徑，螞蟻之間的協(xié)作性越強； β為期望啟發(fā)式因子，表示能見度的相對重要性，反映螞蟻在運動過程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度，其值越大，則該狀態(tài)狀態(tài)轉移概率越接近于貪心規(guī)則； ? ηij(t)為啟發(fā)函數(shù)， ηij(t) =1/dij ? 式中 dij表示相鄰兩個城市之間的距離。 , ( , )( ) ( 4 )k kijQk i jLt????? ???若 第 只 螞 蟻 在 本 次 循 環(huán) 中 經(jīng) 過0, 否 則24 ? AntQuantity模型 , 1 ( , )( ) ( 5 )k ijijQk t t i jdt?????? ???若 第 只 螞 蟻 在 和 之 間 經(jīng) 過0, 否 則25 ? AntDensity模型 ? 區(qū)別： – 式 (5)和式 (6)中利用的是局部信息，即螞蟻完成一步后更新路徑上的信息素；而式 (4)中利用的是整體信息，即螞蟻完成一個循環(huán)后更新所有路徑上的信息素，在求解 TSP時性能較好，因此通常采用式 (4)作為蟻群算法的基本模型。 (8)根據(jù)公式 (2)和式 (3)更新每條路徑上的信息量。 33 QoS網(wǎng)絡路由 ? 網(wǎng)絡路由方面的研究主要通過兩個途徑來提高服務質(zhì)量 (QoS）：一條途徑是節(jié)點控制；另一條途徑是整網(wǎng)或局部網(wǎng)絡控制。 ? 平面 QoS路由 –所有路由器都在同一級內(nèi)， –以前對 QoS路由的研究大多采用平面網(wǎng)絡， ? 分級 QoS路由 –基本思想：將路由器分成多個邏輯組，每個組又可包含更小的組。 ? where, 0α0 1, cons is a constant. Adjusting the amount of pheromone by the rule can make the desirability of edges change dynamically. In this way, ants will make a better use of pheromone information。 50 平面 QoS螞蟻路由算法具體步驟 (2) ? (4)從蟻巢開始放出 m只螞蟻去尋找食物源，在第一個時間單位，每只螞蟻從節(jié)點集合中隨機地選擇一個節(jié)點，然后各螞蟻通過重復應用狀態(tài)轉移規(guī)則來選擇各自的路徑。 ? 在大多數(shù)應用中，時延要求是最為重要的，為了方便起見，這里在研究 QoS路由時僅考慮時延限制。 59 211112111111 , 0()0 L A NNNdij ijijjiNNdij ijijjiFFFF L C Pi f ZF H Zothe rw i seZ L D P??????????????? ? ??????其 中 表 示 內(nèi) 節(jié) 點 的 端 到 端 時 延 限 制60 參考文獻 ? Zhang S B, Liu Z M. A QoS routing algorithm based on ant