單親遺傳算法的改進及用于城市垃圾回收路線優化

楊帆

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

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

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

1 概述

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

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

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

2 單親遺傳算法的優化

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

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

（1）“擇優插入法”產生初始群體

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

（2）選擇精英保留策略

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

（3）遺傳迭代終止規則

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

3 實驗結果驗證及分析

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

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

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

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

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

4 結論

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

參考文獻：

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

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

[3]晏夢君.遺傳算法在派送路線優化系統中的應用[D].吉林大學，2005.

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

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