單親遺傳算法的改進(jìn)及用于城市垃圾回收路線優(yōu)化

楊帆

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

關(guān)鍵詞：?jiǎn)斡H遺傳算法；垃圾回收路線優(yōu)化；改進(jìn)

中圖分類號(hào)：R124.3 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：2095-2945（2017）23-0077-02

1 概述

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

從目標(biāo)函數(shù)和建模思路來(lái)看，城市垃圾收運(yùn)路線的優(yōu)化問(wèn)題為車(chē)輛調(diào)度問(wèn)題，屬于組合優(yōu)化問(wèn)題。其實(shí)質(zhì)是對(duì)一系列裝貨點(diǎn)和（或）卸貨點(diǎn)，組織適當(dāng)?shù)男熊?chē)線路，使車(chē)輛有序地通過(guò)它們，在滿足一定的約束條件，如車(chē)輛容量、行駛里程、時(shí)間等限制因素，達(dá)到一定的目標(biāo)如路程最短、費(fèi)用最少、使用車(chē)輛數(shù)量盡量少等。

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

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

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

本文對(duì)單親遺傳算法進(jìn)行了以下改進(jìn)：

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

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

（2）選擇精英保留策略

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

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

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

3 實(shí)驗(yàn)結(jié)果驗(yàn)證及分析

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

與其他文獻(xiàn)中的結(jié)果對(duì)比：

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

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

本文算法從三個(gè)方面對(duì)單親遺傳算法進(jìn)行了改進(jìn)，取得了較好的結(jié)果，達(dá)到了縮短運(yùn)輸距離及高效節(jié)能的目標(biāo)。

4 結(jié)論

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

參考文獻(xiàn)：

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

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

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

[4]張超群，鄭建國(guó)，錢(qián)潔.遺傳算法編碼方式比較[J].計(jì)算機(jī)應(yīng)用研究，2011（3）：819-822.

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