【文章內(nèi)容簡介】 ,它是在原有進(jìn)化算法理 論框 架的基礎(chǔ)上引入一個(gè)新算子 — 免疫算子 (i~une叩 erator),從而形成一種新的 算法。求解背包問題的免疫算法主要采用克隆選擇和貪心修正機(jī)理【川。與相應(yīng)的 遺傳算法相比 ,該算法有效克服了早熟問題、改善了陷入局部極小值的缺陷 ,而 且尋優(yōu)效果明顯。 遺傳算法、免疫算法等算法都是從進(jìn)化理論發(fā)展而來的 ,但是大自然給我們 的啟示并不僅僅在進(jìn)化方面 ,許多社會性動物 (如螞蟻、蜜蜂等 )的自組織行為也 引起了人們的廣泛關(guān)注和研究。蟻群算法的提出正是這些研究的成果。蟻群算法 是一種十分有效的算法 ,它在背包問題上也有重要的 應(yīng)用。本文的工作就是在蟻 群算法的基礎(chǔ)上進(jìn)行的。 遺傳算法、免疫算法和蟻群算法等算法雖然可能在求解某些問題時(shí)有計(jì)算時(shí) 間長 ,且容易陷入局部最優(yōu)解的缺點(diǎn) ,但是它們也有通用性強(qiáng)、容易與其它算法 相結(jié)合的優(yōu)點(diǎn)。在使用這些算法求解背包問題時(shí) ,縮短求解時(shí)間和提高解的質(zhì)量 就成為算法設(shè)計(jì)的一個(gè)關(guān)鍵。本文根據(jù)背包問題的特征 ,嘗試引入局部搜索策略 解決這個(gè)問題。 群算法求解 0一 l背包問題 仁自 _崔參硯 l弓旨 二月勺 `拼 .JIF二 I 1背包問題簡介 0一 1背包問題的描述 在算法研究過程中 ,有很多有實(shí)際背景的重要問題 ,它們是否有有效的算法 , 是計(jì)算機(jī)科學(xué)家們非常感興趣的問題。 1971年庫克 ()發(fā)表了 `,The eomplexity。 fTheoremProvingProeedures”〔 `l和 1972年卡普 ()發(fā)表的 。 `Redueibility靦 ongeombinatorialProb一 ems” I,l兩篇著名的論文奠定了砂完備理 論的基礎(chǔ)。即是 `NondeterministiePol” omial”的縮寫 ,意為“非確定型的多項(xiàng)式”。 在 NP 問題中 ,有一個(gè)子類 ,即完全 (NPComPlcte,簡記為腳 C)問題 ,指的是 那些 NP 問題中最難的問題 :所有其它的 NP 問題都可以歸約到這些 NP 完全問 題。 o一 1背包問題 (O一 1knapsackproblem,KP,以下簡稱背包問題 )是一個(gè)典型 NPC 問題 [2]。對一個(gè) m維。一 1背包問題可描述為 :己知有幾個(gè)價(jià)值為 vj仃 =l,2,? ,。 )的 物品 ,m個(gè)容積大小為 c,(i=l,2,? ,m)的容器 ,且卿個(gè)物品占用第 i個(gè)容器的容積 大小為烏?，F(xiàn)在問題是 :選擇哪些物品裝入這 m個(gè)容器使得裝入總價(jià)值最大。其 嚴(yán)格數(shù)學(xué)描述為 : maxf(x,x:,? ,x,:)= n s `藝 b。 x,三 e`(`一 `,2/=l 藝 vi xj j=l ,? ,m)() xz 任 {o,1}(j=1,2,? ,n) 這里 xj 表示是否選擇第 j個(gè)物品裝入背包 ,如果 xj 一 o,表示沒有選擇該物品 裝入 ,反之 xj 一 1,則表示選擇該物品裝入 。函數(shù) f(x,xZ,? ,戈 ,)表示裝入背包的 物品總價(jià)值。當(dāng) m姿 2時(shí) ,又稱為多維背包問題。背包問題本質(zhì)上是一個(gè)整數(shù)規(guī) 劃問題。 群算法求解 O一 l背包問題 本文嘗試以蟻群算法為基礎(chǔ)研究背包問題 ,實(shí)現(xiàn)一種能夠快速求解背包問題 的算法。主要對下列幾個(gè)問題進(jìn)行探討 : 。蟻群算法在許多方面已經(jīng)有了很好應(yīng)用 ,但是 在背包問題上應(yīng)用效果還不是很理想。蟻群算法所求解的問題模型可用圖來描 述 ,本文研究了如何將背包問題轉(zhuǎn)化成蟻群算法能夠有效求解的圖問題 ,并推廣 文獻(xiàn) {24」的圖表示法 ,將其應(yīng)用在多維背包問題上。 。蟻群算法的優(yōu)勢在于魯棒性好、具有 分布式 ,缺點(diǎn)是搜索時(shí)間長 ,容易陷于局部最優(yōu)解。交換是一種局部搜索策略 , 可以揚(yáng)長避短 ,極大提高蟻群算法的效率 ,所以需要研究基于交換策略的蟻群算 法。但是背包問題具有其特色 ,交換的 策略不同于其它問題 ,因此本文中提出了 一系列的交換方式來實(shí)現(xiàn)背包問題的交換。 。采用圖形、數(shù)據(jù)等手段實(shí)現(xiàn)了本文 算法同其它算法在時(shí)間、最優(yōu)解、搜索代數(shù)等方面的比較。這使得實(shí)驗(yàn)結(jié)果更加 形象、直觀。 本文的特色主要有 :采用蟻群算法求解背包問題 ,并將求解一維背包問題的 算法模型推廣成可以求解多維背包問題的算法模型 ,具有應(yīng)用創(chuàng)新 。實(shí)現(xiàn)基于交 換策略的蟻群算法求解背包問題 ,可以解決蟻群算法在求解背包問題時(shí)容易陷入 局部最優(yōu)解的問題 ,具有創(chuàng)新意義。 第一章蟻群算法 第二章蟻群算法 螞蟻又稱“玄駒”、 `嗽七好”或“狀元子” ,是一種既渺小而又平常的社會性昆蟲。 在分類上螞蟻屬于節(jié)肢動物門、昆蟲綱、膜翅目、蟻科 ,它在昆蟲界種類最多、 生存量最大 ,而且己經(jīng)在地球上生存了一億多年。隨著環(huán)境的變遷 ,身體龐大的 恐龍?jiān)缫呀?jīng)滅絕了 ,但是身體細(xì)小的螞蟻在弱肉強(qiáng)食、物竟天擇的自然界依靠集 體的力量和頑強(qiáng)的生命力一直生存繁衍到了今天。 盡管螞蟻個(gè)體比較簡單 ,但整個(gè)群體卻表現(xiàn)為高度機(jī)構(gòu)化的社會組織 ,在許 多情況下能完成遠(yuǎn)遠(yuǎn)超過螞蟻個(gè)體能力的復(fù)雜任務(wù)。這種能力 來源于螞蟻群體中 的個(gè)體協(xié)作行為。螞蟻的覓食行為就很好地體現(xiàn)了這種行為 l`2]。 在自然界中 ,螞蟻的食物源總是隨機(jī)散布于蟻巢周圍。在現(xiàn)實(shí)生活中 ,我們 總可以觀察到大量螞蟻在巢穴和食物源之間形成幾乎直線的路徑 ,而不是曲線或 者圓等其他形狀 ,如圖 。 圖 螞蟻群體不僅能完成復(fù)雜的任務(wù) ,而且還能適應(yīng)環(huán)境的變化 ,如在蟻群運(yùn)動 路線上突然出現(xiàn)障礙物時(shí) ,一開始螞蟻分布是均勻的 ,不管路徑長短 ,螞蟻總是 先按同等概率選擇各路徑 ,如圖 。 算法求解 0一 l背包問題 食物源 種扣 ~吧勃” 圖 但是經(jīng)過一段時(shí)間后 ,大部分螞蟻會選擇比較短的路徑。這是因?yàn)槲浵佒g 通過一種叫信息素 (Pheromone)的化學(xué)物質(zhì)進(jìn)行了信息的交流。螞蟻在運(yùn)動過程 中 ,能夠在其經(jīng)過的路徑上留下信息素 ,而且能感知這種物質(zhì)的存在及強(qiáng)度 ,并 以此指導(dǎo)自己運(yùn)動的方向 ,螞蟻傾向于信息素濃度高的方向移動。相等時(shí)間內(nèi)較 短路徑上的信息素遺留得比較多 ,則選擇較短路徑的螞蟻也隨之增多 ,如圖 所示。 啥氣 黑腸 .蒸麟月 *閱咖 圖 ,選擇該路徑的螞蟻增多 不難看出由大 量螞蟻集體行為表現(xiàn)出了一種信息正反饋現(xiàn)象 ,即某一條路徑 上走過的螞蟻越多 ,則后者選擇該路徑的概率越大。螞蟻個(gè)體之間就是通過這種 信息交流機(jī)制搜索食物 ,并最終沿著最短路徑行進(jìn) ,如圖 。 蟻穴 `粉瀚毒弩 圖 第一章蟻群算法 螞蟻選路過程中較短路徑上遺留的信息素濃度會在很短時(shí)間內(nèi)大于較長路 徑的原理我們不妨用下圖 (圖 )說明【 39。3】 :假設(shè) A、 D兩點(diǎn)是蟻群的巢穴和食物 源 ,從其間有兩條路徑 A一 B一 E一 C一 D和 A一 B一 F一 C一 D,其中 B一 F和 F一 C間距離 為 lm, B一 E和 E一 C間的距離為 ,如圖 (a)所示。 最初 (即 t=O時(shí)刻 ),當(dāng) 30只螞蟻?zhàn)叩椒致房?B或者 C點(diǎn)時(shí) ,要決定往哪個(gè) 方向走。因?yàn)槌跏紩r(shí)沒有什么線索可供它們選擇 ,所以它們就以相同的概率選擇 路徑 ,結(jié)果有巧只螞蟻?zhàn)咦筮吢窂?C一 F和 B一 F。另外巧只螞蟻?zhàn)哂疫叺穆窂? C一 E和 B一 E,如圖 (b)所示 ,這些螞蟻在行進(jìn)過程中分別留下信息素。若假設(shè) 螞蟻都具有相同的速度 (1耐 s)和信息素釋放能力 ,則經(jīng)過 ls 后從 B點(diǎn)出發(fā)的 30 只螞蟻有巧只到達(dá)了 F,有巧只經(jīng)過 E到達(dá)了 C點(diǎn) ,同樣從 C點(diǎn)出發(fā)的 30只 螞蟻有巧只螞蟻到達(dá)了 F,有巧只經(jīng)過 E到達(dá)了 C點(diǎn)。很顯然 ,在相等時(shí)間間 隔內(nèi)路徑 B一 F一 C上共有巧只螞蟻經(jīng)過并遺留信息素 ,B一 E一 C上卻有 30只螞蟻經(jīng) 過并遺留了信息素 ,其信息素強(qiáng)度是 B一 F一 C路徑上的 2倍。因此當(dāng) 30只螞蟻分 別回到 B、 C點(diǎn)重新選擇路徑時(shí)就會以 2倍于 B一 F一 C的概率選擇路徑 B一 E一 C,從 而 B一 F一 C上的螞蟻數(shù)目變成 10只 ,是 B一 E一 C上螞蟻數(shù)目的一半 ,如圖 (c)所 示 ,距離較短的路徑上信息素很快得到強(qiáng)化 ,其優(yōu)勢很快被蟻群所發(fā)現(xiàn)。 君?華卜 05丫尸 d谷 (a)E 圖 中螞蟻覓食模擬 1989年 ,GosSS等通過著名的“雙橋”實(shí)驗(yàn)對蟻群的覓食行為進(jìn)行研究 ,并 給出了蟻群覓食行為的數(shù)學(xué)模型。首先 ,假設(shè)在非對稱橋上的信息素與過去一段 第一章蟻群算法 算機(jī)中只有一個(gè)個(gè)離散點(diǎn) ,因此 ,用任意兩個(gè)節(jié)點(diǎn)表示螞蟻的巢穴 (初始節(jié)點(diǎn) )和 食物源 (目標(biāo)節(jié)點(diǎn) ),人工螞蟻從初始節(jié)點(diǎn)出發(fā)根據(jù)一定概率條件 (信息素大小 )選 擇下一個(gè)節(jié)點(diǎn) ,直到找到目標(biāo)節(jié)點(diǎn) ,這就是問題的一個(gè)可行解。 對信息素?fù)]發(fā)的抽象。因?yàn)樾畔⑺負(fù)]發(fā)在現(xiàn)實(shí)世界中也是一個(gè)連續(xù)事件 ,而 且螞蟻在經(jīng)過路徑上也是連續(xù)不斷地留下信息素。通常做法是 :當(dāng)螞蟻完成從某 個(gè)節(jié)點(diǎn)到下一個(gè)節(jié)點(diǎn)的移動后 ,即經(jīng)過一個(gè)時(shí)間單位之后 ,進(jìn)行一次信息素?fù)]發(fā) , 這種離散時(shí)間點(diǎn)揮發(fā)方式與螞蟻覓食機(jī)理是完全相符的。 引入啟發(fā)因子。蟻群算法的整個(gè)過程體現(xiàn)了自組織性 ,但是這種自組織系統(tǒng) 存在一個(gè)缺陷 ,就是系統(tǒng)的演化需要很長時(shí)間。因此在決定螞蟻行走方向的狀態(tài) 轉(zhuǎn)移概率時(shí) ,引入一個(gè)隨機(jī)搜索過程 ,即引入啟發(fā)因子 ,根據(jù)所求問題空間的具 體特征 ,給蟻群算法一個(gè)初始引導(dǎo) ,這個(gè)過程極大地加快了算法的時(shí)間有效性。 通過上述描述的一些抽象過程 ,可以建立一個(gè)蟻群算法的基本模型。其問題 空間是用圖來描述的 ,解的獲取是構(gòu)造性的 ,而且在解的構(gòu)造過程中人工螞蟻沒 有接受任何全局的指導(dǎo)信息 ,因而求解過程是自組織的。在定義了一些規(guī)則之后 , 蟻群算法就可以求解那些可用圖描述的問題。 蟻群算法的數(shù)學(xué)模型可以描述如下【 `4]Il8][l9]: 設(shè) C一 {cl,cZ,? ,c。 }為。個(gè)節(jié)點(diǎn)的集合 ,L一 {氣 }c,c,。 C}是 C中節(jié)點(diǎn)兩兩連 接的路徑權(quán)值集合 ,幾 (t)為 t時(shí)刻路徑 (i,力上的信息素濃度 ,r=籠幾 (t)}ci,cj任 C} 是 t時(shí)刻路徑 (i,力上殘留信息素濃度的集合 ,在初始時(shí)刻各條路徑上的信 息素濃 度相等 ,并設(shè)幾 (0)=const,蟻群算法就是通過有向圖 G=(C,L,r)實(shí)現(xiàn)的。 n 設(shè)互 (t)(i二 `,2,一” )是 t時(shí)刻節(jié)點(diǎn) `的螞蟻數(shù) ,則 m。一藝今 (t)為全部螞蟻數(shù)。 i=, 每只人工螞蟻有以下特性 : (l)螞蟻根據(jù)一定概率函數(shù)選擇下一節(jié)點(diǎn) ,其中概率函數(shù)是節(jié)點(diǎn)之間權(quán)值及 邊上信息素濃度的函數(shù)。 (2)每只人工螞蟻只能走合法路線 ,除非一次遍歷結(jié)束 ,不允許轉(zhuǎn)到己經(jīng)訪 群算 .法求解 0一 l背包問題 時(shí)間內(nèi)通過該橋的螞蟻成正比 。其次 ,再假設(shè)某一時(shí)刻螞蟻按照橋上的殘留信息 素的多少來選擇其中某座橋 ,經(jīng)過 該橋的螞蟻數(shù)目越多 ,則該橋上的殘留信息素 就越多。該例中 ,假設(shè)短橋?yàn)?A,長橋?yàn)?B,從 ,:和盡 。:分別表示經(jīng)過橋 A和經(jīng)過 橋 B的螞蟻數(shù)目 (態(tài) +凡 ,=m),則當(dāng)所有 m只螞蟻都經(jīng)過兩座橋后 ,第 m+l只 螞蟻選擇 A橋的概率為 :凡 (m)(A,。 +k)“ (A,+k)力 +(B,+k)丙 (次 ,(盡” 選擇 B橋的概率為 :凡 (m)=1一凡 (m) 式中 ,參數(shù) h和 k用以匹配真實(shí)實(shí)驗(yàn)數(shù)據(jù)。第 m+1只螞蟻按概率選擇不同的橋。 根據(jù)上面的模型 ,對蟻群覓食過程進(jìn)行計(jì)算機(jī)動態(tài)模擬 ,最終的結(jié)果是螞蟻 會集中在離食物源最近的路徑上。 根據(jù)螞蟻覓食的群體行為 ,意大利學(xué)者 DorigoM等【 `“ ]于 1991年在法國巴黎 召開的第一界歐洲人工生命會議 (EuropeanConfereneeonArtifieialLife,EeAL) 上最早提出了蟻群算法的基本模型 。1992年 ,DorigoM又在其博士學(xué)位論文中 進(jìn)一步闡述了蟻群算法的核心思想【 39。5】。 .,蟻群算法模型的建立 蟻群算法的模型主要從下面幾個(gè)方面對自然界中真實(shí)螞蟻覓食行為進(jìn)行了 抽象 [39。“ ][39。7]: 對螞蟻個(gè)體的抽象。由于蟻群算法只是對螞蟻覓食行為的一種 模擬 ,沒有必 要對螞蟻個(gè)體進(jìn)行完全再現(xiàn) ,摒棄與算法無關(guān)的因素 ,這樣抽象出來的人工螞蟻 可以看作一個(gè)簡單的智能體 ,能夠構(gòu)造所求問題的解 ,也能通過一種信息手段相 互影不 !l句。 對問題空間描述的抽象。自然界中的真實(shí)螞蟻存在于一個(gè)連續(xù)的三維空間 中 ,但計(jì)算機(jī)只能處理一些離散的點(diǎn)。在實(shí)現(xiàn)過程中 ,一般都將蟻群算法求解的 問題轉(zhuǎn)換成數(shù)學(xué)上的圖 (graPh)來描述 ,在實(shí)際工程中許多問題都可以用圖來描 述 ,這也是蟻群算法應(yīng)用廣泛的一個(gè)原因。 對尋找路徑的抽象。螞蟻的覓食路徑在現(xiàn)實(shí)中是一個(gè)面上連續(xù)路徑 ,但是計(jì) 群算 .法求解 O一 l背包問題 問的節(jié)點(diǎn)。該過程由螞蟻的禁忌表來控制 ,禁忌表 tabu*(k二 1,2,? ,m。 )用來記錄 螞蟻 k當(dāng)前走過節(jié)點(diǎn)的集合 ,如果螞蟻 k經(jīng)過節(jié)點(diǎn) i,就將節(jié)點(diǎn)動口入到自己的禁忌 表中 ,表示下次不能再選擇節(jié)點(diǎn) i,這樣集合會隨著移動過程作動態(tài)調(diào)整。 (3)完成一次遍歷后 ,螞蟻在其訪問過的每一條邊上留下相應(yīng)的信息素。 蟻群算法可以表述如下 :在算法初始時(shí)刻 ,將 mc只螞蟻隨機(jī)放到 n個(gè)節(jié)點(diǎn) , 同時(shí)更新禁忌表 ,此時(shí)各條路徑上的信息素相等 ,且為一常數(shù)。接下來 ,螞蟻 k(k=l,2,二 ,m。 )在運(yùn)動過程中 ,根據(jù)各條路徑上的 信息素濃度決定其轉(zhuǎn)移方向。 在搜索過程中 ,螞蟻根據(jù)各條路徑上的信息素及路徑