改進(jìn)蟻群算法在農(nóng)村垃圾治理問題中的應(yīng)用

李婷

李 婷. 改進(jìn)蟻群算法在農(nóng)村垃圾治理問題中的應(yīng)用［J］. 湖北農(nóng)業(yè)科學(xué)，2024，63（3）：255-259．

摘要：為了減少農(nóng)村垃圾治理的運(yùn)輸費(fèi)用，通過引入節(jié)約因子、將螞蟻分為探索蟻和確定蟻兩種分工合作模式、保留父代最優(yōu)路徑3個(gè)方面對蟻群算法進(jìn)行改進(jìn)，并將其應(yīng)用于農(nóng)村垃圾車回收最優(yōu)路徑的確定中，從而減少運(yùn)輸路程。將改進(jìn)后的蟻群算法與最大最小螞蟻系統(tǒng)進(jìn)行性能對比試驗(yàn)，結(jié)果顯示，改進(jìn)后的蟻群算法在迭代次數(shù)為132次時(shí)趨于穩(wěn)定，且其最優(yōu)值為623.157 9，均優(yōu)于最大最小螞蟻系統(tǒng)。該結(jié)果說明改進(jìn)后的蟻群算法的尋找最優(yōu)路徑性能更優(yōu)，可以利用其對農(nóng)村垃圾回收路徑進(jìn)行確定，為農(nóng)村垃圾治理領(lǐng)域提供一個(gè)新思路。

關(guān)鍵詞：垃圾治理；蟻群算法；節(jié)約因子；回收路徑

中圖分類號：F799.3? ? ? ? ?文獻(xiàn)標(biāo)識碼：A

文章編號：0439-8114（2024）03-0255-05

DOI：10.14088/j.cnki.issn0439-8114.2024.03.038 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

隨著人們生活品質(zhì)的提高，垃圾的產(chǎn)量也越來越高，而農(nóng)村的垃圾處理問題頻發(fā)，很多農(nóng)村對垃圾治理不及時(shí)或方式不對，導(dǎo)致農(nóng)村居民的生活質(zhì)量下降［1，2］。國家對此非常重視，投入大量資金開展農(nóng)村垃圾治理工作，但由于農(nóng)村垃圾回收路徑的規(guī)劃模型不夠完善，無法確定最短的垃圾回收路徑，導(dǎo)致政府資金的浪費(fèi)，因此探索一種可以確定農(nóng)村垃圾回收最短路徑的方法具有重要意義［3，4］。蟻群算法是一種根據(jù)螞蟻運(yùn)動(dòng)演變而來的算法，其可以利用信息素的幫助確定最短路徑［5］。但傳統(tǒng)的蟻群算法收斂速度慢，確定最優(yōu)路徑的穩(wěn)定性不高［6］。故將改進(jìn)后的蟻群算法與農(nóng)村垃圾回收路徑模型相結(jié)合，確定農(nóng)村垃圾回收的最短路徑，從而降低農(nóng)村垃圾治理的運(yùn)輸費(fèi)用，為政府節(jié)省開支。

1 基于改進(jìn)蟻群算法的農(nóng)村垃圾治理模型構(gòu)建

1.1 農(nóng)村垃圾治理模型構(gòu)建及相應(yīng)路徑優(yōu)化算法

農(nóng)村垃圾治理問題已成為廣大農(nóng)村的普遍問題，在農(nóng)村垃圾治理中存在諸多問題［7］。為了更好地對農(nóng)村垃圾進(jìn)行治理并降低垃圾的運(yùn)輸成本，研究提出了一種農(nóng)村垃圾回收路徑（Rural garbage collection routing，RGCR）。該回收路徑是以各小鎮(zhèn)為單位，求得農(nóng)村生活垃圾的總路程最小的轉(zhuǎn)運(yùn)路徑，從而減少農(nóng)村垃圾的運(yùn)輸成本。在一個(gè)小鎮(zhèn)中，垃圾的回收過程如下，首先是多輛垃圾車離開車場，分別前往各鄉(xiāng)村進(jìn)行垃圾回收，當(dāng)垃圾車回收的垃圾達(dá)到其最大載重量時(shí)，隨即前往轉(zhuǎn)運(yùn)站進(jìn)行傾倒垃圾，然后返回車場。RGCR如圖1所示。

