DNA-蟻群算法在車輛路徑優(yōu)化問題中的應(yīng)用

劉 波（湖南人文科技學(xué)院，湖南 婁底 417100）

DNA-蟻群算法在車輛路徑優(yōu)化問題中的應(yīng)用

劉 波
（湖南人文科技學(xué)院，湖南 婁底 417100）

摘 要：隨著我國經(jīng)濟(jì)和科技的發(fā)展，物流配送已經(jīng)成為促進(jìn)經(jīng)濟(jì)發(fā)展的重要環(huán)節(jié)，在物流的配送過程中如何使用車輛路徑的優(yōu)化問題是長期困擾人們的難題，隨著群智能算法發(fā)展的今天，已經(jīng)有多種算法能夠應(yīng)用到車輛路徑的最優(yōu)化模擬的建立和計(jì)算中。本文通過對蟻群算法在路徑最優(yōu)模型的過程中的優(yōu)缺點(diǎn)進(jìn)行介紹。

關(guān)鍵詞：蟻群算法；最優(yōu)優(yōu)化；DNA算法

通過使用蟻群算法能夠建立起車輛路徑問題的模型，來解決長期困擾著人們的車輛路徑問題，但是在使用過程中發(fā)現(xiàn)， 蟻群算法在建立模型的過程中會(huì)出現(xiàn)過早收斂局部最優(yōu)解以及收斂時(shí)間周期長等缺點(diǎn)，同時(shí)在使用蟻群算法時(shí)需要對參數(shù)進(jìn)行相應(yīng)的選用，不然，為解決這一問題，通過使用DNA算法的精髓與蟻群算法向結(jié)合，在原有蟻群算法的基礎(chǔ)上進(jìn)一步發(fā)展，形成了DNA-蟻群算法。通過對改進(jìn)型的蟻群算法進(jìn)行了系統(tǒng)測試，發(fā)現(xiàn)其建立解決車輛路徑優(yōu)化問題的速度大幅提升，并且將原先蟻群算法存在的較早收斂于局部最優(yōu)解以及收斂速度較慢等問題加以解決。

1 蟻群算法簡介

蟻群算法是一種模擬螞蟻覓食行為的模擬優(yōu)化算法. 蟻群算法是一種基于種群的啟發(fā)式仿生進(jìn)化系統(tǒng)。蟻群算法最早成功應(yīng)用于解決著名的旅行商問題（TSP），該算法采用了分布式正反饋并行計(jì)算機(jī)制，易于與其他方法結(jié)合，而且具有較強(qiáng)的魯棒性。蟻群算法具有如下一些優(yōu)點(diǎn)：①通用性較強(qiáng)，能夠解決很多可以轉(zhuǎn)換為連通圖結(jié)構(gòu)的路徑優(yōu)化問題；②同時(shí)具有正負(fù)反饋的特點(diǎn)，通過正反饋特點(diǎn)利用局部解構(gòu)造全局解，通過負(fù)反饋特點(diǎn)也就是信息素的揮發(fā)來避免算法陷入局部最優(yōu)；③有間接通訊和自組織的特點(diǎn)，螞蟻之間并沒有直接聯(lián)系，而是通過路徑上的信息素來進(jìn)行間接的信息傳遞，自組織性使得群體的力量能夠解決問題。但是，基本蟻群算法也存在一些缺點(diǎn)：①從蟻群算法的復(fù)雜度來看，該算法與其他算法相比，所需要的搜索時(shí)間較長；②該算法在搜索進(jìn)行到一定程度以后，容易出現(xiàn)所有螞蟻所發(fā)現(xiàn)的解完全一致這種“停滯現(xiàn)象”，使得搜索空間受到限制。

蟻群算法原理圖如圖1、圖2、圖3和圖4所示。

圖1螞蟻正常行進(jìn)，突然環(huán)境改變，增加了障礙物

圖2螞蟻以等同概率選擇各條路徑，較短路徑信息素濃度高，選擇該路徑的螞蟻增多

圖3螞蟻選路過程示例

圖3螞蟻?zhàn)罱K繞過障礙物找到最優(yōu)路徑

2 最優(yōu)路徑所需研究的問題

