基于MATLAB的蟻算法解決旅行商問題(附帶源程序、仿真)

---

摘要：旅行商問題的傳統(tǒng)求解方法是遺傳算法，但此算法收斂速度慢，并不能

獲得問題的最優(yōu)化解。蟻算法是受自然界中蟻搜索食物行為啟發(fā)而提出的一

種智能優(yōu)化算法，通過介紹蟻覓食過程中基于信息素的最短路徑的搜索策略，

給出基于MATLAB的蟻算法在旅行商問題中的應(yīng)用，對(duì)問題求解進(jìn)行局部?jī)?yōu)

化。經(jīng)過計(jì)算機(jī)仿真結(jié)果表明，這種蟻算法對(duì)求解旅行商問題有較好的改進(jìn)效

果。

關(guān)鍵詞：蟻算法；旅行商問題；MATLAB；優(yōu)化

一、意義和目標(biāo)

旅行商問題是物流領(lǐng)域中的典型問題，它的求解具有十分重要的理論和現(xiàn)實(shí)

意義。采用一定的物流配送方式，可以大大節(jié)省人力物力，完善整個(gè)物流系統(tǒng)。

已被廣泛采用的遺傳算法是旅行商問題的傳統(tǒng)求解方法，但遺傳算法收斂速

度慢，具有一定的缺陷。本文采用蟻算法，充分利用蟻算法的智能性，求解

旅行商問題，并進(jìn)行實(shí)例仿真。進(jìn)行仿真計(jì)算的目標(biāo)是，該算法能夠獲得旅行商

問題的優(yōu)化結(jié)果，平均距離和最短距離。

二、國(guó)內(nèi)外研究現(xiàn)狀

仿生學(xué)出現(xiàn)于20世紀(jì)50年代中期，人們從生物進(jìn)化機(jī)理中受到啟發(fā)，提出

了遺傳算法、進(jìn)化規(guī)劃、進(jìn)化策略等許多用以解決復(fù)雜優(yōu)化問題的新方法。這些

以生物特性為基礎(chǔ)的演化算法的發(fā)展及對(duì)生物落行為的發(fā)現(xiàn)引導(dǎo)研究人員進(jìn)

一步開展了對(duì)生物社會(huì)性的研究，從而出現(xiàn)了基于智能理論的蟻算法，并掀

起了一股研究的熱潮。

20世紀(jì)90年代意大利科學(xué)家M最早提出了蟻優(yōu)化算法——螞

-.-word資料-

---

蟻系統(tǒng)（Antsystem,AS），在求解二次分配、圖著問題、車輛調(diào)度、集成電路

設(shè)計(jì)以及通信網(wǎng)絡(luò)負(fù)載問題的處理中都取得了較好的結(jié)果。

旅行商問題（TSP,TravelingSalesmanProblem）被認(rèn)為是一個(gè)基本問題，

是在1859年由威廉·漢密爾頓爵士首次提出的。所謂TSP問題是指：有個(gè)城市，

要求旅行商到達(dá)每個(gè)城市各一次，且僅一次，并回到起點(diǎn)，且要求旅行路線最短。

這是一個(gè)典型的優(yōu)化問題，對(duì)一個(gè)具有中等頂點(diǎn)規(guī)模的圖來說，精確求解也是很

復(fù)雜的，計(jì)算量隨著城市個(gè)數(shù)的增加而呈指數(shù)級(jí)增長(zhǎng)，即屬于所謂的P問題。

TSP在工程領(lǐng)域有著廣泛的應(yīng)用，并常作為比較算法性能的標(biāo)志。如網(wǎng)絡(luò)通訊、

貨物運(yùn)輸、電氣布線、管道鋪設(shè)、加工調(diào)度、專家系統(tǒng)、柔性制造系統(tǒng)等方面，

都是TSP廣泛應(yīng)用的領(lǐng)域。求解算法包括貪婪法（GM）、極小代數(shù)法（MA）、模

擬退火法（SA）和遺傳算法（GA）等。而應(yīng)用蟻算法求解旅行商問題是近年

