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

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

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

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

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

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

1 蟻群算法簡(jiǎn)介

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

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

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

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

圖3螞蟻選路過(guò)程示例

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

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

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

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

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

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

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

結(jié)語(yǔ)

蟻群算法是一種車輛最優(yōu)路徑問(wèn)題中良好的求解方式，使用DNA算法與蟻群算法相結(jié)合，形成了DNA-蟻群算法，使用兩種算法相結(jié)合的方式來(lái)提高對(duì)于蟻群算法中參數(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]王占鋒，杜海蓮，安素芳，等.求解車輛路徑問(wèn)題的改進(jìn)蟻群算法[J].華僑大學(xué)學(xué)報(bào)，2013（34）.

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

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