求解多維0_1背包問題的蟻群算法研究

《求解多維0_1背包問題的蟻群算法研究》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、第7卷%第12期軟件導(dǎo)刊Vol.7No.122008年12月SoftwareGuideDec.2008求解多維0-1背包問題的蟻群算法研究張芹，宮洪蕓（中國地質(zhì)大學(xué)計(jì)算機(jī)學(xué)院，湖北武漢430074）摘要：系統(tǒng)地闡述了蟻群算法,并對它進(jìn)行改進(jìn)、優(yōu)化。將蟻群算法應(yīng)用于求解多維0-1背包問題,提出一種新的求解多維0-1背包問題的算法———基于交換策略的蟻群算法。關(guān)鍵詞：多維0-1背包問題；蟻群算法；交換策略；優(yōu)化中圖分類號：TP312文獻(xiàn)標(biāo)識碼：A文章編號：1672-7800（2008）12-0049-03n

2、1maxf（x1，x2，x3，…，xn）=Σvj*xj多維0-1背包問題j=1ns.t．Σbij*xj≤ci（i=1，2，…，m）（1）1.1問題描述j=1多維0-1背包問題就是給出一套實(shí)體及它們的價值和尺xi∈{0，1}，（i=1，2，…，n）寸，選擇一個或多個互不相干的子集，使每個子集的尺寸不超其中f（x1，x2，x3，…，xn）為目標(biāo)函數(shù)；xj為0-1變量，當(dāng)物品j過給定邊界，而被選擇的價值總和最大。具體地，已知n個價值被選入時xj=1，否則xj=0。為vj（j=1，2，…，n）的物品，m個容積為

3、Ci（i=1，2，…，m）的容１.2多維0-1背包問題的圖形表示器，第j個物品占用第i個容器的容積大小為bij?，F(xiàn)在的問題是多維0-1背包問題的構(gòu)造圖如圖1所示。該圖由n+1個節(jié)點(diǎn)按照先后順序排列而成，從節(jié)點(diǎn)i（i=1，2，…n）出發(fā)共有n條有向選擇哪些物品裝入這m個容器，即求一個二進(jìn)制的向量X=（線段a［i，j］（j=1，2，…n）連接到節(jié)點(diǎn)i+1，在a［i，j］（i，j=1，2，…n）x1，x2，…，xn），使得裝入的總價值最大。這是一個整數(shù)規(guī)劃問題。上有vj（第j個物品的價值）和占用每個容器大小b

4、ij（i，j=1，2，…其嚴(yán)格的數(shù)學(xué)描述如下：n）與其相關(guān)聯(lián)。３結(jié)束語參考文獻(xiàn):［1］王麗娜，郭遲，李鵬.信息隱藏技術(shù)實(shí)驗(yàn)教程［M］.武漢：武漢大學(xué)本文提出了一種基于離散小波變換（DWT）的彩色圖像水出版社，2004.印算法，與二值圖像和灰度圖像不同，彩色圖像作為水印圖像［2］王麗娜，張煥國.信息隱藏技術(shù)與應(yīng)用［M］.武漢：武漢大學(xué)出版嵌入與提取的難度較大，因其具有R，G，B不同的層面，在嵌入社，2003.與提取時都要充分考慮水印圖像嵌入到原始圖像的各層的比［3］SwansonMD，KobayashiM

5、，TewfikAH.Multimediadata例系數(shù)，從嵌入水印后圖像中提取時也要考慮比例系數(shù)（本文embeddingandwatermarkingtechnologies［J］.ProceedingsoftheR，G，B各層的嵌入與提取的比例系數(shù)均取0.1），實(shí)驗(yàn)結(jié)果表IEEE，1986（6）.明：隱藏了水印的圖像與原始圖像在視覺上幾乎分辨不出，較［4］龔劬，苗婷.基于圖像特征的小波域自適應(yīng)水印算法［J］.計(jì)算機(jī)好地達(dá)到了隱藏水印的目的，實(shí)驗(yàn)結(jié)果：輸入圖像均方差工程與應(yīng)用，2007（25）.（MSE

6、）檢測數(shù)據(jù)的MSE為:127.6094，待測圖像的信躁比為:［5］孔祥維，劉華健，劉雨.數(shù)字圖像的光電處理對數(shù)字水印的影響0.034245dB，提取的水印具有很高的峰值信噪比（PSNR=［J］.光電子·激光，2001（6）.［6］劉挺，尤韋彥.一種基于離散小波變換和HVS的彩色圖像數(shù)字水51.154dB）且與原始水印具有很好的相似性（NC=0.94974），從印技術(shù)［J］.計(jì)算機(jī)工程，2003（４）.而驗(yàn)證了該算法的可行性。但該算法提取水印時需要原始圖像（責(zé)任編輯：卓光）的參與，不能實(shí)現(xiàn)盲水印提取。作者

7、簡介：張芹（1983~），女，湖北武漢人，中國地質(zhì)大學(xué)（武漢）碩士研究生，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)；宮洪蕓（1985~），女，湖北武漢人，中國地質(zhì)大學(xué)（武漢）碩士研究生，研究方向?yàn)榫W(wǎng)絡(luò)工程與應(yīng)用?！?0·軟件導(dǎo)刊2008年步驟2：生成M只螞蟻，并將其置于節(jié)點(diǎn)1。步驟3：for每只螞蟻do{按照式（1）計(jì)算并選擇下一條有向線段；如果沒有有向線段滿足背包問題的約束條件，則該螞蟻就死掉；圖1背包問題的圖形表示如果螞蟻沒有死亡，則將選擇有向線段的序號加入螞蟻的禁忌表中；2蟻群算法}2.1算法基本思想步驟4：計(jì)算本次

8、迭代的最好解，如果其優(yōu)于當(dāng)前的最好蟻群算法是一種源于大自然的新型仿生類進(jìn)化算法，源解，則用其替代當(dāng)前的最好解。于對螞蟻覓食模型的研究。它成功地應(yīng)用于求解TSP、二次分步驟5：按照式（2）更新路徑的信息素。配、圖著色、車輛調(diào)度、集成電路設(shè)計(jì)以及通信網(wǎng)絡(luò)負(fù)載等問步驟6：if（未達(dá)到NCmax）&&（沒有進(jìn)入停滯狀態(tài)）then題。蟻群算法的基本思想是：模仿螞蟻依賴信息素進(jìn)行通信而{顯示出的社會性行為，在智能體定義的基礎(chǔ)上，由一個貪心法（1）清空所