《車輛路徑問題求解算法分析綜述》2000字

車輛路徑問題求解算法分析綜述1.1算法概述車輛路徑問題一般會有多個約束條件疊加，這會增加問題求解的復(fù)雜程度，所以此類問題屬于NP難題，針對車輛路徑問題的求解算法從早期的精確算法逐漸發(fā)展到大規(guī)模的智能優(yōu)化算法。根據(jù)目前的研究成果，求解此類問題的方法總體上可分為精確算法和啟發(fā)式算法，具體如圖2-1所示REF_Ref25478\r\h[1]。圖2-1VRP問題的常用求解算法精確算法精確算法可以在有限的計(jì)算步驟內(nèi)求出問題的最優(yōu)解，但計(jì)算時間會隨著問題規(guī)模的增加以指數(shù)速度上升，所以只適用于規(guī)模較小的問題。由于實(shí)際問題具有系統(tǒng)性與復(fù)雜性，尤其是針對車輛路徑問題等NP難題而言，使用精確算法所產(chǎn)生的成本可能是無法接受甚至不現(xiàn)實(shí)的，不適合大多數(shù)的配送模型。傳統(tǒng)啟發(fā)式算法為了在可接受的計(jì)算成本范圍內(nèi)進(jìn)行復(fù)雜問題的求解，學(xué)者引入了啟發(fā)式算法。此類方法要求研究人員通過經(jīng)驗(yàn)總結(jié)、實(shí)驗(yàn)分析等方式對求解過程進(jìn)行引導(dǎo)，使得可以在較短時間內(nèi)找到可接受的滿意解。傳統(tǒng)啟發(fā)式算法需要針對具體問題模型設(shè)計(jì)相應(yīng)的算法，通常用來解決組合優(yōu)化問題，具有計(jì)算速度快、程序較為簡單等優(yōu)點(diǎn)。但是由于搜索范圍的局限性，該方法無法保證求得最優(yōu)解。同時，傳統(tǒng)啟發(fā)式算法是通過局部搜索技術(shù)找到滿意解的，容易陷入局部最優(yōu)。亞啟發(fā)式算法亞啟發(fā)式算法又稱元啟發(fā)式算法，通過全局搜索獲取滿意解，找到全局最優(yōu)解的概率更高。此類算法是以自然界或人類社會中的一些智能現(xiàn)象為基礎(chǔ)產(chǎn)生的，例如遺傳算法源于自然界中生物的遺傳、自然選擇等進(jìn)化規(guī)律，蟻群算法源于螞蟻在覓食過程中的群體行為，粒子群算法源于鳥群的捕食行為，模擬退火算法源于熱力學(xué)中固體的退火過程。1.2遺傳算法算法原理遺傳算法是一種可以實(shí)現(xiàn)全局優(yōu)化的自適應(yīng)概率搜索算法，主要啟于生物進(jìn)化中“適者生存”的規(guī)律，即自然環(huán)境中適應(yīng)能力越高的群體往往會產(chǎn)生更加優(yōu)秀的后代。通過模擬個體交叉和染色體基因突變等現(xiàn)象產(chǎn)生候選解，然后按照一定原則從中選擇較優(yōu)的個體，不斷重復(fù)上述操作，直至得到達(dá)到終止條件的滿意解。算法組成要素編碼：將優(yōu)化問題的解轉(zhuǎn)變成位串的形式，便于解的表達(dá)和計(jì)算。主要方式有二進(jìn)制編碼、格雷編碼、序列編碼和大字符集編碼等。適應(yīng)度函數(shù)：是個體優(yōu)劣的唯一評價指標(biāo)，應(yīng)結(jié)合求解問題的要求設(shè)定。該值越大說明相應(yīng)個體的質(zhì)量越好，則被遺傳到下一代群體的概率更高。遺傳算子：包括選擇算子、交叉算子和變異算子。選擇算子是根據(jù)個體的適應(yīng)度，按照一定規(guī)則選擇性能優(yōu)良的父代，常用方法包括輪盤賭選擇、超比例選擇、種馬進(jìn)化算法、錦標(biāo)賽選擇等；交叉算子是將群體中挑選出的個體隨機(jī)搭配成對，通過互換個體間的部分染色體進(jìn)而產(chǎn)生新個體，常用的交叉方法包括單點(diǎn)交叉、多點(diǎn)交叉、均勻交叉、洗牌交叉等；變異算子是按照變異概率更改個體數(shù)據(jù)串中的部分值，由此可減少種群規(guī)模較小導(dǎo)致的近親繁殖的情況。變異概率對算法性能的影響很大，該值過高會趨向于隨機(jī)搜索，過低會導(dǎo)致近親繁殖等問題，難以找到滿意解?？刂茀?shù)：包括初始種群的個數(shù)、交叉概率、變異概率及遺傳操作的終止條件等。其中，終止條件主要包括：算法進(jìn)化代數(shù)達(dá)到預(yù)定值；遺傳搜索找到較為理想的目標(biāo)值；個體的適應(yīng)度函數(shù)值趨于穩(wěn)定，即種群難以繼續(xù)優(yōu)化。算法步驟遺傳算法步驟如圖2-2所示。圖2-2遺傳算法步驟算法優(yōu)點(diǎn)并行計(jì)算，全局搜索能力強(qiáng)。遺傳算法是對由多個體組成的群體進(jìn)行操作處理，即可以同時使用多個搜索點(diǎn)的信息，在一次搜索循環(huán)中可以覆蓋到較大規(guī)模的個體，在全局搜索方面有明顯的優(yōu)勢，適合復(fù)雜性問題。適用范圍廣。遺傳算法通過適應(yīng)度函數(shù)即可得到進(jìn)一步的搜索方向和搜索范圍，而且對目標(biāo)函數(shù)的限制條件極少，因此該算法適合于目標(biāo)函數(shù)無法求導(dǎo)或?qū)?shù)不存在的優(yōu)化問題及優(yōu)化組合問題。具有很好的靈活性。遺傳算法的選擇、交叉、變異操作可通過參數(shù)設(shè)定進(jìn)行控制的，對操作算子進(jìn)行優(yōu)化，可以引導(dǎo)種群會產(chǎn)生更多優(yōu)良的個體。算法缺點(diǎn)容易陷入局部最優(yōu)，出現(xiàn)“早熟”現(xiàn)象。遺傳算法是通過交叉操作和變異操作產(chǎn)生新個體的，但在算法后期，優(yōu)勢個體可能占據(jù)大部分種群、交叉操作難以產(chǎn)生新個體；此時變異操作又受到變異概率的限制，則會出現(xiàn)過早收斂的情況，導(dǎo)致算法的最終解并非滿意解。無法保證每次都收斂到相同的解。由于遺傳算法會受到隨機(jī)概率的影響，所以無法保證算法解的良好收斂性。1.3模擬退火算法算法原理模擬退火算法源自于固體退火現(xiàn)象，首先在高溫下進(jìn)行粗略搜索，可以快速進(jìn)入“熱平衡”狀態(tài)，然后隨著溫度逐漸減低，各狀態(tài)出現(xiàn)概率的差距逐漸擴(kuò)大，搜索精度提高，使收斂到全局最小點(diǎn)。該算法的優(yōu)勢就是具有概率突跳特性，即能夠以一定概率接受差解，在得到局部最優(yōu)解后可以繼續(xù)尋優(yōu)，最終實(shí)現(xiàn)全局最優(yōu)。算法步驟該算法使用Metropolis準(zhǔn)則判斷是否接受新解，即當(dāng)新解優(yōu)于原解時，選擇接受新解；當(dāng)新解劣于原解時，以概率exp(??fTi圖2-3模擬退火算法步驟算法特點(diǎn)局部搜索能力強(qiáng)。模擬退火