蟻群算法在0-1背包問題中的研究與實(shí)現(xiàn)

摘要：蟻群算法也稱為螞蟻算法，即模擬螞蟻從居住地出發(fā)去尋找食物源的過程，它在一定程度上可以看成是一種用來在圖中尋找最優(yōu)路徑的算法。該算法已成功地應(yīng)用于許多離散問題。隨著研究的深入與應(yīng)用領(lǐng)域的逐步擴(kuò)展，蟻群算法已經(jīng)在智能領(lǐng)域顯示出了較為重要的地位，對于解決各種復(fù)雜優(yōu)化問題都顯示出了它的優(yōu)點(diǎn)。0-1背包問題是一個(gè)經(jīng)典算法，在實(shí)際生活中應(yīng)用較為廣泛，例如在材料切割、貨物裝箱、車間調(diào)度等問題中都有相關(guān)的應(yīng)用。本文主要實(shí)現(xiàn)了蟻群算法解決0-1背包問題，首先研究了蟻群算法的基本原理及算法思想，然后在MATLAB下實(shí)現(xiàn)了蟻群算法求解0-1背包問題。實(shí)驗(yàn)表明，算法運(yùn)行結(jié)果正確，穩(wěn)定性好。

關(guān)鍵詞：蟻群算法;0-1背包;信息素;揮發(fā)因子

中圖分類號：TP 391

引言

蟻群算法是一種群體智能理論的優(yōu)化算法，蟻群算法的基本思想是根據(jù)螞蟻從蟻巢出發(fā)去尋找食物源的過程得出的。蟻群算法如今也多用于求解旅行商問題，隨著網(wǎng)絡(luò)科技的發(fā)展，網(wǎng)購等在人們的生活中所占比重越來越大，還有近幾年流行的‘UU跑腿’等，這些實(shí)際生活中的問題都會用到蟻群算法，該算法已經(jīng)成功地應(yīng)用到了許多離散問題中，在國際群體智能計(jì)算領(lǐng)域，蟻群算法已經(jīng)成為一個(gè)熱門的研究方向。

背包問題最早是由 Dantzing在 20 世紀(jì)50 年代首次提出的，應(yīng)用已經(jīng)越來越廣泛。背包問題是指：對于n個(gè)物品和一個(gè)背包，當(dāng)知道每個(gè)物品的重量和價(jià)值以及背包所能承受的最大重量時(shí)，從這些物品中選出若干件放入背包中，使得背包的重量小于背包所能承受的最大重量，并且背包的總價(jià)值能夠達(dá)到最大。背包的總價(jià)值等于裝入背包的物品價(jià)值之和，找出一種放入物品的方案能同時(shí)滿足上述兩個(gè)條件。

記背包的總重量為為total_weight，總價(jià)值為total_value，x（i）=1表示將第i個(gè)物品放入背包，x（i）=0表示未放入，根據(jù)0-1背包問題的算法原理，可將其數(shù)學(xué)模型表示為如下：

1? 蟻群算法的算法思想

蟻群算法是指螞蟻從蟻巢出發(fā)去尋找食物的過程中，當(dāng)蟻巢到食物源的距離越短，則螞蟻從巢到食物源，然后再返回巢的時(shí)間越短。這相當(dāng)于在相同的時(shí)間內(nèi)，路徑越短螞蟻會分泌和積累越多的信息素，而隨后去尋找食物的螞蟻會根據(jù)前面螞蟻分泌的信息素來判斷哪條路徑最短，以便能夠快速準(zhǔn)確的選擇哪條路徑。所以某條路徑上的信息素越多，螞蟻選擇這條路的可能性就越大。

2? 蟻群算法實(shí)現(xiàn)0-1背包的算法步驟

蟻群算法的算法步驟如下：

（1）初始化參數(shù)：設(shè)置蟻群參數(shù)，背包相關(guān)的參數(shù)，路徑信息素等參數(shù);

（2）螞蟻移動(dòng)：后續(xù)出發(fā)的螞蟻根據(jù)前面螞蟻留下的信息素含量和一定的概率來選擇要行走的路徑，在實(shí)現(xiàn)0-1背包問題中計(jì)算某個(gè)物品被選擇的概率;

（3）螞蟻要行走的路線信息更新：根據(jù)（2）中計(jì)算的概率，螞蟻將選擇某條路徑，同時(shí)將對應(yīng)的物品添加到路徑中;

（4）判斷是否滿足條件：判斷將物品添加到背包后是否滿足條件，并更新背包的價(jià)值的重量;

（5）評價(jià)蟻群：計(jì)算一次循環(huán)結(jié)束后的最優(yōu)值，將其與全局最優(yōu)值比較，判斷是否需要更新全局最優(yōu)值。

3? 算法實(shí)現(xiàn)

（1）初始化參數(shù)：定義物品的價(jià)值，重量以及背包能承受的最大重量;定義信息素?fù)]發(fā)因子為r，全局最優(yōu)解為Jie_best，全局最優(yōu)值為value_best，定義最大迭代次數(shù)為count ;

