李婷

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

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

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

中圖分類號：F799.3? ? ? ? ?文獻標識碼：A

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

DOI：10.14088/j.cnki.issn0439-8114.2024.03.038 開放科學（資源服務）標識碼（OSID）：

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

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

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

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

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

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

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

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

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

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

式（1）中，[n]為垃圾轉(zhuǎn)運站；[i]和[j]分別為2個農(nóng)村節(jié)點；[dij]表示2個農(nóng)村節(jié)點之間的距離。最大最小螞蟻系統(tǒng)（Max-min ant system，MMAS）通過只允許在最好的解中增加信息素來實現(xiàn)最優(yōu)路徑搜索。MMAS使用簡單的機制限制了信息素的增強，有效避免了搜索的過早收斂。將[uij]應用于MMAS路徑選擇機制中，可以得到改進混合蟻群算法的路徑選擇機制公式如式（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é)點[i]的時刻；[j]為螞蟻[k]下一個需要訪問的城市節(jié)點；[s]表示訪問途中的城市節(jié)點；[η]表示啟發(fā)式因子；[α]和[β]分別表示路徑上的信息素濃度和啟發(fā)信息的相對重要性。HACA的第二個改進之處為在螞蟻進行食物搜尋時，將螞蟻分為探索性搜尋和確定性搜尋2類，將1/5的螞蟻用作探索性搜尋，剩余的螞蟻用作確定性搜尋，通過2種搜尋方式相結合的方式，對發(fā)現(xiàn)最優(yōu)解有所幫助。若螞蟻為探索性搜尋螞蟻，則按照隨機比例規(guī)則對下一個農(nóng)村節(jié)點進行選擇，其選擇公式如式（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)良基因，還在一定程度上擴大了解的范圍，減慢了算法的收斂速度。若算法此次最優(yōu)解的長度為[Lbest]，次優(yōu)解長度為[L]，父代最優(yōu)解的長度為[Lfb]，當路徑[（i，j）]在本次迭代最優(yōu)解中時，信息素增加量表達式如式（4）所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 小結

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

參考文獻：

［1］ 曲 青，董立波，趙 濤. 精準施策巧分類 垃圾治理成效顯［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)村生活垃圾治理實踐及問題對策研究［J］. 農(nóng)業(yè)資源與環(huán)境學報， 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］ 陳 宇，王 彪. 基于改進蟻群算法的二維MUSIC多譜峰搜索研究［J］. 聲學技術， 2021， 40（1）：128-133.

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

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

［9］ 陳東寧，劉一丹，姚成玉，等. 多階段自適應蝙蝠-蟻群混合群智能算法［J］. 機械工程學報， 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

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

作者簡介：李 婷（1986-），女，陜西米脂人，講師，在讀碩士研究生，研究方向為社會治理、政務公開，（電話）13991182045（電子信箱）935742690@qq.com。