圖1為某鎮(zhèn)的垃圾回收路徑圖，從中可以看出，該鎮(zhèn)共管轄7個(gè)鄉(xiāng)村，利用2輛垃圾車對轄內(nèi)7個(gè)鄉(xiāng)村進(jìn)行垃圾處理，2輛垃圾車從垃圾車場出發(fā)，對每個(gè)農(nóng)村的垃圾進(jìn)行回收，當(dāng)垃圾車的垃圾收集量到達(dá)最大承載量后返回垃圾處理廠進(jìn)行垃圾傾倒，然后返回垃圾車車場。在RGCR中包括垃圾車車場、農(nóng)村、垃圾處理廠、垃圾車等要素。其中垃圾車車場既是垃圾車的出發(fā)位置也是其結(jié)束位置，而垃圾車是該路徑中的主體，其主要作用是對垃圾進(jìn)行運(yùn)輸。垃圾對應(yīng)的是物流中的貨物，具有重量及采集地點(diǎn)2個(gè)屬性，其為垃圾車行駛路徑選擇的依據(jù)。農(nóng)村為該回收路徑中的服務(wù)對象，每個(gè)農(nóng)村為1個(gè)垃圾采集點(diǎn)，且每個(gè)垃圾采集點(diǎn)能且只能被服務(wù)1次。垃圾轉(zhuǎn)運(yùn)站的主要功能是對垃圾進(jìn)行傾倒。除此之外還有約束條件和目標(biāo)函數(shù)，約束條件是指垃圾車在回收垃圾過程中需要滿足的條件，而目標(biāo)函數(shù)是指對路徑問題進(jìn)行求解的函數(shù)，研究選取車輛總行駛里程最短為目標(biāo)函數(shù)對該路徑問題進(jìn)行求解。通過該垃圾回收模型找到車輛總行駛里程最短的路徑即可節(jié)約垃圾運(yùn)輸成本。蟻群算法是一種最優(yōu)化路徑的方法，其基本原理與螞蟻的運(yùn)動(dòng)相關(guān)［8］。具體內(nèi)容為，螞蟻會在其途徑的道路上留下名為信息素的分泌物，螞蟻之間可以通過信息素進(jìn)行信息交流，螞蟻在運(yùn)動(dòng)過程中會更喜歡沿著信息素濃度高的路徑行走，因此該路徑信息素濃度又會升高，從而形成正反饋現(xiàn)象［9］。在螞蟻的路徑行走正反饋現(xiàn)象形成一段時(shí)間后，會導(dǎo)致某條路徑的信息素濃度遠(yuǎn)高于其他路徑，此時(shí)大多數(shù)螞蟻會在該路徑上聚集，而該路徑即為螞蟻到食物源的最優(yōu)路徑［10］。蟻群算法的簡易原理如圖2所示。

