車輛路徑問題的改進遺傳算法.pdf

1、在計算機飛速發(fā)展的今天，車輛路徑問題(Vehicle Routing Problems，簡稱VRP)一直以來是眾多計算機學者研究的焦點。如何針對車輛路徑問題的特點，構(gòu)造運算簡單、性能優(yōu)異的啟發(fā)式算法，對物流系統(tǒng)及許多可以轉(zhuǎn)化為車輛路徑問題的組合優(yōu)化問題都有十分重要的意義。因此，本文針對傳統(tǒng)遺傳算法求解車輛路徑問題所存在的不足，將《作物育種學》中的理論分別應(yīng)用于目前遺傳算法求解車輛路徑問題的兩種最典型的算法：即廣泛使用的單種群遺傳算法和尋

2、優(yōu)效率較高的雙種群遺傳算法，并通過仿真實驗驗證了本文所設(shè)計的算法的性能。本文研究內(nèi)容及成果如下： ①針對傳統(tǒng)遺傳算法在求解車輛路徑問題中存在的“早熟收斂”、易陷入局部極值點等不足，本文提出了將作物育種學中的差異性原理應(yīng)用于遺傳算法求解車輛路徑問題的算法設(shè)計中的改進思路。我們將該原理應(yīng)用到單種群遺傳算法交叉前的父染色體選擇過程，以及雙種群遺傳算法的種群交叉過程，通過模擬自然界中的進化規(guī)律來提高遺傳算法的優(yōu)化性能。 ②基于上

3、述改進思路，本文設(shè)計了一種改進的單種群遺傳算法。該算法通過采用新的父染色體選擇策略以及新的交叉算子，能夠保證一對適應(yīng)值有一定差異的染色體進行交叉，使產(chǎn)生的后代性狀分離。這樣就可以增加種群中個體的多樣性，擴展解的搜索空間，避免過早陷入局部最優(yōu)，在優(yōu)化性能的提高方面取得更好的效果。 ③基于上述改進思路，本文還設(shè)計了一種改進的雙種群遺傳算法。該算法采用了一種新的種群交叉策略，主要是針對種群間互換染色體這一步驟，對傳統(tǒng)的雙種群遺傳算法做

4、了改進。同時還提出了一種新的染色體交叉與變異策略，讓兩個種群使用不同的交叉和變異算子，以及不同的交叉和變異概率。通過新的種群交叉策略的引入和新的染色體交叉與變異策略的引入，改進后的算法能更有效地模擬現(xiàn)實物種進化過程，以保證種群內(nèi)物種多樣性，有利于整個種群的進化。 ④采用廣泛使用的標準測試數(shù)據(jù)，對本文提出的單種群遺傳算法和雙種群遺傳算法與傳統(tǒng)遺傳算法作了較為充分的實驗測試和對比分析。實驗結(jié)果表明，文中的方法能更為有效的求得車輛路徑