DNA-蟻群算法在車輛路徑優化問題中的應用

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

DNA-蟻群算法在車輛路徑優化問題中的應用

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

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

關鍵詞：蟻群算法；最優優化；DNA算法

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

1 蟻群算法簡介

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

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

圖1螞蟻正常行進，突然環境改變，增加了障礙物

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

圖3螞蟻選路過程示例

圖3螞蟻最終繞過障礙物找到最優路徑

2 最優路徑所需研究的問題

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

3 蟻群算法中參數對于算法的影響

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

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

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

結語

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

參考文獻

[1]曾云.基于改進蟻群算法的物流配送路徑優化研究[J].北京物資學院，2012 （02）.

[2]樊曉平，羅熊，張航.復雜環境下基于蟻群優化算法的機器人路徑規劃[J].控制與決策，2004（19）.

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

中圖分類號：TP3

文獻標識碼：A