如圖2所示，蟻穴到食物之間存在NACBF和NADBF兩條路徑。假設(shè)在螞蟻從蟻穴前往食物所在地的過程中速度相同且其在路過每一段路徑時(shí)都會分泌相同量的信息素，則螞蟻在圖2的覓食過程具體描述如下所示。假定共有16只螞蟻從蟻穴出發(fā)去食物F處，當(dāng)過去1個(gè)時(shí)刻時(shí)，所有螞蟻都移動(dòng)至A處，此時(shí)由于AC、AD兩條路徑上均無信息素，故有8只螞蟻選擇AD、8只螞蟻選擇AC。在4個(gè)時(shí)刻后8只通過ADB路徑的螞蟻率先找到食物F并返回蟻穴，返回途徑B點(diǎn)時(shí)因BC和BD的信息素濃度相同故選擇BD和BC路徑的螞蟻數(shù)量相同。在8個(gè)時(shí)刻后，經(jīng)過BDA返回蟻穴的4只螞蟻回到蟻穴，其他的螞蟻處于返回途中，其中BC中點(diǎn)處、AC中點(diǎn)處、D處各有4只螞蟻。而在9個(gè)時(shí)刻后，返回到蟻穴的4只螞蟻再次來到A處，此時(shí)AC和AD路徑上的信息素?cái)?shù)量分別為12和16，由于AD路徑上的信息素含量較多，這4只螞蟻將大概率選擇AD路徑前往食物F處。這將導(dǎo)致AD路徑的信息素含量進(jìn)一步增大，使得AD和AC路徑上的信息素濃度差距越來越大，隨著螞蟻覓食過程時(shí)間的增長，最終會導(dǎo)致所有螞蟻都聚集在NADBF這條較短的路徑上。通過蟻群算法可以找到農(nóng)村垃圾處理車運(yùn)輸?shù)淖疃搪窂?，從而減少運(yùn)輸成本。

1.2 蟻群算法的優(yōu)化及其在RGCR中的應(yīng)用

雖然傳統(tǒng)的蟻群算法可以對最優(yōu)路徑進(jìn)行求解，但其在實(shí)際的求解過程中仍存在收斂速度慢、優(yōu)化能力不足的問題。為了更好地利用蟻群算法對農(nóng)村垃圾回收最優(yōu)路徑進(jìn)行求解，對蟻群算法進(jìn)行了3個(gè)改進(jìn)得到混合蟻群算法（Hybrid ant colony algorithm，HACA）。HACA的第一個(gè)改進(jìn)是在蟻群算法的基礎(chǔ)上利用節(jié)約算法思想引入節(jié)約因子[uij]，在研究提出的RGCR模型中節(jié)約因子的計(jì)算原理如圖3所示。

圖3a的過程為從車場派出2輛垃圾車前往[i]、[j]? 2個(gè)農(nóng)村進(jìn)行垃圾回收，在垃圾回收后2輛垃圾車前往轉(zhuǎn)運(yùn)站傾倒垃圾，然后返回車場，圖3b的過程為從車場派出1輛垃圾車前往[i]、[j] 2個(gè)農(nóng)村進(jìn)行垃圾回收，利用該路徑的前提是垃圾車的承載量大于[i]、[j] 2個(gè)農(nóng)村的垃圾總量。而節(jié)約因子其實(shí)就是圖3b中的總里程數(shù)與圖3a中總里程數(shù)的差值，其表達(dá)式如式（1）所示。

[uij=din+dn1+d1j-dij]? ? ? （1）

式（1）中，[n]為垃圾轉(zhuǎn)運(yùn)站；[i]和[j]分別為2個(gè)農(nóng)村節(jié)點(diǎn)；[dij]表示2個(gè)農(nóng)村節(jié)點(diǎn)之間的距離。最大最小螞蟻系統(tǒng)（Max-min ant system，MMAS）通過只允許在最好的解中增加信息素來實(shí)現(xiàn)最優(yōu)路徑搜索。MMAS使用簡單的機(jī)制限制了信息素的增強(qiáng)，有效避免了搜索的過早收斂。將[uij]應(yīng)用于MMAS路徑選擇機(jī)制中，可以得到改進(jìn)混合蟻群算法的路徑選擇機(jī)制公式如式（2）所示。

[j=argmaxs∈allowedkτis（t）αηisβμisγ，q≤q0pkij（t）=τij（t）αηijβμisγs∈allowedkτis（t）αηisβμisγ，? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? j∈allowedk，q>q0? ? ? ? ? ? ? ? ? ? ? ?0，otherwise] （2）

