基于改進(jìn)單親遺傳算法的車輛路徑優(yōu)化問題研究

陳曉桐

摘 要：單親遺傳算法隨著種群的進(jìn)化，單親遺傳算法的突變、逆序、變異使得算法在局部搜索的能力逐步減弱。為了克服該缺點(diǎn)，文中提出了一種基于貪心思想的重組算子。在進(jìn)化過程中它不斷地對(duì)父代和子代的染色體進(jìn)行篩選，保留最優(yōu)，加快了整體的收斂速度。

關(guān)鍵詞：VRP；PGA；貪心算法

DOI：10.16640/j.cnki.37-1222/t.2018.19.182

1 單親遺算法

單親遺算法（PGA）是通過選擇和變異算子繁衍后代，取消了傳統(tǒng)序號(hào)編碼GA的交叉算子，只在一條染色體上操作基因重組的遺傳算法，簡化了操作，提高了計(jì)算效率，并且不需要出示群體的多樣性，也不存在“早熟收斂”，是一種適合求解組合問題的新型遺傳算法[1]。

2 單親遺傳算法的改進(jìn)

引入貪心算法，進(jìn)行局部調(diào)整操作。即在進(jìn)行變異操作后，對(duì)變異后的個(gè)體進(jìn)行適應(yīng)度值計(jì)算，如果適應(yīng)度大于上一代的適應(yīng)度值，變異后個(gè)體代替變異前個(gè)體，否則放棄變異后個(gè)體，保留原先個(gè)體。通過此種方法的局部尋優(yōu)，找到局部最優(yōu)。因此，在求VRP時(shí)，既利用單親遺傳算法的優(yōu)勢(shì)來確保全局搜索的能力，又利用了貪心算子來保證局部搜索能力。這種混合型算法，不僅使收斂速度得到提高，還能夠盡可能快的尋求到問題的最優(yōu)解。

3 基于改進(jìn)PGA的VRP問題研究

3.1 問題描述及模型建立

本文研究對(duì)象是物流中心，n個(gè)零售商，m輛運(yùn)輸車輛，每個(gè)零售需求量為Ci。假定每輛車容量為Q，零售商有優(yōu)先級(jí)，配送成本分為固定和可變成本。其優(yōu)化的目標(biāo)是在滿足需求，求車輛的運(yùn)貨路線，使得總運(yùn)輸成本最低。根據(jù)約束條件和參數(shù)變量，數(shù)學(xué)表達(dá)式如下：

（1）

s.t

（2）

（3）

當(dāng)時(shí)， （4）

3.2 關(guān)鍵算法的設(shè)計(jì)

3.2.1 適應(yīng)度值計(jì)算

GA中最重要的數(shù)據(jù)是適應(yīng)度值。是進(jìn)化時(shí)優(yōu)勝劣汰的依據(jù)。計(jì)算過程如下：

（1） i=1，v=1；（2） 按照個(gè)體中零售商編號(hào)依次將第i次序的零售商加入到車v的配送路線中；（3）若車v運(yùn)輸貨物量總和超過車輛運(yùn)載量，至步驟4，否則轉(zhuǎn)至步驟2，且i=i+1；（4）將配送路線中的零售商按優(yōu)先級(jí)進(jìn)行排序；（5）計(jì)算車v配送成本；（6） v=v+1；（7）若配送車輛已用完，或者所有零售商都已得到配送，則結(jié)束，輸出適應(yīng)度，否則回到步驟2。

3.2.2 變異算子

本文中采用帶貪心算法的基因串逆轉(zhuǎn)算子，具體過程如下：（1）隨機(jī)選擇一段基因串片段；（2）將選擇的基因串片段逆序翻轉(zhuǎn)；（3）計(jì)算變異后的個(gè)體適應(yīng)度，如果大于變異前個(gè)體適應(yīng)度，則用變異后個(gè)體代替變異前個(gè)體，否則放棄編譯后個(gè)體。

3.2.3 改進(jìn)后的單親遺傳算法的步驟

（1）初始種群的產(chǎn)生；（2）計(jì)算初始群體的個(gè)體的適應(yīng)值；（3）保留最優(yōu)個(gè)體；（4）輪盤賭算法選擇子代個(gè)體；（5）采用貪心算法思想，利用基因串逆轉(zhuǎn)操作進(jìn)行個(gè)體的變異，只將變異后適應(yīng)度得到改進(jìn)的染色體保留；（6）完成群體的更新，新群體由保留下來的最優(yōu)解個(gè)體和新的個(gè)體組成；（7）將初始設(shè)定的代數(shù)作為判斷運(yùn)算是否終止的依據(jù)，滿足終止條件，則終止運(yùn)算，并輸出結(jié)果，否則返回到步驟2。

四 實(shí)證分析

本文案例中，車輛數(shù)量為5，運(yùn)載量為15，啟動(dòng)成本為30。種群規(guī)模取m=30，最大迭代次數(shù)為300，零售商的需求量為[1 4 2 1 2 3 4 1 1 2 3 2 1 2 3 4 3 4 2 3 1 4 3 2 4 2 1 4 3 2]，配送優(yōu)先級(jí)為[1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 2 2 2 2]得出配送總成：758.36。

為了驗(yàn)證改進(jìn)單親遺傳算法在車輛路徑問題的優(yōu)勢(shì)，本文做了仿真比較。由圖2可以看出改進(jìn)遺傳算法的收斂速性和解的精確度方面都高于基本的單親遺傳算。所以改進(jìn)單親遺傳引入貪心算法，能提前獲得大量的優(yōu)良基因，所花時(shí)間、迭代次數(shù)和最優(yōu)結(jié)果等方面都優(yōu)于一般GA。

參考文獻(xiàn)：

[1]占焱發(fā).基于遺傳算法的物流配送車輛路徑問題研究[D].北京交通大學(xué)博士學(xué)位論文2010.

[2]傅成紅.多周期庫存路徑問題及其算法研究[D].中南大學(xué)博士學(xué)位論文，2010.