首頁 > 法律常識

蟻優化算法原理及Matlab編程實現

更新時間:2025-12-16 03:09:56 閱讀：評論：0

2022年8月1日發
(作者：環保工程專業承包叁級)

蟻優化算法原理及Matlab編程實現

蟻算法的提出：

人類認識事物的能力來源于與自然界的相互作用，自然界一直是人類創造力

的源泉。自然界有許多自適應的優化現象不斷地給人以啟示，生物和自然中的生

態系

統可以利用自身的演化來讓許多在人類看來高度復雜的優化問題得到幾乎完美

的解決。近些年來，一些與經典的數學問題思想不同的，試圖通過模擬自然生態

系統

來求解復雜優化問題的仿生學算法相繼出現，如蟻算法、遺傳算法、粒子算

法等。這些算法大大豐富了現在優化技術，也為那些傳統最優化技術難以處理的

組

合優化問題提供了切實可行的解決方案。

生物學家通過對螞蟻的長期的觀察發現，每只螞蟻的智能并不高，看起來沒

有集中的指揮，但它們卻能協同工作，集中事物，建起堅固漂亮的蟻穴并撫養后

代，

依靠體能力發揮出超出個體的智能。蟻算法是最新發展的一種模擬昆蟲王國

中螞蟻體智能行為的仿生優化算法，它具有較強的魯棒性、優良的分布式計算

機

制、易于與其他方法相結合等優點。盡管蟻算法的嚴格理論基礎尚未奠定，國

內外的相關研究還處于實驗階段，但是目前人們對蟻算法的研究已經由當初單

一

的旅行商問題(TSP)領域滲透到了多個應用領域，由解決一維靜態優化問題發展

到解決多維動態組合優化問題，由離散域范圍內的研究逐漸擴展到了連續域范圍

內的

研究，從而使這種新興的仿生優化算法展現出勃勃生機和廣闊的發展前景。

人工螞蟻與真實螞蟻的異同比較

相同點比較

蟻算法是從自然界中真實螞蟻覓食的體行為得到啟發而提出的，其很多

觀點都來源于真實蟻，因此算法中所定義的人工螞蟻與真實螞蟻存在如下共同

點。

（1）都存在一個體中個體相互交流通信的機制

人工螞蟻和真實螞蟻都存在一種改變當前所處環境的機制：真實螞蟻在經過

的路徑上留下信息素，人工螞蟻改變在其所經路徑上存儲的數字信息，該信息就

是算

法中所定義的信息量，它記錄了螞蟻當前解和歷史解的性能狀態，而且可被其他

后繼人工螞蟻讀寫。蟻的這種交流方式改變了當前螞蟻所經路徑周圍的環境，

同

時也以函數的形式改變了整個蟻所存儲的歷史信息。通常，在蟻算法中有一

個揮發機制，它像真實的信息量揮發一樣隨著時間的推移來改變路徑上的信息

量。

揮發機制使得人工螞蟻和真實螞蟻可以逐漸地忘卻歷史遺留信息，這樣可使螞蟻

在選擇路徑時不局限于以前螞蟻所存留的“經驗”。

（2）都要完成一個相同的任務

人工螞蟻和真實螞蟻都要完成一個相同的任務，即尋一條從源節點（巢穴）

到目的節點（食物源）的最短路徑。人工螞蟻和真實螞蟻都不具有跳躍性，只能

在

相鄰節點之間一步步移動，直至遍歷完所有城市。為了能在多次尋路過程中到

最短路徑，則應該記錄當前的移動序列。

（3）利用當前信息進行路徑選擇的隨機選擇策略

人工螞蟻和真實螞蟻從某一節點到下一節點的移動都是利用概率選擇策略實

現的，概率選擇策略只利用當前的信息去預測未來的情況，而不能利用未來的信

息。

因此，人工螞蟻和真實螞蟻所使用的選擇策略在時間和空間上都是局部的。

不同點比較

在從真實蟻行為獲得啟發而構造蟻算法的過程中，人工螞蟻還具備了真

實螞蟻所不具備的一些特性：

（1）人工螞蟻存在于一個離散的空間中，它們的移動是從一個狀態到另一個

狀態的轉換；

（2）人工螞蟻具有一個記憶其本身過去行為的內在狀態；

（3）人工螞蟻存在于一個與時間無關聯的環境中；

（4）人工螞蟻不是完全盲從的，它還受到問題空間特征的啟發。例如有的問

題中人工螞蟻在產生一個解后改變信息量，但無論哪種方法，信息量的更新并不

是隨

時都可以進行的；

（5）為了改善算法的優化效率，人工螞蟻可增加一些性能，如預測未來、局

部優化、回退等，這些行為在真實螞蟻中是不存在的。在很多具體應用中，人工

螞蟻

可在局部優化過程中相互交換信息，還有一些改進蟻算法中的人工螞蟻可實現

簡單預測。

蟻算法的流程圖

基本蟻算法的實現步驟

以TSP為例，基本蟻算法的具體實現步驟如下：