來研究的新方向，由于其并行性與分布性，特別適用于大規(guī)模啟發(fā)式搜索，實(shí)驗(yàn)

結(jié)果證明了其可行性和有效性。

三、蟻系統(tǒng)基本原理

在螞蟻到食物時(shí)，它們總能到一條從食物到巢穴之間的最優(yōu)路徑。這

是因?yàn)槲浵佋趯ぢ窂綍r(shí)會(huì)在路徑上釋放出一種特殊的信息素（phero-mone）。

當(dāng)它們碰到一個(gè)還沒有走過的路口時(shí)，就隨機(jī)地挑選一條路徑前行。與此同時(shí)釋

放出與路徑長(zhǎng)度有關(guān)的信息素。路徑越長(zhǎng)，釋放的激素濃度越低。當(dāng)后來的螞蟻

再次碰到這個(gè)路口的時(shí)候，選擇激素濃度較高路徑概率就會(huì)相對(duì)較大。這樣形成

了一個(gè)正反饋。最優(yōu)路徑上的激素濃度越來越大，而其它的路徑上激素濃度卻會(huì)

隨著時(shí)間的流逝而消減。最終整個(gè)蟻會(huì)出最優(yōu)路徑。在整個(gè)尋徑過程中，雖

然單個(gè)螞蟻的選擇能力有限，但是通過激素的作用，整個(gè)蟻之間交換著路徑信

-.-word資料-

---

息，最終出最優(yōu)路徑。

四、基于MATLAB的蟻算法求解旅行商問題

TSP問題描述如下：

設(shè)有n個(gè)城市C=（1，2,...,n），任意兩個(gè)城市i，j之間的距離為dij

，求一

條經(jīng)過每個(gè)城市的路徑π=（π（1），π（2），...，π（n）），使得距離最小。

主要符號(hào)說明

Cn個(gè)城市的坐標(biāo)，n×2的矩陣

C_max最大迭代次數(shù)

m螞蟻個(gè)數(shù)

Alpha表征信息素重要程度的參數(shù)

Beta表征啟發(fā)式因子重要程度的參數(shù)

Rho信息素蒸發(fā)系數(shù)

Q信息素增加強(qiáng)度系數(shù)

R_best各代最佳路線

L_best各代最佳路線的長(zhǎng)度

求解TSP問題的螞蟻算法中，每只螞蟻是一個(gè)獨(dú)立的用于構(gòu)造路線的過程，

若干螞蟻過程之間通過自適應(yīng)的信息素值來交換信息，合作求解，并不斷優(yōu)化。

這里的信息素值分布式存儲(chǔ)在圖中，與各弧相關(guān)聯(lián)。螞蟻算法求解TSP問題的

過程如下：

（1）首先初始化，設(shè)迭代的次數(shù)為C。初始化C=0

（2）將m個(gè)螞蟻置于n個(gè)頂點(diǎn)上

（3）m只螞蟻按概率函數(shù)選擇下一座城市，完成各自的周游

-.-word資料-

---

每個(gè)螞蟻按照狀態(tài)變化規(guī)則逐步地構(gòu)造一個(gè)解，即生成一條回路。螞蟻的任

務(wù)是訪問所有的城市后返回到起點(diǎn)，生成一條回路。設(shè)螞蟻k當(dāng)前所在的頂點(diǎn)為

i，那么，螞蟻k由點(diǎn)i向點(diǎn)j移動(dòng)要遵循規(guī)則而不斷遷移，按不同概率來選擇下

一點(diǎn)。

（4）記錄本次迭代最佳路線

（5）全局更新信息素值

應(yīng)用全局信息素更新規(guī)則來改變信息素值。當(dāng)所有m個(gè)螞蟻生成了m個(gè)解，

其中有一條最短路徑是本代最優(yōu)解，將屬于這條路線上的所有弧相關(guān)聯(lián)的信息素

值進(jìn)行更新。

全局信息素更新的目的是在最短路線上注入額外的信息素，即只有屬于最短

路線的弧上的信息素才能得到加強(qiáng)，這是一個(gè)正反饋的過程，也是一個(gè)強(qiáng)化學(xué)習(xí)