式（2）中，[γ]為節(jié)約因子在路徑選擇過程中的重要程度；[k]為螞蟻；[t]為螞蟻訪問城市節(jié)點(diǎn)[i]的時(shí)刻；[j]為螞蟻[k]下一個(gè)需要訪問的城市節(jié)點(diǎn)；[s]表示訪問途中的城市節(jié)點(diǎn)；[η]表示啟發(fā)式因子；[α]和[β]分別表示路徑上的信息素濃度和啟發(fā)信息的相對重要性。HACA的第二個(gè)改進(jìn)之處為在螞蟻進(jìn)行食物搜尋時(shí)，將螞蟻分為探索性搜尋和確定性搜尋2類，將1/5的螞蟻用作探索性搜尋，剩余的螞蟻用作確定性搜尋，通過2種搜尋方式相結(jié)合的方式，對發(fā)現(xiàn)最優(yōu)解有所幫助。若螞蟻為探索性搜尋螞蟻，則按照隨機(jī)比例規(guī)則對下一個(gè)農(nóng)村節(jié)點(diǎn)進(jìn)行選擇，其選擇公式如式（3）所示。

[pkij（t）=τij（t）αηijβμisγs∈allowedkτis（t）αηisβμisγ，j∈allowedk，q>q0? ? ? ? 0，? ?otherwise] ? （3）

式（3）中，[α]為信息素重要程度；[β]為啟發(fā)信息重要程度。除此之外，HACA還選擇保留一部分父代最優(yōu)路徑，通過將其與此次最優(yōu)解相比較，在更優(yōu)的路徑中添加更多的信息素。這種方式不僅可以保留優(yōu)良基因，還在一定程度上擴(kuò)大了解的范圍，減慢了算法的收斂速度。若算法此次最優(yōu)解的長度為[Lbest]，次優(yōu)解長度為[L]，父代最優(yōu)解的長度為[Lfb]，當(dāng)路徑[（i，j）]在本次迭代最優(yōu)解中時(shí)，信息素增加量表達(dá)式如式（4）所示。

[Δτij=0.6×1Lbest] （4）

若路徑（i，j）不在本次迭代最優(yōu)解中時(shí)，則信息素額外增量的公式如式（5）所示。

[Δτ*ij=Δτfbij，Lfb≤LbestΔτ′ij，Lfb>Lbest] （5）

式（5）中，[Δτfbij]為路徑（i，j）在父代最優(yōu)解中時(shí)的信息素增加量，其表達(dá)式如式（6）所示。

[Δτfbij=0.4×1Lfb] （6）

式（5）中，[Δτ′ij]為路徑（i，j）在算法迭代最優(yōu)解中時(shí)的信息素增加量，其表達(dá)式如式（7）所示。

[Δτ′ij=0.4×1L] （7）

最終通過式（8）所示的表達(dá)式對路徑上的所有信息素進(jìn)行更新，在更新結(jié)束后對信息素的濃度進(jìn)行調(diào)整，然后確定是否結(jié)束迭代。

[τij（t+1）=（1-p）τij（t）+Δτij+Δτ*ij] （8）

式（8）中，[p]為信息素?fù)]發(fā)系數(shù)。通過改進(jìn)后的蟻群算法具有更好的收斂性和準(zhǔn)確性，其對農(nóng)村垃圾回收最優(yōu)路徑的求解具體過程如圖4所示。

如圖4所示，改進(jìn)后的蟻群算法運(yùn)行的第一步是對參數(shù)進(jìn)行初始化，然后確定螞蟻的編號，通過螞蟻編號確定其是否為探索性螞蟻，通過式（2）、式（3）分別對路徑進(jìn)行選擇，若形成路徑則繼續(xù)下一步，若未形成則重新確定編號。未形成m條路徑時(shí)，將螞蟻編號加1再次進(jìn)行輸入，在形成m條路徑后，對所有路徑的長度排序并找出最短路徑，將其與父代最優(yōu)解長度進(jìn)行對比，根據(jù)對比結(jié)果情況，利用式（4）至式（8）對路徑上的信息素增加量進(jìn)行計(jì)算，最后將信息素調(diào)整在上下限之內(nèi)，確定是否迭代結(jié)束，若結(jié)束則輸出路徑最優(yōu)解與對應(yīng)路徑，若未結(jié)束則繼續(xù)進(jìn)行算法。