（1）參數初始化。令時間t=0和循環次數τ=0，設置最大循環次數

=0，將m

只螞蟻置于n個元素（城市）上，令有向圖上每條邊

（i，j）的初始化信息量τ

(t)=const，其中const表示常數，且初始時刻Δτ

(0)=0。

（2）循環次數。

（3）螞蟻的禁忌表索引號k=1。

（4）螞蟻數目。

（5）螞蟻個體根據狀態轉移概率公式計算的概率選擇元素（城市）j并前進，

。

其中，表示在t時刻螞蟻k由元素（城市）i轉移到元素（城市）j的狀態轉

移概率。allowed

=C?tabu

表示螞蟻k下一步允許選擇的城市。α為啟發式因

子，

表示軌跡的相對重要性，反映了螞蟻在運動過程中所積累的信息在螞蟻運動時所

起的作用，其值越大，則該螞蟻越傾向于選擇其他螞蟻

經過的路徑，螞蟻之間的協作性越強。β為期望啟發式因子，表示能見度的相對

重要性，反映了螞蟻在運動過程中啟發信息在螞蟻選擇路徑中的受重

視程度，其值越大，則該狀態轉移概率越接近于貪心規則；η

(t)為啟發函數，

表達式為。式中，d

表示相鄰兩個城市之間的距離。

（6）修改禁忌表指針，即選擇好之后將螞蟻移動到新的元素（城市），并把該

元素（城市）移動到該螞蟻個體的禁忌表中。

（7）若集合C中元素（城市）未遍歷完，即k

執行第（8）步。

（8）根據公式更新每條路徑上的信息量：

(t+n)=(1?ρ)*τ

(t)+Δτ

(t)

（9）若滿足結束條件，即如果循環次數，則循環結束并輸出程序計算結果，

否則清空禁忌表并跳轉到第（2）步。

]蟻算法的matlab源程序

1.蟻算法主程序：main.m

%function[bestroute,routelength]=Ant

clc

clear

tic

%讀入城市間距離矩陣數據文件

CooCity=load('');%城市網絡圖坐標數據文件，txt形式給

出

C=length(CooCity);%城市個數

fori=1:C%計算各城市間的距離

forj=1:C

distance(i,j)=sqrt((CooCity(i,2)-CooCity(j,2))^2+(CooCity(i,3)-CooCit

y(j,3))^2);

end

MAXIT=10;%最大循環次數

Citystart=[];%起點城市編號

tau=ones(C,C);%初始時刻各邊上的信息痕跡為1

rho=0.5;%揮發系數

alpha=1;%殘留信息相對重要度

beta=5;%預見值的相對重要度

Q=10;%蟻環常數

umAnt=20;%螞蟻數量

routelength=inf;%用來記錄當前到的最優路徑長度

forn=1:MAXIT

fork=1:umAnt%考查第K只螞蟻

deltatau=zeros(C,C);%第K只螞蟻移動前各邊上的信息增量為

零

%[routek,lengthk]=path(distance,tau,alpha,beta,[]);%

不靠率起始點

[routek,lengthk]=path(distance,tau,alpha,beta,Citystart);%指定起

始點

iflengthk

:::routelength=lengthk;

:::bestroute=routek;

end

fori=1:C-1%第K只螞蟻在路徑上釋放的信息量

deltatau(routek(i),routek(i+1))=deltatau(routek(i),routek(i+1))+Q/len

gthk;%信息素更新

end

%deltatau(routek(C),1)=deltatau(routek(C),1)+Q/lengthk;%

end

length_n(n)=routelength;%記錄路徑收斂

tau=(1-rho).*tau;%信息素揮發

end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

costtime=toc;

subplot(1,2,1),plot([CooCity(bestroute,2)],[CooCity(bestroute,3)],'-*

subplot(1,2,2),plot([1:MAXIT],length_n,'-*')

[routelength,costtime]

2.蟻算法尋路徑程序：path.m

%某只螞蟻到的某條路徑routek,lengthk

function[routek,lengthk]=path(distance,tau,alpha,beta,Citystart)

[m,n]=size(distance);

ifisempty(Citystart)%如果不確定起點

p=fix(m*rand)+1;%隨機方式初始化起點，均勻概率

else

p=Citystart;%外部給定確定起點

end

lengthk=0;%初始路徑長度設為0

routek=[p];%螞蟻路徑點序列，即該螞蟻已經過的城市集合，路徑初

始起點

fori=1:m-1

np=routek(end);%螞蟻路徑城市序號，依次經過的城市編號

np_sum=0;%路由長度初始為0

forj=1:m

ifinroute(j,routek)%判斷城市節點j是否屬于tabuk，即

是否已經過

continue;

else%j為還未經過的點，對

ada=1/distance(np,j);%預見度

np_sum=np_sum+tau(np,j)^alpha*ada^beta;%路由表：信息痕

跡、預見度

end

cp=zeros(1,m);%轉移概率，基于路徑長度及路由表

forj=1:m

ifinroute(j,routek)

continue;

留言與評論（共有 0 條評論）