的過程。在圖中各弧上，伴隨著信息素的揮發(fā)，全局最短路線上各弧的信息素值

得到增加。

（6）終止

若終止條件滿足，則結(jié)束；否則C=C+1，轉(zhuǎn)入步驟（2）進(jìn)行下一代進(jìn)化。

終止條件可指定進(jìn)化的代數(shù)，也可限定運(yùn)行時(shí)間，或設(shè)定最短路長(zhǎng)的下限。

（7）輸出結(jié)果

-.-word資料-

---

五、數(shù)據(jù)實(shí)驗(yàn)及結(jié)果

通過計(jì)算機(jī)仿真，得出旅行商問題優(yōu)化結(jié)果和平均距離和最短距離，如圖所

示：

-.-word資料-

---

六、分析與總結(jié)

本文設(shè)計(jì)了一種基于MATLAB實(shí)現(xiàn)的蟻算法，用以求解組合優(yōu)化難題中的

典型代表旅行商問題。對(duì)30個(gè)城市旅行商問題進(jìn)行了測(cè)試，所得結(jié)果能達(dá)到優(yōu)

化作用，實(shí)現(xiàn)了本文的研究目標(biāo)。

經(jīng)過對(duì)旅行商問題的深入理解，得到了能解決問題的基本數(shù)學(xué)模型，然后設(shè)

計(jì)算法的基本思想，技術(shù)路線，最后編碼。在多次調(diào)試，修改后，本算法成功運(yùn)

行，并實(shí)現(xiàn)了最初的設(shè)定目標(biāo)。另外，MATLAB具有豐富的繪圖函數(shù)，對(duì)于繪圖

十分方便，這是選擇MATLAB解決TSP問題的算法編寫、調(diào)試的原因。

蟻算法研究處于初期，還有許多問題值得研究，如算法的參數(shù)選擇、螞蟻

數(shù)的比例等只能通過仿真實(shí)驗(yàn)，無法給出理論指導(dǎo)。

-.-word資料-

---

附錄：

蟻算法解決旅行商問題MATLAB程序

functionyy=ACATSP

x=[4783987541444]';

y=[948467626499584462696269717876435

50]';

C=[xy];

C_max=50;

m=30;

Alpha=1.5;

Beta=2;

Rho=0.1;

Q=10^6;

%%-------------------------------------------------------------------------

%%主要符號(hào)說明

%%Cn個(gè)城市的坐標(biāo)，n×2的矩陣

%%C_max最大迭代次數(shù)

%%m螞蟻個(gè)數(shù)

%%Alpha表征信息素重要程度的參數(shù)

%%Beta表征啟發(fā)式因子重要程度的參數(shù)

%%Rho信息素蒸發(fā)系數(shù)

%%Q信息素增加強(qiáng)度系數(shù)

%%R_best各代最佳路線

%%L_best各代最佳路線的長(zhǎng)度

%%=========================================================================

%%第一步：變量初始化

n=size(C,1);%n表示問題的規(guī)模（城市個(gè)數(shù)）

D=zeros(n,n);%D表示完全圖的賦權(quán)鄰接矩陣

fori=1:n

forj=1:n

ifi~=j

D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;

else

D(i,j)=eps;%i=j時(shí)不計(jì)算，應(yīng)該為0，但后面的啟發(fā)因子要取倒數(shù)，用eps

（浮點(diǎn)相對(duì)精度）表示

end

D(j,i)=D(i,j);%對(duì)稱矩陣

end

end

-.-word資料-

---

Eta=1./D;%Eta為啟發(fā)因子，這里設(shè)為距離的倒數(shù)

Tau=ones(n,n);%Tau為信息素矩陣

Tabu=zeros(m,n);%存儲(chǔ)并記錄路徑的生成

C=1;%迭代計(jì)數(shù)器，記錄迭代次數(shù)

R_best=zeros(C_max,n);%各代最佳路線

L_best=inf.*ones(C_max,1);%各代最佳路線的長(zhǎng)度

L_ave=zeros(C_max,1);%各代路線的平均長(zhǎng)度

