蟻群算法在車輛路徑問題中的應(yīng)用.doc

蟻群算法在車輛路徑問題中的應(yīng)用摘 要蟻群算法（Ant Colony Optimization, ACO）是意大利學(xué)者M(jìn).Dorigo等人通過模擬蟻群覓食行為提出的一種基于種群的模擬進(jìn)化算法。通過介紹蟻群覓食過程中基于信息素（pheromone）的最短路徑的搜索策略，給出了基于MATLAB的蟻群算法在車輛路徑問題（Vehicle Routing Problem, VRP）中的應(yīng)用。蟻群算法采用分布式并行計算機(jī)制，易于其他方法結(jié)合，而且具有較強(qiáng)的魯棒性，但搜索時間長，容易陷入局部最優(yōu)解。針對蟻群算法存在的過早收斂問題，加入2opt方法對問題求解進(jìn)行了局部優(yōu)化，計算機(jī)仿真結(jié)果表明，這種混合型蟻群算法對求解車輛路徑問題有較好的改進(jìn)效果。關(guān)鍵詞：蟻群算法、 組合優(yōu)化、車輛路徑問題、2-opt方法 1. 車輛路徑問題車輛路徑問題（VRP）來源于交通運輸，1959年由Dantzig提出，它是組合優(yōu)化問題中一個典型的NP-hard問題。最初用于研究亞特蘭大煉油廠向各個加油站投送汽油的運輸路徑優(yōu)化問題，并迅速成為運籌學(xué)和組合優(yōu)化領(lǐng)域的前沿和研究熱點。車路優(yōu)化問題如下：已知有一批客戶，各客戶點的位置坐標(biāo)和貨物需求已知，供應(yīng)商具有若干可供派送的車輛，運載能力給定，每輛車都是從起點出發(fā)，完成若干客戶點的運送任務(wù)后再回到起點?，F(xiàn)要求以最少的車輛數(shù)和最少的車輛總行程來完成貨物的派送任務(wù)。2、蟻群系統(tǒng)基本原理 在螞蟻群找到食物時，它們總能找到一條從食物到蟻穴之間的最短路徑。因為螞蟻在尋找食物時會在路途上釋放一種特殊的信息素。當(dāng)它們碰到一個還沒有走過的路口時，會隨機(jī)地挑選一條路徑前行。與此同時釋放出與路徑長度有關(guān)的信息素。路徑越長，釋放的激素濃度越低。當(dāng)后面的螞蟻再次碰到這個路口時，會選擇激素濃度較高的路徑走。這樣形成了一個正反饋，最優(yōu)路徑上的激素濃度越來越高，而其他的路徑上激素濃度卻會隨時間的流逝而消減。最終整個蟻群會找出最優(yōu)路徑。在整個尋找過程中，整個蟻群通過相互留下的信息素作用交換著路徑信息，最終找到最優(yōu)路徑。3、 基本蟻群算法求解車輛路徑問題 求解VRP問題的螞蟻算法中，每只螞蟻是一個獨立的用于構(gòu)造路線的過程，若干螞蟻過程之間通過信息素值來交換信息，合作求解，并不斷優(yōu)化。這里的信息素值分布式存儲在圖中，與各弧相關(guān)聯(lián)。螞蟻算法求解VRP問題的過程如下:(1) 參數(shù)初始化。令t=0和循環(huán)次數(shù)也NC=0，設(shè)置最大循環(huán)次數(shù)NCmax。，將m只螞蟻隨機(jī)地放到n個城市，將每條邊(i,j)上的信息素設(shè)為一個常數(shù)，且=0（表示循環(huán)中路徑(i,j)上的信息素增量），將出發(fā)點城市設(shè)置到禁忌表中；(2) 選擇城市。每個螞蟻按照狀態(tài)變化規(guī)則逐步地構(gòu)造一個解，即生成一條路。螞蟻任務(wù)是在約束條件下，訪問客戶后回到倉庫，生成一條回路。設(shè)螞蟻k當(dāng)前所在的頂點為i ，則螞蟻k由點i 向點j 移動要遵循一下公式（1）的狀態(tài)變化規(guī)則而不斷遷徙，按不同概率來選擇下一個。 (,) Exploitation () Exploration （1）（其中 表示螞蟻k當(dāng)前選擇的城市集合，為禁忌表，它記錄螞蟻k已經(jīng)路過的城市，用來說明人工螞蟻的記憶性。用于評價螞蟻由點i 向點j 移動的啟發(fā)函數(shù)，其值通常用距離的倒數(shù)求得，即。體現(xiàn)了信息素和啟發(fā)信息對螞蟻決策的影響。取值為1；參數(shù)描述啟發(fā)函數(shù)的重要性;參數(shù)（）決定利用和開發(fā)的相對重要性，利用（Exploitation）指走最好的路，開發(fā)（Exploration）指按信息素濃度高概率高的原則選擇V, q是在0,1上任取的隨機(jī)數(shù)） 當(dāng)時，按公式（2）的概率進(jìn)行選擇：（3）修改禁忌表，即選擇好之后將螞蟻移動到下一個城市，并把該城市移動到螞蟻個體的禁忌表中；（4）循環(huán)執(zhí)行第2步和第3步，直到每只螞蟻都生成一條路徑；（5）計算第k只螞蟻所走路徑的總長度；（6）根據(jù)公式（3）（4）更新所有路徑上的信息量； （3） （4）（7）若循環(huán)次數(shù)NCNCmax,則循環(huán)結(jié)束并輸出計算結(jié)果，否則清空禁忌表并轉(zhuǎn)到第2步。相應(yīng)的MATLAB程序如下：%第一步：變量初始化L_nn,P_nn=NearestNeighborTSP(d);%是最近鄰域啟發(fā)算法產(chǎn)生的路線長度L_best=inf;T_best=0;tau0=1/(n* L_nn);%n為客戶以及倉庫數(shù)tau=ones(n,n)*tan0;ant_path=zeros(m,n+1);%第二步：將將m個螞蟻置于倉庫中ant_path(:,1)=randint(m,1,1,1);%第三步：選擇城市current_node=ant_path(k,s-1);%k為螞蟻數(shù)目，取值1m, s為問題規(guī)模，取2nvisited=ant_path(k,:);to_visit=setdiff(1:n,visited);c_temp=length(to_visit);if c_temp=0 p=zeros(1,c_temp);for i=1:c_temp p(i)=(tau(current_node,to_visit(i)alpha*(1/d(current_node, to_visit(i)beta:%計算endsun_p=sum(p);q0=rand;select=to_visit(c_temp);if q0capacity_limit %不滿足約束條件則回到倉庫select=1;endtotal_load=0;city_to_visit=select;ant_path(k,s)=city_to_visit;end%第四步：更新信息素值tau(current_node,city_to_visit)=(1-rho)*tau(current_node, city_to_visit)+tan0;tau(Tour_min(i),Tour_min(i+1)=(1-rho)*tau(Tour_min(i), Tour_min(i+1)+rho/L_gb;%第五步：禁忌表清零ant_path=zeros(m,n+1);end%第六步：輸出結(jié)果Pos=find(L_best=min(L_best);Shortest_Route=T_best(Pos(1),:)Shortest_Length=L_best(Pos(1)4、 基本蟻群算法的優(yōu)缺點 基本蟻群算法具有很強(qiáng)的發(fā)現(xiàn)解的能力，這是因為該算法不僅利用了正反饋原理，在一定程度上可以加快進(jìn)化過程，而且是一種本質(zhì)上并行的算法，不同個體之間不斷進(jìn)行信息交流和傳遞，從而能夠相互協(xié)作，有利于發(fā)現(xiàn)較好解。具有如下的優(yōu)點：(1)分布式本質(zhì)并行算法，它是一種基于種群的進(jìn)化算法，本質(zhì)上具有并行性，易于并行實現(xiàn)；(2)具有較強(qiáng)的魯棒性，對其模型稍加修改，便可以應(yīng)用于其他問題；(3)易于與其他方法結(jié)合，基本蟻群算法很容易與多種啟發(fā)式算法結(jié)合，以改善算法的性能；(4)其優(yōu)化過程不依賴于優(yōu)化問題本身的嚴(yán)格數(shù)學(xué)性質(zhì)，如連續(xù)性，可導(dǎo)性及目標(biāo)函數(shù)和約束函數(shù)的精確數(shù)學(xué)描述；(5)是一類概率型的全局搜索方法，這種非確定性使算法能夠有更多的機(jī)會求得全局最優(yōu)解；基本蟻群算法是一種有效的隨機(jī)搜索算法，但也存在一些缺陷：(1)與其他方法相比，該算法一般需要較長的時間；(2)該算法易出現(xiàn)停滯現(xiàn)象，即搜索進(jìn)行到一定程度后，所有個體所發(fā)現(xiàn)的解完全一致，不能對解空間進(jìn)一步搜索，不利于發(fā)現(xiàn)更好的解。5、一種新的改進(jìn)蟻群算法用2-opt方法局部優(yōu)化用蟻群算法構(gòu)造的VRP解不同的智能算法出現(xiàn)停滯現(xiàn)象的原因各不相同,但結(jié)果是相同的,即所求的解越來越相似,避免這種現(xiàn)象的方法也是一致的,那就是增加解的多樣性。螞蟻算法盡管能夠分布式并行搜索，但在限定的時間或代數(shù)內(nèi)找到最優(yōu)解仍是困難的，可能找到的只是可行的近優(yōu)解，這一點與遺傳算法相似。 用于啟發(fā)式局部優(yōu)化的方法很多!，主要包括2-opt,3-opt,頂點重定位（relocate）,交換（exchange）和交叉(cross)等，其中最實用有效的是2-opt和3-opt算法。因此，我們在螞蟻算法中混入局部優(yōu)化算法，對每代構(gòu)造的解進(jìn)行改進(jìn)，從而進(jìn)一步縮短解路線的長度，以加快螞蟻算法的收斂速度。 將2-opt方法混入螞蟻算法求解過程中，對每代迭代產(chǎn)生的最優(yōu)解的相鄰邊進(jìn)行交換。將2-opt方法混入螞蟻算法求解過程中:repeatmodified_tour:=apply_2-opt_move(current_tour)if length(modified_tour)0) r= All_line(1,1);s= All_line(1,2);All_line=setdiff(All_line,r s,rows);%排除已經(jīng)處理過的邊ctemp=T(r+1:s-1);n_ctemp=length(ctemp);temp=zeros(1,n_ctemp);for i=0: n_ctemp-1temp(i+1)= ctemp(n_ctemp-i);endcurrent_T=T(1：r-1)T(s) temp T(r) T(s+1:n);%進(jìn)行邊交換current_T=current_T current_T(1);%形成回路current_L=0;for i=1:ncurrent_L= current_L+d(current_T(i), current_T(i+1);endif(current_LL)T= current_T;L= current_L;All_line=N;endend %此時的T為經(jīng)過2-opt后的最短路勁6、 改進(jìn)蟻群算法和基本蟻群算法實驗對比選用VRPLIB中列出的Chris