2 農(nóng)村垃圾治理模型仿真試驗(yàn)結(jié)果分析

為了對研究提出的HACA性能進(jìn)行驗(yàn)證及對比，將其MMAS在2組算例中的測試結(jié)果進(jìn)行比較。2組算例的具體內(nèi)容如下所示。算例A中垃圾車的最大載重量為4 600 kg，節(jié)點(diǎn)共31個(gè)，1號節(jié)點(diǎn)為車場，31號節(jié)點(diǎn)為轉(zhuǎn)運(yùn)站，其他節(jié)點(diǎn)均為農(nóng)村節(jié)點(diǎn)；算例B中垃圾車的最大載重量為180 kg，節(jié)點(diǎn)共51個(gè)，1號節(jié)點(diǎn)為車場，51號節(jié)點(diǎn)為轉(zhuǎn)運(yùn)站，其他節(jié)點(diǎn)均為農(nóng)村節(jié)點(diǎn)。在測試算例A、B時(shí)，設(shè)置最大迭代次數(shù)200次；螞蟻規(guī)模為30；[α=1]；[β=2]；[γ=1]；[q0=0.2]。研究將HACA和MMAS在算例A、B中運(yùn)行10次，其結(jié)果對比如表1所示。

從表1中可以得到，在算例A中的10次運(yùn)行結(jié)果中，HACA的最大值為669.631 7，低于MMAS的最大值702.217 5，且HACA的最小值為623.157 9，低于MMAS的最小值662.378 5；在算例B中的10次運(yùn)行結(jié)果中，HACA的最大值為667.125 8，低于MMAS的最大值753.647 8，且HACA的最小值為619.356 4，低于MMAS的最小值668.247 9。該結(jié)果說明HACA搜尋到的最優(yōu)解最小，說明其路徑質(zhì)量更優(yōu)，也說明HACA搜尋最優(yōu)解的性能優(yōu)于MMAS。

除了對路徑結(jié)果進(jìn)行對比外，還對2種算法的收斂性進(jìn)行對比，其中改進(jìn)蟻群算法和最大最小螞蟻算法在算例A、B中的最優(yōu)解收斂性對比如圖5、圖6所示。

由圖5可知，HACA在算例A中迭代次數(shù)為130次時(shí)最優(yōu)值趨于穩(wěn)定，且最優(yōu)值穩(wěn)定在650左右；而MMAS在算例A中在迭代次數(shù)為200次時(shí)還未趨于穩(wěn)定，且數(shù)值在700～800附近波動(dòng)。該結(jié)果說明，HACA在算例A中的收斂性優(yōu)于MMAS，且最優(yōu)值也優(yōu)于MMAS，此結(jié)果也可以說明HACA搜尋最優(yōu)路徑的性能優(yōu)于MMAS。

由圖6可知，HACA在算例B中迭代次數(shù)為133次時(shí)最優(yōu)值趨于穩(wěn)定，且最優(yōu)值穩(wěn)定在650左右；而MMAS在算例B中在迭代次數(shù)為200次時(shí)還未趨于穩(wěn)定，且數(shù)值在700～900附近波動(dòng)。該結(jié)果說明，HACA在算例B中的收斂性優(yōu)于MMAS，且最優(yōu)值也優(yōu)于MMAS，此結(jié)果也可以說明HACA搜尋最優(yōu)路徑的性能優(yōu)于MMAS。通過上述結(jié)果可以得出HACA相較于MMAS可以更好地找到最優(yōu)路徑，且其更加穩(wěn)定，利用該方式對農(nóng)村垃圾回收路徑進(jìn)行確定，可以有效地減少運(yùn)輸成本。

3 小結(jié)