最優(yōu)路徑所需要研究的問題主要是：在物流配送環(huán)境，在已知客戶的位置、貨物的種類和裝量的條件下，物理配送人員在給定的運(yùn)力條件下，如何使每一輛運(yùn)輸車輛從同一起點(diǎn)出發(fā)在完成所有運(yùn)輸任務(wù)的條件下能夠使用最少的車輛和行駛里程來完成配送任務(wù)，在這一過程中車輛的行駛路線不能重復(fù)。

3 蟻群算法中參數(shù)對于算法的影響

在蟻群算法中參數(shù)取值的不同會(huì)對算法的效率產(chǎn)生重大的影響，Q參數(shù)會(huì)對算法的收斂速度產(chǎn)生影響，如果其值過大將會(huì)使算法收斂于局部最小值，如果過小將會(huì)影響算法的收斂速度，而隨著問題規(guī)模的擴(kuò)大Q值也會(huì)隨著擴(kuò)大，α值大的小表明留在每個(gè)結(jié)點(diǎn)上的信息量受重視的程度，其值越大，蟻群選擇以前選過的點(diǎn)的可能性越大，但是如果值過大會(huì)使搜索過早陷入局部最小點(diǎn)，β的大小表明啟發(fā)式信息受重視的程度，如果值越大表明選擇路徑時(shí)越依賴啟發(fā)式信息，ρ值表明揮發(fā)程度，對收斂的結(jié)果有著重大的影響，經(jīng)過試驗(yàn)表明，在取值過大或者是過小的情況下運(yùn)行的結(jié)果都不理想，其值一般去在0.5左右。

4 DNA-蟻群算法在車輛最優(yōu)路徑中的問題求解

以上對蟻群算法的原理以及參數(shù)對于算法的影響，可以看出蟻群算法在求解車輛優(yōu)化路徑中的優(yōu)越性，但是在試驗(yàn)過程中發(fā)現(xiàn)，蟻群算法存在著收斂于局部最優(yōu)解且收斂速度較慢等問題。使用DNA算法能夠解決這一難題，DNA似乎脫氧核糖核酸的簡稱，其主要是由核苷酸組成，而DNA通常是由2條核苷酸組成，形成了雙螺旋結(jié)構(gòu)。DNA是由A、T、C、G組成的，在DNA算法中使用A、T、C、 G交叉配對且用一定的概率實(shí)現(xiàn)兩點(diǎn)交叉的方法，意思就是說通過對一段DNA片段更換任意一部分核苷酸來形成新的DNA鏈，DNA算法具有良好的替換性，同時(shí)采用DNA算法與蟻群算法進(jìn)行結(jié)合來提高了蟻群算法中對于參數(shù)的控制，提高了算法的效率，其具體的DNA-蟻群算法的求解步驟如下：（1）使用DNA算法來優(yōu)化參數(shù)，建立起蟻群算法中參數(shù)的參數(shù)矩陣，（2）使用DNA算法對這些參數(shù)進(jìn)行變異交叉對比，（3）使用蟻群算法進(jìn)行車輛最優(yōu)路徑的模型建立以及問題求解。（4）在試驗(yàn)時(shí)選用不同的參數(shù)進(jìn)行變異交叉對比來選用合理的蟻群算法參數(shù)。

結(jié)語

蟻群算法是一種車輛最優(yōu)路徑問題中良好的求解方式，使用DNA算法與蟻群算法相結(jié)合，形成了DNA-蟻群算法，使用兩種算法相結(jié)合的方式來提高對于蟻群算法中參數(shù)的選取效率，使用蟻群算法中的參數(shù)選取更能符合蟻群算法的需求。

參考文獻(xiàn)

[1]曾云.基于改進(jìn)蟻群算法的物流配送路徑優(yōu)化研究[J].北京物資學(xué)院，2012 （02）.

[2]樊曉平，羅熊，張航.復(fù)雜環(huán)境下基于蟻群優(yōu)化算法的機(jī)器人路徑規(guī)劃[J].控制與決策，2004（19）.

[3]王占鋒，杜海蓮，安素芳，等.求解車輛路徑問題的改進(jìn)蟻群算法[J].華僑大學(xué)學(xué)報(bào)，2013（34）.

中圖分類號(hào)：TP3

文獻(xiàn)標(biāo)識(shí)碼：A