楊帆

摘 要：改進垃圾收集轉運方式能夠有效地提高垃圾轉運效率，文章對現有的單親遺傳算法進行改進，提出了擇優(yōu)插入、精英保留等策略。改進后的算法可以進一步優(yōu)化垃圾收運路線，提高收運效率，并將其運用到實際的垃圾收運路線優(yōu)化中。

關鍵詞：單親遺傳算法；垃圾回收路線優(yōu)化；改進

中圖分類號：R124.3 文獻標志碼：A 文章編號：2095-2945（2017）23-0077-02

1 概述

據《中國統(tǒng)計年鑒》（2014年），中國共有建制城市657個，城市生活垃圾清運量已經達到17860.2萬噸[1]。制定合理的垃圾收運方案，及時清運垃圾，可以減少垃圾回收清運費用，并減少對環(huán)境的污染。

從目標函數和建模思路來看，城市垃圾收運路線的優(yōu)化問題為車輛調度問題，屬于組合優(yōu)化問題。其實質是對一系列裝貨點和（或）卸貨點，組織適當的行車線路，使車輛有序地通過它們，在滿足一定的約束條件，如車輛容量、行駛里程、時間等限制因素，達到一定的目標如路程最短、費用最少、使用車輛數量盡量少等。

王文梅[2]提出利用單親遺傳算法對垃圾回收路線進行優(yōu)化，本文針對這一算法進行了改進，很大程度上避免了傳統(tǒng)遺傳算法存在的“早熟收斂”等問題。本算法從傳統(tǒng)物流路線優(yōu)化方面得到啟發(fā)，并通過java語言編譯，形成一套新的“垃圾回收路線優(yōu)化算法”。

2 單親遺傳算法的優(yōu)化

遺傳算法（Genetic Algorithm，GA）是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應全局優(yōu)化概率搜索算法[3]，即適者生存、優(yōu)勝劣汰的遺傳機制。目前的基本遺傳算法是由Goldberg統(tǒng)一了各種編碼方式和遺傳算子[4]，只使用了選擇、交叉、變異三種基本遺傳算子構成完備的算子集合，其遺傳過程簡單，容易理解，是其他遺傳算法的基礎，不僅給各種遺傳算法提供了一個基本框架，同時也具有很高的應用價值。

本文對單親遺傳算法進行了以下改進：

（1）“擇優(yōu)插入法”產生初始群體

初始群體染色體的好壞對于整個群體的進化效率有很大的影響。本算法在產生初始群體的時候，采用“擇優(yōu)插入法”，提高收斂效率。

（2）選擇精英保留策略

在選擇操作中加入精英保留策略，即在使用變異、交叉算子之前先選出適應度值最大的個體保存在最優(yōu)解中。在本算法的每個群體的第一個位置為“精英保留區(qū)”，每次進行遺傳操作時，如果得到的個體適應度值比“精英保留區(qū)”中的個體的適應度大的時候，就復制該個體到“精英保留區(qū)”中，這樣每一代出現的最優(yōu)個體都會被保留。

（3）遺傳迭代終止規(guī)則

若連續(xù)Q代內都滿足條件| fgmax-f（g-1）max|≤ε，其中 ε為適當小的正數，fgmax為第g代種群內個體的最大適應度值，f（g-1）max為第g-1代種群內個體的最大適應度值。一般進化結果趨于平穩(wěn)時，則可以認為是一個最優(yōu)解。所以本算法為了減少運行時間，增大開發(fā)效率，優(yōu)化了停機規(guī)則。

3 實驗結果驗證及分析

本文算法倒位變異概率為0.75，變異概率為0.02。程序用java編寫。

與其他文獻中的結果對比：

按文獻[5]可將問題描述為：在某市有12個垃圾收集點，1個垃圾集中處置點，收集點的垃圾量、各個收集點之間的距離（單位：公里）如表1所示。這些收集點由垃圾處置點處的載重量為8噸的垃圾收集車收集，要求合理完成安排車輛的行車路線，使得行程最短。

文獻[5]中使用的是單親遺傳算法的多點換位算子，選擇算子使用的是保留最佳個體方法；文獻[3]中使用的是帶“放哨”的遺傳算法。表2顯示了當進化100代時文獻[5]中的單親遺傳算法、保留最佳個體的基因移位變異算法、保留最佳個體的基因倒位算法和文獻[3]中的算法，以及本優(yōu)化算法之間的比較。

本文算法從三個方面對單親遺傳算法進行了改進，取得了較好的結果，達到了縮短運輸距離及高效節(jié)能的目標。

4 結論

本文將傳統(tǒng)的單親遺傳算法進行了優(yōu)化，主要從初始種群的創(chuàng)建、精英保留策略和遺傳迭代終止規(guī)則進行了優(yōu)化，并與參考文獻的結果進行了比較，驗證了本算法的可行性。本文算法存在的不足是沒有考慮到存在多個處置點的情況，沒有考慮車輛不同載重量的情況，沒有將油耗情況結合起來，只是考慮路徑長短的問題。

參考文獻：

[1]中華人民共和國國際統(tǒng)計局.中國統(tǒng)計年鑒2015年[M].北京：中國統(tǒng)計出版社，2015.

[2]王文梅.基于單親遺傳算法的城市垃圾收運路線優(yōu)化的研究[D].西南交通大學，2005.

[3]晏夢君.遺傳算法在派送路線優(yōu)化系統(tǒng)中的應用[D].吉林大學，2005.

[4]張超群，鄭建國，錢潔.遺傳算法編碼方式比較[J].計算機應用研究，2011（3）：819-822.

[5]李茂軍，朱陶業(yè)，童調生.單親遺傳算法與傳統(tǒng)遺傳算法的比較[J].系統(tǒng)工程，2001，19（1）：61-65.endprint