（2）從i=1到count循環(huán)遍歷：定義一個(gè)零矩陣用以存儲m只螞蟻的路徑，j從1到n開始循環(huán)，根據(jù)信息素的重要因子（a）及吸引因子（b）計(jì)算每個(gè)物品被選擇的概率。

for j=1：n

d=d+t（j）^a*（value（j）/weight（j））^b;

end

for j=1：n

q（j）=t（j）^a*（value（j）/weight（j））^b/d;

end

（3）選擇物品放入背包：先隨機(jī)選取一個(gè)物品放入背包，并將其添加到當(dāng)前對應(yīng)螞蟻的路徑中，修改背包當(dāng)前的容量。

x=floor（rand*9）+1;

D（k，x）=1;

W_now=weight（x）;

（4）更新路徑及背包信息：利用輪盤賭法，信息素?fù)]發(fā)系數(shù)計(jì)算下一個(gè)物品被選擇的概率，如果滿足背包容量限制條件則將其加入背包中，并更新當(dāng)前螞蟻的路徑信息和背包信息。

j=roulette_wheel（u，temp）;

u=u-temp（j）;

Temp（j）=0;

if（W_now+weight（j）<=W）

D（k，j）=1;

W_now=W_now+weight（j）;

（5）更新全局最優(yōu)值：一次迭代完成后將本次迭代的最優(yōu)值與全局最優(yōu)值對比，根據(jù)對比結(jié)果重新定義全局最優(yōu)值。

[p_best（i），J]=max（D*value’）;

if（value_best<p_best（i））

value_best=p_best（i）;

Jie_best=D（J，：）;

4? 運(yùn)行結(jié)果

圖1是輸入5個(gè)物品時(shí)的運(yùn)行結(jié)果，隨機(jī)輸入5個(gè)物品的價(jià)值和重量可由蟻群算法求出背包的最大價(jià)值，最大重量以及裝入背包的物品序號。由圖1可知，對于給定的物品價(jià)值和物品重量，背包的最大容量以及其他相關(guān)參數(shù)，圖2算法求得背包的最大價(jià)值，最大重量以及裝入背包的物品序號，在改變相關(guān)參數(shù)時(shí)背包的價(jià)值和重量，最優(yōu)解不會改變，但是達(dá)到最有解的迭代次數(shù)會發(fā)生相應(yīng)的變化。在一定的范圍內(nèi)，當(dāng)揮發(fā)系數(shù)增加時(shí)，達(dá)到最優(yōu)解的迭代次數(shù)越大。這一結(jié)果在理論上也可以解釋，因?yàn)楫?dāng)信息素?fù)]發(fā)系數(shù)越大時(shí)，后續(xù)螞蟻在尋找食物時(shí)選到最短路徑的概率就會越小，因此全局找到最短路徑的時(shí)間就越長，這一原理體現(xiàn)在0-1背包問題中就是選擇下一個(gè)物品裝入背包時(shí)，選到使背包最終價(jià)值最大的物品的時(shí)間會越長。

5? 結(jié)語

蟻群算法的研究現(xiàn)在已經(jīng)達(dá)到了相對成熟的水平，已有不少學(xué)者進(jìn)行了大量的研究，提出了很多研究結(jié)論和寶貴經(jīng)驗(yàn)，本文基于蟻群算法實(shí)現(xiàn)了0-1背包問題。針對蟻群算法，雖然它可以應(yīng)用到貨物配送等問題中，但是在實(shí)際的配送中可能需要考慮更多的因素，例如當(dāng)有物品需要特殊處理或優(yōu)先配送時(shí)需要對蟻群算法進(jìn)行一定的改進(jìn)，體現(xiàn)在蟻群算法中就是優(yōu)先處理有特殊需求的城市頂點(diǎn)，后面將對這一點(diǎn)進(jìn)行進(jìn)一步的研究。

參考文獻(xiàn)：

[1]M. Dorigo，V. Maniezzo，A. Colorni，“Ant system optimization by a colony of cooperating agents，” IEEE Transactions on System，Man，and Cybernetics-Part B，1996，26（1）. 8- 41.

[2]M. Dorigo，L.M. Gambardella. “Ant colony system：a cooperative learning approach to the traveling salesman problem，” IEEE Transactions on Evolutionary Computing，1997，1（1）. 53- 56.

[3]胡小兵. 蟻群優(yōu)化原理、理論及其應(yīng)用研究[D]. 重慶大學(xué)，2004

[4]鄢莉. 0-1背包問題的算法決策分析[J]. 電腦知識與技術(shù)，2020，16（04）：259-260+264.

[5]田峰楠，王于. 求解0-1背包問題算法綜述[J]. 軟件導(dǎo)刊，2009，8（01）：59-61.

[6]宋志飛. 基于蟻群算法的TSP問題研究[D]. 江西理工大學(xué)，2013.

[7]弓英瑛. 蟻群算法的改進(jìn)研究與應(yīng)用[D]. 安徽理工大學(xué)，2014.

作者簡介：宇亞衛(wèi)（1979-），女，陜西乾縣人，碩士，講師，主要從事圖形圖像處理方面的教學(xué)和研究工作。