車輛路徑問(wèn)題的改進(jìn)遺傳算法.pdf

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

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

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

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