蟻群算法思想論文：蟻群算法的0-1背包問題求解研究

1、蟻群算法思想論文：蟻群算法的0-1背包問題求解研究摘要：提出解決背包問題的蟻群算法思想及求解0-1背包問題問題描述，給出了改進(jìn)常規(guī)的蟻群算法的方法。關(guān)鍵詞：背包問題，蟻群算法，問題設(shè)計(jì)，算法改進(jìn)1問題描述0/1背包問題是指有不同價(jià)值、不同重量的物品n件，求從這n件物品中選取一部分物品且對(duì)每一物品，要么選，要么不選，滿足被選物品的總重量不超過背包指定的限制重量且達(dá)到被選物品的價(jià)值總和最大的問題。如果所有物品的重量之和小于背包的容量，貝恫題極其簡單，所得利益也就是所有物品的價(jià)值之和。2蟻群算法的思想蟻群算法是模仿真實(shí)的蟻群行為而提出的一種模擬進(jìn)化算法.螞蟻之間是通過一種稱為信息素(Pheromon

2、e)的物質(zhì)傳遞信息的，螞蟻在運(yùn)動(dòng)過程中能夠在經(jīng)過的路徑上留下該種物質(zhì)，而且能夠感知這種物質(zhì)的存在及其強(qiáng)度，并以此指導(dǎo)自己的運(yùn)動(dòng)方向.因此，由大量螞蟻組成的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一條路徑上走過的螞蟻越多，該路徑上留下的信息素就越多，則后來者選擇該路徑的概率就越大.螞蟻個(gè)體之間就是通過這種信息素的交流，搜索到一條從蟻巢到食物源的最短路徑.3利用蟻群算法求解0-1背包問題設(shè)計(jì)設(shè)有n個(gè)城市，d,(i,J=l,2,，n)表示城市i和J間的距離，t.j(t)表示在t時(shí)刻城市i和j之間的信息量，以此來模擬實(shí)際螞蟻的分泌物。設(shè)共有m只螞蟻，用P.ijk表示在t時(shí)刻螞蟻k由城市i轉(zhuǎn)移到城市J的概

3、率，則Pk.ijk(t)由城市i轉(zhuǎn)移到城市J的概率，貝SQ.ij(t)Ii.ij(t)ErallowedkQ.ir(t)卩.ir(t)jallowdk0otherwise其中，allowedk表示螞蟻k下一步允許走過的城市的集合，表示路徑上的信息量對(duì)螞蟻選擇路徑所起的作用大小，n為由城市i轉(zhuǎn)移到城市j的期望程度，例如，可以取nij=1/d.ij。B表示nij的作用。當(dāng)a=0時(shí)，算法就是傳統(tǒng)的貪心算法；而當(dāng)p=O時(shí),就成了純粹的正反饋的啟發(fā)式算法。經(jīng)過n個(gè)時(shí)刻，螞蟻?zhàn)咄晁械某鞘?，完成一次循環(huán)。每只螞蟻所走過的路徑就是一個(gè)解。此時(shí)，要根據(jù)式(3)對(duì)各路徑上的信息量作更新：tij(t+1)=(1-

4、p)?tij+Atij(2)其中p(0,I),表示信息量r.ij隨時(shí)間的推移而衰減的程度。信息增量AT可表示為Axij=Dmk=1k.ij其中Ajk表示螞蟻k在本次循環(huán)中在城市i和之間留下的信息量，它的計(jì)算公式根據(jù)計(jì)算模型而定，例如在最常用的antcirclesystem模型中.螞蟻k在本次循環(huán)中經(jīng)過城市i和j之間AtQ/L.k螞蟻k在本次循環(huán)中經(jīng)過城市i和j之間Totherwise其中Q為常數(shù)，為螞蟻k在本次循環(huán)中所走路徑的長度。經(jīng)過若干次循環(huán)以后，可以根據(jù)適當(dāng)?shù)耐Ｖ箺l件來結(jié)束計(jì)算。4算法描述蟻群算法的主要步驟如下：步驟1:初始化。步驟2:生成M只螞蟻，并將其置于節(jié)點(diǎn)1。步驟3：for每只螞蟻do按照式（1）計(jì)算并選擇下一條有向線段；如果沒有有向線段滿足背包問題的約束條件，則該螞蟻就死掉：如果螞蟻沒有死亡.則將選擇有向線段的序號(hào)加入螞蟻的禁忌表中；.步驟4:計(jì)算本次迭代的最好解.如果其優(yōu)于當(dāng)前的最好解。則用其