針對農(nóng)村垃圾回收最短路徑較難確定的問題，研究提出一種基于節(jié)約因子以及分工模式的改進(jìn)蟻群算法，通過將該算法與農(nóng)村垃圾回收路徑模式相結(jié)合，可得到農(nóng)村垃圾回收的最優(yōu)路徑。將優(yōu)化后的HACA與MMAS進(jìn)行仿真試驗(yàn)對比性能，結(jié)果顯示，HACA在算例A中結(jié)果的最大值和最小值分別為669.631 7和623.157 9，HACA在算例B中結(jié)果的最大值和最小值分別為667.125 8和619.356 4；均低于MMAS，且HACA在迭代次數(shù)為132次時(shí)趨于穩(wěn)定，且其最優(yōu)值在650左右，而MMAS在迭代次數(shù)為200次時(shí)還未穩(wěn)定。上述結(jié)果說明，進(jìn)行優(yōu)化后的蟻群算法HACA確定最優(yōu)路徑的性能明顯優(yōu)于MMAS，且其收斂速度也提高了，可以快速進(jìn)行收斂，從而提高整體性能。也說明利用HACA可以更好地對農(nóng)村垃圾回收最短路徑進(jìn)行精準(zhǔn)確定，從而減少政府的運(yùn)輸成本。雖然研究提出的算法具有較高的性能，但在研究過程中，只針對鎮(zhèn)轉(zhuǎn)運(yùn)進(jìn)行了研究，建立的模型較單一，后續(xù)將會對數(shù)學(xué)模型進(jìn)行完善，并對完善的數(shù)學(xué)模型中的蟻群算法進(jìn)行改進(jìn)。

參考文獻(xiàn)：

［1］ 曲 青，董立波，趙 濤. 精準(zhǔn)施策巧分類 垃圾治理成效顯［J］. 環(huán)境衛(wèi)生工程， 2022， 30（1）：90-93.

［2］ LI X R， BI F， HAN Z D， et al. Garbage source classification performance， impact factor， and management strategy in rural areas of China： A case study in Hangzhou［J］. Waste management， 2019， 89：313-321.

［3］ 屠 翰， 華永新， 徐 鋼，等. 杭州市農(nóng)村生活垃圾治理實(shí)踐及問題對策研究［J］. 農(nóng)業(yè)資源與環(huán)境學(xué)報(bào)， 2018， 35（3）：251-256.

［4］ MELLYANAWATY M，NAKAKOJI S，TATARA M，et al. Enrichment of thermophilic methanogenic microflora from mesophilic waste activated sludge for anaerobic digestion of garbage slurry［J］. Journal of bioscience and bioengineering， 2021， 132（6）：630-639.

［5］ KANSO B，KANSOU A，YASSINE A. Open Capacitated ARC routing problem by Hybridized Ant Colony Algorithm［J］. RAIRO-Operations research， 2021， 55（2）：639-652.

［6］ 陳 宇，王 彪. 基于改進(jìn)蟻群算法的二維MUSIC多譜峰搜索研究［J］. 聲學(xué)技術(shù)， 2021， 40（1）：128-133.

［7］ 李亞娟. “美麗鄉(xiāng)村”下的農(nóng)村生活垃圾治理影響因素研究［J］. 環(huán)境科學(xué)與管理， 2019， 44（7）：59-63.

［8］ 胡致遠(yuǎn)，王 征，楊 洋，等. 基于人工魚群-蟻群算法的UUV三維全局路徑規(guī)劃［J］. 兵工學(xué)報(bào)， 2022， 43（7）：1676-1684.

［9］ 陳東寧，劉一丹，姚成玉，等. 多階段自適應(yīng)蝙蝠-蟻群混合群智能算法［J］. 機(jī)械工程學(xué)報(bào)， 2021， 57（6）：236-248.

［10］ SALEH A I，ELKASAS M S， HAMZA A A. Ant colony prediction by using sectorized diurnal mobility model for handover management in PCS networks［J］. Wireless networks， 2019， 25（2）：765-775.

收稿日期：2022-10-13

基金項(xiàng)目：陜西省2021年度政務(wù)公開第三方評估項(xiàng)目（SCZC2021-CS -1289/001）

作者簡介：李 婷（1986-），女，陜西米脂人，講師，在讀碩士研究生，研究方向?yàn)樯鐣卫?、政?wù)公開，（電話）13991182045（電子信箱）935742690@qq.com。