【文章內(nèi)容簡介】 3。 dm pn1 pn2 pnm表1中的n為某個節(jié)點可以選擇的目的節(jié)點數(shù)，m為該節(jié)點的相鄰節(jié)點數(shù)?！靶虐乇怼苯o出了以某個節(jié)點為目的節(jié)點時選擇下一節(jié)點的概率，同時表1中的概率值按照某種規(guī)則周期性地刷新：下面的公式給出了在節(jié)點u中的螞蟻k選擇到相鄰節(jié)點v的概率： (21)其中為鏈路上的“信息素”；為與節(jié)點 直接相連的所有節(jié)點的集合； = ，其中為鏈路的傳輸代價可能是鏈路的距離或鏈路的傳輸成本等；為鏈路上的剩余帶寬；和是決定時延和剩余帶寬相對重要的參數(shù)。從公式我們看出，螞蟻更有可能選擇時延小、可利用帶寬大、信息素強度較強的鏈路。螞蟻開始搜索的初始時刻，各條路徑上分布的信息量相等，即(C為常數(shù))。螞蟻在運動過程中，根據(jù)各條路徑上的信息量決定轉(zhuǎn)移方向，時刻位于某一城市的螞蟻一次只能選擇其中一個目標城市，次后回到起點，完成一次循環(huán)。那么，時刻位于城市的螞蟻選擇城市為目標城市的概率是： (22)其中，表示螞蟻下一步允許選擇的城市。與實際蟻群不同，人工蟻群系統(tǒng)具有記憶功能，用以記錄螞蟻當前所走過的城市，集合隨著進化過程作動態(tài)調(diào)整。隨著時間的推移，以前留下的信息漸漸消失，經(jīng)過個時刻，螞蟻完成一個循環(huán)，各路徑上的信息量要根據(jù)如下做調(diào)整: (23) (24)公式(23)和(24)中表示在時刻和之間第k只螞蟻在路徑上留下的信息素量，表示在時刻和之間路徑上信息素增量，其中是一個參數(shù)，表示殘留信息的持久程度 ，1表示在時刻和+之間信息素消逝程度。當所有螞蟻完成各自路徑的選擇過程，必須對各邊上的信息素按公式(23)作一次全局更新，此時根據(jù)具體算法的不同，，表達形式可以不同，要根據(jù)具體問題而定。 system(蟻周)；antquantity system（蟻量）和antdensity system（蟻密度）在antcycle system模型中： (25)公式(25)中是常數(shù)，為螞蟻循環(huán)一周時釋放在所經(jīng)過路徑上的信息素總量，即總信息量；表示第只螞蟻在本次循環(huán)中所走路徑的長度。初始時刻。在antquantity system模型中： (26)在antdensity system模型中： (27)由公式(25)、((26)、(27)可知，它們的差別在于的不同。，可見antcycle system模型性能較好。 蟻群算法的實現(xiàn)從以上蟻群算法的模型可知，算法的尋優(yōu)過程是一個遞推迭代過程，Antcycle system程序的偽代碼其實現(xiàn)步驟如下(設(shè)NCMAX是定義好的循環(huán)次數(shù))： (1) 初始化:Set ， NC=0，每條邊上的并且隨機放置個螞蟻到個城市上；(2) 令 (s是tabu list的下標)：For k=1 to m do把第k個螞蟻的初始城市號碼放置；(3) 重復(fù)本步驟直到tabu list被填滿(這個步驟重復(fù)n1次)：Set s=s+1 For k=1 to m do，根據(jù)概率式(22)來選擇下一步應(yīng)該到達的城j在時刻，螞蟻k在城市，將第k個螞蟻移到城市j，并將j插入到中；(4) For k=1 to m do，將第k個螞蟻從城市移到，計算第k只螞蟻的總路徑長度，更新找到的最短路徑。For to m do根據(jù)式(24)、(25)，更新邊上的信息素濃度；(5) 根據(jù)式(23)，對每一條邊計算Set Set set (6) 如果并且(不是所有的螞蟻選擇同一條路徑)那么；清空所有的tabu list；轉(zhuǎn)到第(2)步；否則；初始化，設(shè)置時間計數(shù)器，循環(huán)計數(shù)器，每條邊信息素濃度初值，將m只螞蟻隨機放到n個城市 初始化tabu列表，將所有螞蟻的初始城市放置到tabu列表中Tab列表滿？ Y計算機轉(zhuǎn)移概率p，按概率將每只螞蟻從第i個城市移到第j個，寧見j插入tabu列表中 N封閉回路，分別計算每只螞蟻走過的總長度，記錄最短路徑，計算信息素濃度該變量達到最大環(huán)次數(shù)求解度 N Y 顯示并打印最短路徑圖 23 蟻群算法流程圖打印出最短路徑，終止整個程序。由于算法的第一步的復(fù)雜度為，第二步的復(fù)雜度為，第三步的復(fù)雜度為，第四步的復(fù)雜度為，第五步的復(fù)雜度為，第六步的復(fù)雜度為，所以如果程序終止于次循環(huán)后，算法的復(fù)雜度就為。當城市個數(shù)n和螞蟻個數(shù)m成線性關(guān)系時，這個算法的復(fù)雜度為。蟻群算法的流程圖如圖23所示。 蟻群算法迭代過程以下圖為例說明蟻群算法的迭代運算過程。AO、Al代表兩只螞蟻，VO、Vl為兩個節(jié)點，它們之間存在兩條路徑Upper和Down，且Upper的距離為2，Down的距離為1。假設(shè)初始時刻每條路徑均有相同的概率()被選擇，信息素初值，。兩只螞蟻從V0開始尋找最短路徑。 Upper Upper障礙物 A0 A0V1V1V0V0障礙物 A1 A1 Down Down 圖 24 蟻群算法迭代圖初始時，A0走Upper路徑，Al走Down路徑，各自釋放在路徑上的信息素為:,。當A0、Al到達V1后，各條路徑上實際有的信息素為:當螞蟻重回起點V0進行路徑選擇時，根據(jù)概率選擇公式有: 由于，因此，兩只螞蟻都將選擇路徑Down。此路徑即為到達V1的最短路徑。 無線網(wǎng)絡(luò)蟻群算法路由技術(shù)分析針對可擴展性提出的策略，很多相應(yīng)算法應(yīng)運而生，這些算法面臨的最大問題是網(wǎng)絡(luò)的不確定性，換言之，就是隨機性。在隨機搜索方面，蟻群算法是一種行之有效的算法。它具有如下優(yōu)點：(1)蟻群算法是一種分布式的本質(zhì)并行算法。單個螞蟻的搜索過程是彼此獨立的，容易陷入局部最優(yōu)。但通過個體之間不斷的信息交流和傳遞有利于發(fā)現(xiàn)較好解。(2)蟻群算法是一種正反饋算法。路徑上的信息素水平較高，將吸引更多的螞蟻沿這條路徑，這又使得其信息素水平增加，這樣就加快了算法的進化過程。(3)群算法具有較強的魯棒性。只要對其模型稍加修改，便可以應(yīng)用于其它問題。(4)易于與其它方法結(jié)合。蟻群算法很容易與其它啟發(fā)式算法相結(jié)合，以改善算法的性能。將蟻群算法應(yīng)用在網(wǎng)絡(luò)路由上，算法中的每只螞蟻，根據(jù)它在網(wǎng)絡(luò)上的經(jīng)驗與性能，動態(tài)更新路由表項。如果一只螞蟻因為它經(jīng)過了網(wǎng)絡(luò)中堵塞的路段而導(dǎo)致了比較大的延遲，那么就對相應(yīng)的表項做較小的增強，如果某條路段比較順利，那么就對該表項做較大的增強。同時應(yīng)用揮發(fā)機制，就可以做到系統(tǒng)信息的更新，從而使得那些過期的路由信息不再保留。這樣，在當前最優(yōu)路徑出現(xiàn)阻塞時，算法能很快找到另一條可替代的較優(yōu)路徑，從而提高網(wǎng)絡(luò)的均衡性、網(wǎng)絡(luò)負載量以及網(wǎng)絡(luò)的利用率。 簡單相關(guān)路徑Zigbee路由算法概述 簡單相關(guān)多路Zigbee路由算法的基本思想就是所建立的所有替換路徑都靠近主路徑，更進一步講就是替換路徑上的節(jié)點要么就是主路徑上的節(jié)點，要么是主路徑上節(jié)點的鄰節(jié)點。其基本原理可歸納如下。源節(jié)點泛洪Zigbee路由請求報文RREQ。收到RREQ的節(jié)點在確認本節(jié)點既不是目的節(jié)點，又沒有發(fā)送過該RREQ的條件下，計算本節(jié)點與發(fā)送給它RREQ的上游節(jié)點鏈路之間的代價，將其寫入RREQ的Cost域后轉(zhuǎn)發(fā)此RREQ。目的節(jié)點根據(jù)規(guī)定時間內(nèi)接收到的所有RREQ報文提取出網(wǎng)絡(luò)拓撲信息，構(gòu)建簡單相關(guān)多路徑Zigbee路由。由上述原理可知，現(xiàn)有簡單相關(guān)多路徑算法采用洪泛方式建立Zigbee路由，所以存在以下問題：(1) 建立Zigbee路由需要的時間長，且易產(chǎn)生泛洪，從而導(dǎo)致?lián)砣漠a(chǎn)生。(2) 簡單相關(guān)多路徑的多條路徑是從目的節(jié)點在規(guī)定時間內(nèi)接受到的多條Zigbee路由內(nèi)產(chǎn)生的，在這段時間內(nèi)不一定能尋到最優(yōu)路徑。 (3) 算法沒有規(guī)定在特定網(wǎng)絡(luò)約束條件下對Zigbee路由進行優(yōu)化的機制。 路由維護與信息素更改每個從源節(jié)點 向目的節(jié)點 傳輸?shù)臄?shù)據(jù)包，相當于一個路徑增強螞蟻。路徑的增強通過螞蟻施放信息素的機制實現(xiàn)，即在數(shù)據(jù)傳輸?shù)倪^程中通過對所經(jīng)過節(jié)點的信息素的修改來實現(xiàn)。優(yōu)化路徑在這個過程中會自動出現(xiàn)。螞蟻的自動尋優(yōu)機制會保證在數(shù)據(jù)傳輸時自動選擇優(yōu)化路徑。和真實蟻群一樣，所建立的信息素濃度，并不是永久不變的。信息素濃度的變化通過兩種機制實現(xiàn)，信息素增強和信息素蒸發(fā)。(1) 信息素增強．當從節(jié)點 轉(zhuǎn)發(fā)數(shù)據(jù)到鄰居節(jié)點 時，從到的路徑被加強， 路由表中相應(yīng)的按式增加，從而實現(xiàn)優(yōu)勢路徑增強；(2) 信息素蒸發(fā)，為了避免統(tǒng)治地位路徑的產(chǎn)生而使某些節(jié)點的能量消耗過快，網(wǎng)絡(luò)中所有單跳路徑的信息素濃度按式增加；(3) 進行周期性蒸發(fā)，以減小過去的信息素的影響，促進新路徑的使用。網(wǎng)絡(luò)中的各節(jié)點實時檢測自己的剩余能量，并將剩余能量通知鄰居節(jié)點。我們采用閾值觸發(fā)方式啟動能量通知過程，即當能量降低超過一定量，或降低到一定值時，啟動通知機制通知鄰居節(jié)點。具體的通知機制類似于網(wǎng)絡(luò)初始化時的做法：欲發(fā)出能量通知的節(jié)點以一個一跳的消息，將它的剩余能量發(fā)給鄰居節(jié)點，各鄰居節(jié)點根據(jù)收到的能量值更新本地路由表中該節(jié)點對應(yīng)的剩余能量值，從而降低該節(jié)點被選中的概率，減少該節(jié)點的能量消耗。通過這種方式，能較好地達到均衡使用能量的效果。 基于蟻群算法的Zigbee路由研究與改進蟻群算法是最新發(fā)展的一種模擬昆蟲王國中螞蟻群體智能行為的仿生優(yōu)化算法。它具有較強的魯棒性，優(yōu)良的分布計算機制，易于與其他方法相結(jié)合等優(yōu)點，其思想來源于自然界中蟻群尋找食物過程的觀察。在覓食過程中,螞蟻在它所經(jīng)過的路徑上會釋放出與路徑長度有關(guān)的信息素, 路徑越長，釋放的信息量越小。后來的螞蟻能感知信息素的存在及其濃度，以此指導(dǎo)自己的運動方向，并傾向于朝著信息素濃度高的方向移動。于是，螞蟻的集體行為便表現(xiàn)出一種信息正反饋傾向。 蟻群算法中信息素的更新原則當信息包在路徑上傳輸時，信息素的值會發(fā)生變化。如有信息包經(jīng)過，路徑上信息素的值就會增加，而沒有信息包經(jīng)過的路徑的信息素會揮發(fā)。的值由式(24)進行更新。 (28)其中：是信息素揮發(fā)因子；為在鏈路上增加的信息素值，Q為常數(shù)，表示剩余能量，為初始能量。剩余能量越低，則增加的信息素就越少，選擇此路徑的可能性就會降低，從而達到繞開節(jié)點能量低的節(jié)點，使得網(wǎng)絡(luò)中節(jié)點能量消耗均衡。是信息素保持率，而表示衰減率。參數(shù)p始終小于1的意義在于，每一個周期后，所有邊上的信息素必須衰減，不能無限制積累，這樣可義在于，每一個周期后，所有邊上的信息素必須衰減，不能無限制積累，這樣可以讓系統(tǒng)“遺忘比較差的路徑，增加后繼搜索的發(fā)散性。顯然衰減是以指數(shù)級速度進行的。 本章小結(jié)本章詳細描述了第一個ACO算法一螞蟻系統(tǒng)的現(xiàn)實原理和算法模型及描述，螞蟻系統(tǒng)為闡明ACO元啟發(fā)式算法的基本思想做了最好的解釋。有了螞蟻系統(tǒng)的基本原理做鋪墊，融合元啟發(fā)式算法的特點，就可以提出ACO的元啟發(fā)式框架，通過對組合優(yōu)化問題的算法關(guān)聯(lián)定義，ACO元啟發(fā)式就順其自然的有了基本的構(gòu)件組成和運行模式。在這個框架下，螞蟻系統(tǒng)是作為算法的一個實例，并可以衍生出其他算法，盡管其他衍生算法是單獨提出，但是ACO元啟發(fā)式框架是對它們的最好概括。接著講述了幾種典型的ACO算法變種，這些都比原始的蟻群系統(tǒng)的性能有了大幅度提升。第3章 無線網(wǎng)絡(luò)蟻群優(yōu)化算法路由技術(shù)蟻群優(yōu)化ACO算法是一門發(fā)展中的學科的一個組成部分。 蟻群優(yōu)化算法基本原理 蟻群優(yōu)化算法基本概念蟻群優(yōu)化算法是Marco Dorigo等學者受螞蟻覓食行為啟發(fā)提出的一種啟發(fā)式算法。在覓食路徑選擇時，起初由于每只螞蟻僅知道局部信息，無法找到從巢穴到食源的最短路徑，但是螞蟻通過在覓食路徑釋放信息素，間接地完成了與其他螞蟻的路徑信息交換，最終整個蟻群獲得了全局最優(yōu)路徑(全局優(yōu)化結(jié)果)。蟻群優(yōu)化(ACO)的啟發(fā)式搜索方法具有較好的分布性和自適應(yīng)性，可以根據(jù)要優(yōu)化對象的特點改變優(yōu)化策略。還可以通過多條備選路徑均衡了各節(jié)點的能耗，盡可能地延長節(jié)點生命期，該算法在螞蟻數(shù)據(jù)包結(jié)構(gòu)、概率選擇公式及信息素更新公式等方面做了改進。該算法將延長網(wǎng)絡(luò)壽命，提高能量有效性。在計算機上實現(xiàn)以上模型時，一般有兩種方法：第一種是通過定義差分方程或微分方程來逐步計算構(gòu)建解，這樣可以得到系統(tǒng)的期望行為，如蒙特卡洛方法，這樣定義的模型比較有數(shù)學依據(jù)，嚴謹而又有實際意義，然而對這樣的方程計算有時也會帶來計算量大的問題；另一種是模擬再現(xiàn)螞蟻群體，即設(shè)計一種人工螞蟻(artifical ant)來模擬真實螞蟻，其通過一個分布式學習過程來自適應(yīng)地獨立并行地構(gòu)建解，然后通過對(部分)解進行評估，來修改信息素濃度(信息素的釋放和蒸發(fā))，以此對以后搜索過程實施一定的導(dǎo)相似)作用。為提高算法的性能，可以在一次迭代之后進行后臺處理，進行局部優(yōu)化和全局信息收集等集中行動。模擬仿真方法啟發(fā)我們設(shè)計一種人工螞蟻用相似的思路去解決優(yōu)化問題。 蟻群優(yōu)化算法數(shù)學模型基本的蟻群優(yōu)化算法，設(shè)是一個連通的無向圖，V是圖G中頂點的集合，E是邊的集合。；令表示邊上的信息素濃度，表示上預(yù)知的局部啟發(fā)值。局部啟發(fā)值可以是任何形式的代價，如距離、費用等。在頂點Vi的螞蟻使用信息濃度和局部啟發(fā)值來計算選擇下一個相鄰頂點,的概率: (31)其中，