【正文】 機(jī)制搜索食物 ,并最終沿著最短路徑行進(jìn) ,如圖 。因此當(dāng) 30只螞蟻分 別回到 B、 C點(diǎn)重新選擇路徑時(shí)就會(huì)以 2倍于 B一 F一 C的概率選擇路徑 B一 E一 C,從 而 B一 F一 C上的螞蟻數(shù)目變成 10只 ,是 B一 E一 C上螞蟻數(shù)目的一半 ,如圖 (c)所 示 ,距離較短的路徑上信息素很快得到強(qiáng)化 ,其優(yōu)勢(shì)很快被蟻群所發(fā)現(xiàn)。因此在決定螞蟻行走方向的狀態(tài) 轉(zhuǎn)移概率時(shí) ,引入一個(gè)隨機(jī)搜索過(guò)程 ,即引入啟發(fā)因子 ,根據(jù)所求問(wèn)題空間的具 體特征 ,給蟻群算法一個(gè)初始引導(dǎo) ,這個(gè)過(guò)程極大地加快了算法的時(shí)間有效性。 n 設(shè)互 (t)(i二 `,2,一” )是 t時(shí)刻節(jié)點(diǎn) `的螞蟻數(shù) ,則 m。第 m+1只螞蟻按概率選擇不同的橋。由于蟻群算法只是對(duì)螞蟻覓食行為的一種 模擬 ,沒(méi)有必 要對(duì)螞蟻個(gè)體進(jìn)行完全再現(xiàn) ,摒棄與算法無(wú)關(guān)的因素 ,這樣抽象出來(lái)的人工螞蟻 可以看作一個(gè)簡(jiǎn)單的智能體 ,能夠構(gòu)造所求問(wèn)題的解 ,也能通過(guò)一種信息手段相 互影不 !l句。 (3)完成一次遍歷后 ,螞蟻在其訪問(wèn)過(guò)的每一條邊上留下相應(yīng)的信息素。刀為期望啟發(fā)式因子 ,表示能見(jiàn)度的相 對(duì)重要性 ,反映了螞蟻在運(yùn)動(dòng)過(guò)程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度 , 其值越大 ,則該狀態(tài)轉(zhuǎn)移概率越接近于貪心規(guī)則 。)上的信息素可按如下規(guī)則進(jìn)行 調(diào)整 : {T。 在 Ant一 Cycte模型中 若第 k只螞蟻在本次循環(huán)中經(jīng)過(guò) (i,j) 否則 () 一 O乓 Q月 l了、 .t、一一、 ,產(chǎn)襯夕■ 在 Ant一 Quantity模型中 若第 k只螞蟻在 t和 t+l之間經(jīng)過(guò) (i,力 否則 () 一 Qz,0,/`l、 to、 一一 、少 .乙矛 .了、襯夕 A 在 Ant一 Density模型中 若第 k只螞蟻在 t和 t+l之間經(jīng) 過(guò) (i,j39。 設(shè) n為蟻群算法中圖節(jié)點(diǎn)數(shù) ,m。 步驟 6ifNc小于入七用 ax且未進(jìn)入停滯狀態(tài) ,then 1)清空所有螞蟻禁忌表中的數(shù)據(jù) 。 GutjahrWJ最先從有向圖角度對(duì)一種改進(jìn)蟻群算法 — GBAS的收斂性進(jìn)行了 證明 120]。 算一法求解 O一 1背包問(wèn)題 第三章求解背包問(wèn)題的蟻群算法 蟻群算法在優(yōu)化問(wèn)題中表現(xiàn)突出 ,已經(jīng)成功地應(yīng)用于求解 TSP、二次分配、 圖著色、車輛調(diào)度、集成電路設(shè)計(jì)及通信網(wǎng)絡(luò)負(fù)載等問(wèn)題。 不同的路徑圖對(duì)應(yīng)的蟻群算法模型表示也是不同的。 二章求解背包問(wèn)題的蟻群算法 圖 問(wèn)題的構(gòu)造圖。在這里選擇經(jīng)過(guò)的邊不能與前面已經(jīng)選擇的邊相同 , 且選擇的邊必須滿足背包的約束條件。 ))) (((2)))設(shè)置螞蟻禁忌表表 O(腳 e))) (((3)))每只螞蟻單獨(dú)構(gòu)造解解 o(nZmc))) (((4)))解的評(píng)價(jià)和軌跡更新量計(jì)算算 o(nZme))) (((5)))信息素軌跡濃度更新新 o(nZ))) (((6)))判斷是否達(dá)到算法的終止條件 (達(dá)到設(shè)定的最大循環(huán)環(huán) O(nme))) 次次次數(shù) Ncm動(dòng) ,若沒(méi)有 ,轉(zhuǎn)到第 (2)步步步 (((7)))輸出計(jì)算結(jié)果果 O(l))) 當(dāng) n足夠大時(shí) ,低次冪的影響可以忽略不計(jì) ,則由表 ,蟻群算法中 m。為了保存螞蟻尋到的解 ,需要為每只螞 蟻設(shè)立一個(gè)數(shù)組 。 +b,三 c,(i=1,2,? m)其中尸。之后 ,螞蟻 k要對(duì)其經(jīng)過(guò)的路徑上的信息 素進(jìn)行更新 ,更新可以采用公式 ()()。 3)如果螞蟻 未死亡 ,則將所選擇的有向線段加人螞蟻 k的禁 忌表 tabu、 。 End 圖 MKP 算法 群算法求解 0一 l背包問(wèn)題 蟻群算法求解背包問(wèn)題的數(shù)學(xué)模型是建立 在上一節(jié)背包問(wèn)題的圖形表示基 礎(chǔ)上的 ,算法可以表述如下 : 設(shè)丁抓 t)為 t(t=o,1,2,? )時(shí)刻有向線段 ali,j]上的信息素 ,初始時(shí)刻各有向線 段上的信息素為介 (0)=const(const為較小的正常數(shù) )。 _,、 ~_,一 *.,_。由于 `目 對(duì)于每一條邊 ,m的值是固定的 ,在表達(dá)式中可以除去 ,最后可以得到枷 (t)的表 達(dá)式 : 叮。經(jīng)過(guò) 2020代搜索 ,如圖 (0所示 ,信息素濃度分布 與 400代時(shí)改變并不是很大 ,此時(shí)算法搜索已經(jīng)進(jìn)入了一種停滯的狀態(tài) ,也就是 說(shuō) ,算法己經(jīng)找到了一個(gè)比較優(yōu)的解。這種信息素?fù)]發(fā)機(jī)制避免了在一條邊上 的信息素?zé)o限積累 ,并使得極少甚至沒(méi)有獲取新信息素的邊上的信息素含量快速 減少。 圖 2020代搜。 }}}10001111122213331毛毛 己己己已已已已已 444弓弓 eee777eee```.!!!萬(wàn) llll!!!l{{{...卜卜卜卜 卜卜 ...口 111llll冬 111 口口口互 {{{毛 llllllll一一 IIIlllllllllllll匆匆 l!!!愛(ài) 1111111》》 ...1{{{繃繃 ... 1011121314rrreeeeee 廣 尸 廠 一一一一一一一一一一一一一一一一一 :::::::::::::::::::::::::::::::::::::::一一 :一一 :一一廠廠 門(mén)門(mén)廣一門(mén)門(mén)廠一勺勺廠一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一 llllll{{{{llllI111尸一 尸尸戶戶廠 ,尸尸目 llllllll一一一一 !一一 .............................lllllllll一一l一一 IIIIIII{一一三三三 !!!llllll一一 l一一 ................................................... lll!!!!!!一一 I11111獷 rwe~~~~~resesesssree一一一廠 ~一一一 lllllllll一一 l一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一 lllllllll 一一 l 門(mén)門(mén)一一仁二二 :::】一一一習(xí)一一 r 一 尸 一一 llllllllllll】 llllllllllllllr一甲甲】一一 resesesssree一一一尸 ~~lll!!!lllllllllllllllllllllllllllllllllllllllllllllllllllllllllll 、 11111111111〔二二二二二「一一一一 111 一一一一一一一一一一一一一一一一一一一一一一一 l一一 廠廠廠廠一勺勺「一一一一「 一一一一一 .一一 lllllllllll一一 l一一一 l一一 lllllllllll一一 l一一一 iii 毛毛毛毛 lll、 ttttttt .......{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{ ID11121314 圖 (a)初始時(shí)刻信息素分布 (b)搜索 100代后信息素分布 (c)搜索 200代后信息素分布 (d)搜索 300代后信息素分布 (e)搜索 400代后信息素分布溝搜索 2020代后信息素分布 從圖 ,在良好參數(shù)設(shè)置下 ,信息素可以對(duì)算法產(chǎn) 23 三章求 解背包問(wèn)題的蟻群算一法 生長(zhǎng)遠(yuǎn)影響。隨著信息素的揮發(fā) ,只有少數(shù)路徑上會(huì)保持著一定濃度的信息 素 ,這些路徑也是螞蟻經(jīng)常選擇行走的路徑 ,如圖 (d)所示。 /C 一由 `匕計(jì)““發(fā)函”“。從圖 知 ,求解背包問(wèn)題的蟻群算法有一個(gè)特點(diǎn) ,就是信息素僅和物品相關(guān) ,啟發(fā)信息 應(yīng)該偏向于那些具有高價(jià)值而需求低的物品。 4)轉(zhuǎn)至步驟 2。 , 設(shè)置時(shí)間 t=o,令圖上每條邊 (i,力的初始化信息素量幾 (t)一 const 且初始時(shí)刻 :,s(t)一 o(i,j一 1,2,? ,n) 循環(huán)次數(shù) Nc=O 步驟 2生成 mc只螞蟻 ,并將其置于節(jié)點(diǎn) 1上 步驟 3for每只螞蟻 do 1)按公式 ()()()計(jì)算轉(zhuǎn)移概率并選擇下一條有向線 段 。只螞蟻都死亡以后 ,可求得 mc組可行解。 ) 蟻群算法收斂性分析 蟻群算法是一種仿生優(yōu)化算法 ,因此它的收斂性具有十分重要的意義。 ) 由于蟻群算法通常采用有向圖來(lái)描述 ,則需要一個(gè) n階二維矩陣來(lái)表示圖上 的信息素濃度 。 群算法求解 O一 l背包問(wèn)題 為 Nc,最大循環(huán)次數(shù)為 Ncl)In,則針對(duì)前面蟻群算法程序結(jié)構(gòu)流程描述 ,可逐步 分析其時(shí)間復(fù)雜度 ,如表 。螞蟻可以且只可以經(jīng)過(guò)其中一條邊到達(dá)下一個(gè)節(jié)點(diǎn) ,每 經(jīng)一條邊就表示選擇與圖中邊編號(hào)相同編號(hào)的物品。最后一種表示方法是在文獻(xiàn)【 241中提出了圖形表示 , 采用物品作為路徑圖的路徑 ,對(duì)物品的選取表示通過(guò)物品對(duì)應(yīng)的路徑。但是 在背包問(wèn)題中沒(méi)有路徑的概念。此后段海濱等 [23l人還使用不同的工具對(duì)蟻群算法的收斂性進(jìn)行了研究。 第 _章蟻群算法 寫(xiě)算法程序具有指導(dǎo)意義。 Clldfof 步驟 4計(jì)算本次迭代的最優(yōu)解 ,如果其優(yōu)于當(dāng)前最優(yōu)解 ,則用其替換當(dāng) 前最優(yōu)解 。由此 ,可以得到蟻群算法具體實(shí)現(xiàn) : 第一章蟻群算法 開(kāi)開(kāi)始始 初初始化化 螞螞蟻始 111 螞螞蟻?zhàn)o(hù) k+lll 按按照概率轉(zhuǎn)移公式陀 .1)選擇下一個(gè)節(jié)點(diǎn)點(diǎn) 修修改禁忌表表 按按照公式陀 .住 .進(jìn)行信息素更新新 迭迭代次數(shù) Nc=Nc+111 輸輸出計(jì)算結(jié)結(jié) 結(jié)結(jié)束束 圖 從蟻群算法實(shí)現(xiàn)不難 看出 ,蟻群算法實(shí)際上是正反饋原理和啟發(fā)式算法相結(jié) 合的一種方法。 (0)=0:■弓 (t)表示第 k只螞蟻在本次循環(huán)中留在路徑 (i,j)上 的信息素。時(shí)刻在路徑 (l39。 (t)]a[飛 (t)]刀 藝 [幾 (,)一 a「 nls(`)]聲如黝。該過(guò)程由螞蟻的禁忌表來(lái)控制 ,禁忌表 tabu*(k二 1,2,? ,m?！?][39。:分別表示經(jīng)過(guò)橋 A和經(jīng)過(guò) 橋 B的螞蟻數(shù)目 (態(tài) +凡 ,=m),則當(dāng)所有 m只螞蟻都經(jīng)過(guò)兩座橋后 ,第 m+l只 螞蟻選擇 A橋的概率為 :凡 (m)(A,。個(gè)節(jié)點(diǎn)的集合 ,L一 {氣 }c,c,。 引入啟發(fā)因子。若假設(shè) 螞蟻都具有相同的速度 (1耐 s)和信息素釋放能力 ,則經(jīng)過(guò) ls 后從 B點(diǎn)出發(fā)的 30 只螞蟻有巧只到達(dá)了 F,有巧只經(jīng)過(guò) E到達(dá)了 C點(diǎn) ,同樣從 C點(diǎn)出發(fā)的 30只 螞蟻有巧只螞蟻到達(dá)了 F,有巧只經(jīng)過(guò) E到達(dá)了 C點(diǎn)。相等時(shí)間內(nèi)較 短路徑上的信息素遺留得比較多 ,則選擇較短路徑的螞蟻也隨之增多 ,如圖 所示。這種能力 來(lái)源于螞蟻群體中 的個(gè)體協(xié)作行為。采用圖形、數(shù)據(jù)等手段實(shí)現(xiàn)了本文 算法同其它算法在時(shí)間、最優(yōu)解、搜索代數(shù)等方面的比較。主要對(duì)下列幾個(gè)問(wèn)題進(jìn)行探討 : 。藝 b。 在 NP 問(wèn)題中 ,有一個(gè)子類 ,即完全 (NPComPlcte,簡(jiǎn)記為腳 C)問(wèn)題 ,指的是 那些 NP 問(wèn)題中最難的問(wèn)題 :所有其它的 NP 問(wèn)題都可以歸約到這些 NP 完全問(wèn) 題。 遺傳算法、免疫算法和蟻群算法等算法雖然可能在求解某些問(wèn)題時(shí)有計(jì)算時(shí) 間長(zhǎng) ,且容易陷入局部最優(yōu)解的缺點(diǎn) ,但是它們也有通用性強(qiáng)、容易與其它算法 相結(jié)合的優(yōu)點(diǎn)。 免疫算法 [39。 求解背包問(wèn)題的啟發(fā)式算法采用的策略很大一部分是從人類社會(huì)生活經(jīng)驗(yàn) 中借鑒的 [7]。確 定性近似算法主要有 :貪心算法、啟發(fā)式算法等 。 分支定界法 (BranehandBoundMethod)在本世紀(jì)六十年代初由 LandDoig和 Dakin等人提出 ,可用于解純整數(shù)或混合的整數(shù)規(guī)劃問(wèn)題。 .. ....對(duì)于背包問(wèn)題 ,已有的算法可分為精 確算法和近似算法兩大類。 .2背包問(wèn)題的研究現(xiàn)狀 從實(shí)際應(yīng)用方面研究 ,背包問(wèn)題是一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題 I5]。 最后本文從搜索代數(shù)、解的質(zhì)量和搜索時(shí)間等方面對(duì)基于交換策略的蟻群算 法與其它智能算法進(jìn)行比較 ,實(shí)驗(yàn)結(jié)果也顯示本文算法比其它智能算法用時(shí)更 少 ,解的質(zhì)量更高 ,是求解多維 O一 1背包問(wèn)題的有效算法。對(duì)這一問(wèn)題的求解 ,國(guó)內(nèi)外學(xué)者提 出了許多算法。目錄 第一章引言 ........................................................................................?? 1 1背包問(wèn)題簡(jiǎn)介 .....................................................................................?? 1 1背包問(wèn)題的描述 ........................................................................?? 1 .............................................................................?? 2 .............................................................................??“ .2 .................?? ,........