whileC<=C_max%停止條件之一：達(dá)到最大迭代次數(shù)，停止

%%第二步：將m只螞蟻放到n個(gè)城市上

Randpos=[];%隨即存取

fori=1:(ceil(m/n))

Randpos=[Randpos,randperm(n)];

end

Tabu(:,1)=(Randpos(1,1:m))';

%%第三步：m只螞蟻按概率函數(shù)選擇下一座城市，完成各自的周游

forj=2:n%所在城市不計(jì)算

fori=1:m

visited=Tabu(i,1:(j-1));%記錄已訪問的城市，避免重復(fù)訪問

J=zeros(1,(n-j+1));%待訪問的城市

P=J;%待訪問城市的選擇概率分布

Jc=1;

fork=1:n

iflength(find(visited==k))==0%開始時(shí)置0

J(Jc)=k;

Jc=Jc+1;%訪問的城市個(gè)數(shù)自加1

end

end

%下面計(jì)算待選城市的概率分布

fork=1:length(J)

P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);

end

P=P/(sum(P));

%按概率原則選取下一個(gè)城市

Pcum=cumsum(P);%cumsum，元素累加即求和

Select=find(Pcum>=rand);%若計(jì)算的概率大于原來的就選擇這條路線

to_visit=J(Select(1));

Tabu(i,j)=to_visit;

end

end

ifC>=2

Tabu(1,:)=R_best(C-1,:);

end

%%第四步：記錄本次迭代最佳路線

L=zeros(m,1);%開始距離為0，m*1的列向量

-.-word資料-

---

fori=1:m

R=Tabu(i,:);

forj=1:(n-1)

L(i)=L(i)+D(R(j),R(j+1));%原距離加上第j個(gè)城市到第j+1個(gè)城市的距離

end

L(i)=L(i)+D(R(1),R(n));%一輪下來后走過的距離

end

L_best(C)=min(L);%最佳距離取最小

pos=find(L==L_best(C));

R_best(C,:)=Tabu(pos(1),:);%此輪迭代后的最佳路線

L_ave(C)=mean(L);%此輪迭代后的平均距離

C=C+1;%迭代繼續(xù)

%%第五步：更新信息素

Delta_Tau=zeros(n,n);%開始時(shí)信息素為n*n的0矩陣

fori=1:m

forj=1:(n-1)

Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);

%此次循環(huán)在路徑（i，j）上的信息素增量

end

Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);

%此次循環(huán)在整個(gè)路徑上的信息素增量

end

Tau=(1-Rho).*Tau+Delta_Tau;%考慮信息素?fù)]發(fā)，更新后的信息素

%%第六步：禁忌表清零

Tabu=zeros(m,n);%%直到最大迭代次數(shù)

end

%%第七步：輸出結(jié)果

Pos=find(L_best==min(L_best));%到最佳路徑（非0為真）

Shortest_Route=R_best(Pos(1),:)%最大迭代次數(shù)后最佳路徑

Shortest_Length=L_best(Pos(1))%最大迭代次數(shù)后最短距離

subplot(1,2,1);%繪制第一個(gè)子圖形

DrawRoute(C,Shortest_Route);%畫路線圖的子函數(shù)

subplot(1,2,2);%繪制第二個(gè)子圖形

plot(L_best);

holdon%保持圖形

plot(L_ave,'r');

title('平均距離和最短距離')%標(biāo)題

functionDrawRoute(C,R)

%%=========================================================================

%%DrawRoute.m

%%畫路線圖的子函數(shù)

%%-------------------------------------------------------------------------

%%CCoordinate節(jié)點(diǎn)坐標(biāo)，由一個(gè)×2的矩陣存儲(chǔ)

%%RRoute路線

-.-word資料-

---

%%=========================================================================

=length(R);

scatter(C(:,1),C(:,2));

holdon

plot([C(R(1),1),C(R(),1)],[C(R(1),2),C(R(),2)],'g');

holdon

forii=2:

plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)],'g');

holdon

end

title('旅行商問題優(yōu)化結(jié)果')

-.-word資料-