⑴ 蟻群演算法優化BP神經網路 遇到的問題。
蟻群演算法的實質是遺傳演算法,為了避免陷入局部最優解,我使用的辦法是基因多樣化演算法,初始化基因組時,多取幾組隨機值,然後對這n組數據同時進化優化,並行計算。這樣可以大大減低陷入局部最優解的風險
⑵ 請教,採用蟻群演算法求解TSP問題的oliver30最優路徑
給你產考產考//蟻群演算法關於簡單的TSP問題求解//#include#include#include#include#include#defineM13//螞蟻的數量#defineN144//城市的數量#defineR1000//迭代次數#defineIN1//初始化的信息素的量#defineMAX0x7fffffff//定義最大值structcoordinate{charcity[15];//城市名intx;//城市相對橫坐標inty;//城市相對縱坐標}coords[N];doublegraph[N][N];//儲存城市之間的距離的鄰接矩陣,自己到自己記作MAXdoublephe[N][N];//每條路徑上的信息素的量doubleadd[N][N];//代表相應路徑上的信息素的增量doubleyita[N][N];//啟發函數,yita[i][j]=1/graph[i][j]intvis[M][N];//標記已經走過的城市intmap[M][N];//map[K][N]記錄第K只螞蟻走的路線doublesolution[M];//記錄某次循環中每隻螞蟻走的路線的距離intbestway[N];//記錄最近的那條路線doublebestsolution=MAX;intNcMax;//代表迭代次數,理論上迭代次數越多所求的解更接近最優解,最具有說服力doublealpha,betra,rou,Q;voidInitialize();//信息初始化voidInputcoords(FILE*fp);//將文件中的坐標信息讀入voidGreateGraph();//根據坐標信息建圖doubleDistance(int*p);//計算螞蟻所走的路線的總長度voidResult();//將結果保存到out.txt中voidInitialize(){alpha=2;betra=2;rou=0.7;Q=5000;NcMax=R;return;}voidInputcoords(FILE*fp){inti;intnumber;if(fp==NULL){printf("Sorry,thefileisnotexist\n");exit(1);}else{for(i=0;idrand)break;}vis[k][j]=1;//將走過的城市標記起來map[k][s]=j;//記錄城市的順序}s++;}memset(add,0,sizeof(add));for(k=0;k20)//設立一個上界,防止啟發因子的作用被淹沒phe[i][j]=20;}}memset(vis,0,sizeof(vis));memset(map,-1,sizeof(map));}Result();printf("Resultissavedinout.txt\n");return0;}
⑶ 蟻群演算法的路徑規劃,每一次的結果都不同么
蟻群演算法 屬於隨機優化演算法的一種,隨機優化演算法,由於開始和過程都是隨機的數值,所以每次產生的結果都不一樣。但大致收斂方向是一致的。
⑷ 如何提高蟻群路由演算法收斂速度
述了。
目前蟻群演算法主要用在組合優化方面,基本蟻群演算法的思路是這樣的:
1.
在初始狀態下,一群螞蟻外出,此時沒有信息素,那麼各自會隨機的選擇一條路徑。
2.
在下一個狀態,每隻螞蟻到達了不同的點,從初始點到這些點之間留下了信息素,螞蟻繼續走,已經到達目標的螞蟻開始返回,與此同時,下一批螞蟻出動,它們都會按照各條路徑上信息素的多少選擇路線(selection),更傾向於選擇信息素多的路徑走(當然也有隨機性)。
3.
又到了再下一個狀態,剛剛沒有螞蟻經過的路線上的信息素不同程度的揮發掉了(evaporation),而剛剛經過了螞蟻的路線信息素增強(reinforcement)。然後又出動一批螞蟻,重復第2個步驟。
每個狀態到下一個狀態的變化稱為一次迭代,在迭代多次過後,就會有某一條路徑上的信息素明顯多於其它路徑,這通常就是一條最優路徑。
關鍵的部分在於步驟2和3:
步驟2中,每隻螞蟻都要作出選擇,怎樣選擇呢?
selection過程用一個簡單的函數實現:
螞蟻選擇某條路線的概率=該路線上的信息素÷所有可選擇路線的信息素之和
假設螞蟻在i點,p(i,j)表示下一次到達j點的概率,而τ(i,j)表示ij兩點間的信息素,則:
p(i,j)=τ(i,j)/∑τ(i)
(如果所有可選路線的信息素之和∑τ(i)=0,即前面還沒有螞蟻來過,概率就是一個[0,1]上的隨機值,即隨機選擇一條路線)
步驟3中,揮發和增強是演算法的關鍵所在(也就是如何數學定義信息素的)
evaporation過程和reinforcement過程定義了一個揮發因子,是迭代次數k的一個函數
ρ(k)=1-lnk/ln(k+1)
最初設定每條路徑的信息素τ(i,j,0)為相同的值
然後,第k+1次迭代時,信息素的多少
對於沒有螞蟻經過的路線:τ(i,j,k+1)=(1-ρ(k))τ(i,j,k),顯然信息素減少了
有螞蟻經過的路線:τ(i,j,k+1)=(1-ρ(k))τ(i,j,k)+ρ(k)/|w|,w為所有點的集合
為什麼各個函數要如此定義,這個問題很難解釋清楚,這也是演算法的精妙所在。如此定義信息素的揮發和增強,以及路徑選擇,根據馬爾可夫過程(隨機過程之一)能夠推導出,在迭代了足夠多次以後,演算法能夠收斂到最佳路徑。
組合優化很有意思的,像禁忌搜索、模擬退火、蟻群演算法、遺傳演算法、神經網路這些演算法能夠解決很多生活中的實際問題,樓主有空可以招本書看看。
⑸ 求教:蟻群演算法選擇最短路徑問題
這個例子其實是當初數模比賽時用來完成碎片拼接的,但其所用到原理還是求解最短路徑的原理。但這里的最短路徑和數據結構中最短路徑有一定的區別。在數據結構中,對於最短路徑的求解常用的一般有Dijkstra演算法與Floyd演算法,但對於要求出一條經過所有的點的並且要求路徑最短,這些演算法還是有一定的局限性的。而蟻群演算法則很好地滿足了這些條件。話說回來,很想吐槽一下網路流傳的一些蟻群演算法的例子,當初學習這個時候,身邊也沒有相關的書籍,只好到網上找例子。網上關於這個演算法源代碼的常見的有2個版本,都是出自博客,但是在例子都代碼是不完整的,缺失了一部分,但就是這樣的例子,居然流傳甚廣,我很好奇那些轉載這些源碼的人是否真的有去學習過這些,去調試過。當然,我下面的例子也是無法直接編譯通過的,因為涉及到圖像讀取處理等方面的東西,所以就只貼演算法代碼部分。但是對於這個問題蟻群演算法有一個比較大的缺點,就是收斂很慢,不過對於數量小的路徑,效果還是很好的。function bestqueue =aco1(nt,nc_max,m ,st, sd ,Alpha ,Beta ,Rho ,Q,gethead,getend)%參數解釋:%nt 路徑所經過的點的個數;%nc_max 迭代的次數;%m 螞蟻的個數;%st 起點序號;%sd 終點序號;%Alpha 信息素系數;�ta 啟發因子系數;%Rho 蒸發系數;% Q 信息量;%gethead getend 是用來求距離矩陣的,可根據實際情況修改
% nt = 209;%碎片個數full = zeros(nt,nt);tic;%初始化距離矩陣for i =1:nt for t = 1:nt if i ~= t full(i,t) = sum(abs(getend(:,i) - gethead(:,t))); else full(i,t) = inf; end endend% a =full(156,187)eta = 1./full;%啟發因子,取距離的倒數% eta% e = eta(4,2)tau = ones(nt,nt);%信息素矩陣% tabu = zeros(nt,nt);%禁忌矩陣,取螞蟻數量和碎片數量一致,以減少迭代次數nc =1;%初始化迭代次數;rbest=zeros(nc_max,nt);%各代最佳路線rbest(:,1) = (linspace(st,st,nc_max))';rbest(:,nt) =(linspace(sd,sd,nc_max))'; lbest=zeros(nc_max,1);%各代最佳路線的長度pathlen = 0;%臨時記錄每代最佳路線長度stime = 1;%記錄代數進度for i = 1:nc_max % 代數循環 delta_tau=zeros(nt,nt);%初始化改變數 stime for t = 1:m % 對螞蟻群體的循環, tabu=zeros(1,nt);%禁忌向量,標記已訪問的碎片,初試值設為0,訪問之後則變為1; viseted = zeros(1,nt);%記錄已訪問的元素的位置 tabu(st) = 1;%st為起點,在此表示為碎片矩陣的編號,因為已經將蟻群放在起點,故也應將禁忌向量和位置向量的狀態進行修改 tabu(sd) =1;%同上 visited(nt) = sd ;%同上; visited(1) = st;%同上; ht = 0; for r = 2:nt-1 %記錄了還沒訪問的圖片編號 vp = 1;%visited指示量 pp = [];%置空的概率向量 jc = 0; %獲取尚未訪問的位置的向量。 wv = zeros( nt -2 - ht ); for k =1 : nt if tabu(k) == 0 jc = jc +1; wv(jc) = k; end end% a =(tau(visited(end),ju(3))^Alpha)*(eta(visited(end),ju(3))^Beta)% visited(end) %計算選擇的概率 for k=1:length(wv) pp(k)=(tau(visited(vp),wv(k))^Alpha)*(eta(visited(vp),wv(k))^Beta);%下一張碎片的選擇概率計算,p =(信息素^信息素系數)*(啟發因子^啟發因子系數) end pp=pp./(sum(pp));%歸一化 pcum =cumsum(pp); psl = find(pcum >= rand);%輪盤賭法 to_visit= wv(psl(1)) ;%完成選點 tabu(to_visit) =1; visited(r) = to_visit; ht =ht +1;%已訪問碎片個數變化 vp =vp+1; end %路徑變化信息 %對單個螞蟻的路徑進行統計 sum1 =0; for pr = 1:nt -1 x = visited(pr); y = visited(pr+1) ; sum1 =sum1 + full(x,y); end% vcell{t} =visited;%元胞記錄每個螞蟻的路徑,即碎片順序;% msum(t) = sum1; %信息素變化; for ww=1:(nt-1) delta_tau(visited(ww),visited(ww+1))=delta_tau(visited(ww),visited(ww+1)) + Q/sum1; end% delta_tau(visited(end),visited(1))=delta_tau(visited(end),visited(1))+Q/(sum1/100);% if t == m & i == nc_max % bestqueue = visited% end if t == m bestqueue = visited end end tau=(1-Rho).*tau+delta_tau; %完成信息素的更新,找出現有的最新的最佳路徑,即信息素最多的路徑; stime =stime +1;end toc;
⑹ 用螞蟻演算法來實現公交線網優化,誰有源代碼
我只告訴你什麼是螞蟻演算法: 蟻群演算法(ant colony optimization, ACO),又稱螞蟻演算法,是一種用來在圖中尋找優化路徑的機率型技術。它由Marco Dorigo於1992年在他的博士論文中引入,其靈感來源於螞蟻在尋找食物過程中發現路徑的行為。
為什麼小小的螞蟻能夠找到食物?他們具有智能么?設想,如果我們要為螞蟻設計一個人工智慧的程序,那麼這個程序要多麼復雜呢?首先,你要讓螞蟻能夠避開障礙物,就必須根據適當的地形給它編進指令讓他們能夠巧妙的避開障礙物,其次,要讓螞蟻找到食物,就需要讓他們遍歷空間上的所有點;再次,如果要讓螞蟻找到最短的路徑,那麼需要計算所有可能的路徑並且比較它們的大小,而且更重要的是,你要小心翼翼的編程,因為程序的錯誤也許會讓你前功盡棄。這是多麼不可思議的程序!太復雜了,恐怕沒人能夠完成這樣繁瑣冗餘的程序。
然而,事實並沒有你想得那麼復雜,上面這個程序每個螞蟻的核心程序編碼不過100多行!為什麼這么簡單的程序會讓螞蟻干這樣復雜的事情?答案是:簡單規則的涌現。事實上,每隻螞蟻並不是像我們想像的需要知道整個世界的信息,他們其實只關心很小范圍內的眼前信息,而且根據這些局部信息利用幾條簡單的規則進行決策,這樣,在蟻群這個集體里,復雜性的行為就會凸現出來。這就是人工生命、復雜性科學解釋的規律!那麼,這些簡單規則是什麼呢?下面詳細說明:
1、范圍:
螞蟻觀察到的范圍是一個方格世界,螞蟻有一個參數為速度半徑(一般是3),那麼它能觀察到的范圍就是3*3個方格世界,並且能移動的距離也在這個范圍之內。
2、環境:
螞蟻所在的環境是一個虛擬的世界,其中有障礙物,有別的螞蟻,還有信息素,信息素有兩種,一種是找到食物的螞蟻灑下的食物信息素,一種是找到窩的螞蟻灑下的窩的信息素。每個螞蟻都僅僅能感知它范圍內的環境信息。環境以一定的速率讓信息素消失。
3、覓食規則:
在每隻螞蟻能感知的范圍內尋找是否有食物,如果有就直接過去。否則看是否有信息素,並且比較在能感知的范圍內哪一點的信息素最多,這樣,它就朝信息素多的地方走,並且每隻螞蟻多會以小概率犯錯誤,從而並不是往信息素最多的點移動。螞蟻找窩的規則和上面一樣,只不過它對窩的信息素做出反應,而對食物信息素沒反應。
4、移動規則:
每隻螞蟻都朝向信息素最多的方向移,並且,當周圍沒有信息素指引的時候,螞蟻會按照自己原來運動的方向慣性的運動下去,並且,在運動的方向有一個隨機的小的擾動。為了防止螞蟻原地轉圈,它會記住最近剛走過了哪些點,如果發現要走的下一點已經在最近走過了,它就會盡量避開。
5、避障規則:
如果螞蟻要移動的方向有障礙物擋住,它會隨機的選擇另一個方向,並且有信息素指引的話,它會按照覓食的規則行為。
7、播撒信息素規則:
每隻螞蟻在剛找到食物或者窩的時候撒發的信息素最多,並隨著它走遠的距離,播撒的信息素越來越少。
根據這幾條規則,螞蟻之間並沒有直接的關系,但是每隻螞蟻都和環境發生交互,而通過信息素這個紐帶,實際上把各個螞蟻之間關聯起來了。比如,當一隻螞蟻找到了食物,它並沒有直接告訴其它螞蟻這兒有食物,而是向環境播撒信息素,當其它的螞蟻經過它附近的時候,就會感覺到信息素的存在,進而根據信息素的指引找到了食物。
說了這么多,螞蟻究竟是怎麼找到食物的呢?
在沒有螞蟻找到食物的時候,環境沒有有用的信息素,那麼螞蟻為什麼會相對有效的找到食物呢?這要歸功於螞蟻的移動規則,尤其是在沒有信息素時候的移動規則。首先,它要能盡量保持某種慣性,這樣使得螞蟻盡量向前方移動(開始,這個前方是隨機固定的一個方向),而不是原地無謂的打轉或者震動;其次,螞蟻要有一定的隨機性,雖然有了固定的方向,但它也不能像粒子一樣直線運動下去,而是有一個隨機的干擾。這樣就使得螞蟻運動起來具有了一定的目的性,盡量保持原來的方向,但又有新的試探,尤其當碰到障礙物的時候它會立即改變方向,這可以看成一種選擇的過程,也就是環境的障礙物讓螞蟻的某個方向正確,而其他方向則不對。這就解釋了為什麼單個螞蟻在復雜的諸如迷宮的地圖中仍然能找到隱蔽得很好的食物。
當然,在有一隻螞蟻找到了食物的時候,其他螞蟻會沿著信息素很快找到食物的。
螞蟻如何找到最短路徑的?這一是要歸功於信息素,另外要歸功於環境,具體說是計算機時鍾。信息素多的地方顯然經過這里的螞蟻會多,因而會有更多的螞蟻聚集過來。假設有兩條路從窩通向食物,開始的時候,走這兩條路的螞蟻數量同樣多(或者較長的路上螞蟻多,這也無關緊要)。當螞蟻沿著一條路到達終點以後會馬上返回來,這樣,短的路螞蟻來回一次的時間就短,這也意味著重復的頻率就快,因而在單位時間里走過的螞蟻數目就多,灑下的信息素自然也會多,自然會有更多的螞蟻被吸引過來,從而灑下更多的信息素……;而長的路正相反,因此,越來越多地螞蟻聚集到較短的路徑上來,最短的路徑就近似找到了。也許有人會問局部最短路徑和全局最短路的問題,實際上螞蟻逐漸接近全局最短路的,為什麼呢?這源於螞蟻會犯錯誤,也就是它會按照一定的概率不往信息素高的地方走而另闢蹊徑,這可以理解為一種創新,這種創新如果能縮短路途,那麼根據剛才敘述的原理,更多的螞蟻會被吸引過來。
引申:
跟著螞蟻的蹤跡,你找到了什麼?通過上面的原理敘述和實際操作,我們不難發現螞蟻之所以具有智能行為,完全歸功於它的簡單行為規則,而這些規則綜合起來具有下面兩個方面的特點:
1、多樣性
2、正反饋
多樣性保證了螞蟻在覓食的時候不置走進死胡同而無限循環,正反饋機制則保證了相對優良的信息能夠被保存下來。我們可以把多樣性看成是一種創造能力,而正反饋是一種學習強化能力。正反饋的力量也可以比喻成權威的意見,而多樣性是打破權威體現的創造性,正是這兩點小心翼翼的巧妙結合才使得智能行為涌現出來了。
引申來講,大自然的進化,社會的進步、人類的創新實際上都離不開這兩樣東西,多樣性保證了系統的創新能力,正反饋保證了優良特性能夠得到強化,兩者要恰到好處的結合。如果多樣性過剩,也就是系統過於活躍,這相當於螞蟻會過多的隨機運動,它就會陷入混沌狀態;而相反,多樣性不夠,正反饋機制過強,那麼系統就好比一潭死水。這在蟻群中來講就表現為,螞蟻的行為過於僵硬,當環境變化了,螞蟻群仍然不能適當的調整。
既然復雜性、智能行為是根據底層規則涌現的,既然底層規則具有多樣性和正反饋特點,那麼也許你會問這些規則是哪裡來的?多樣性和正反饋又是哪裡來的?我本人的意見:規則來源於大自然的進化。而大自然的進化根據剛才講的也體現為多樣性和正反饋的巧妙結合。而這樣的巧妙結合又是為什麼呢?為什麼在你眼前呈現的世界是如此栩栩如生呢?答案在於環境造就了這一切,之所以你看到栩栩如生的世界,是因為那些不能夠適應環境的多樣性與正反饋的結合都已經死掉了,被環境淘汰了!
參數說明:
最大信息素:螞蟻在一開始擁有的信息素總量,越大表示程序在較長一段時間能夠存在信息素。信息素消減的速度:隨著時間的流逝,已經存在於世界上的信息素會消減,這個數值越大,那麼消減的越快。
錯誤概率表示這個螞蟻不往信息素最大的區域走的概率,越大則表示這個螞蟻越有創新性。
速度半徑表示螞蟻一次能走的最大長度,也表示這個螞蟻的感知范圍。
記憶能力表示螞蟻能記住多少個剛剛走過點的坐標,這個值避免了螞蟻在本地打轉,停滯不前。而這個值越大那麼整個系統運行速度就慢,越小則螞蟻越容易原地轉圈。
-----例子-----
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><HEAD>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
<title>蟻群演算法js版</title>
<style>
.ant{
position:absolute;
background-color:#000000;
overflow:hidden;
width:2px;
height:2px;
}
.food{
position:absolute;
background-color:#0000ff;
overflow:hidden;
width:2px;
height:2px;
}
.nest{
position:absolute;
background-color:#ff0000;
overflow:hidden;
width:2px;
height:2px;
}
</style>
<script type="text/JavaScript">
//============================
//系統參數初始化
//----------------------------
//生命體數量與軌跡長度
Unit=10;Path=30;
//生命體速度上下限
v0=2;vM=10;
//生命體加速度變化范圍
Kr=0.1;Kv=0.1*(vM-v0);
//生命體運動范圍
x0=0;xM=document.documentElement.clientWidth;
y0=0;yM=document.documentElement.clientHeight;
//生命體出生地(巢穴)
xi0=x0+(xM-x0)*Math.random();
yi0=y0+(yM-y0)*Math.random();
str0='<div class="ant" style="left:'+xi0+';top:'+yi0+';"></div>';
//食物所在地
xf=x0+(xM-x0)*Math.random();
yf=y0+(yM-y0)*Math.random();
//氣味感知范圍
R_2=5*5;
//============================
var r=new Array();
var v=new Array();
var dr=new Array();
var dv=new Array();
var x=new Array();
var y=new Array();
var life=new Array();
//單擊暫停
var xi0,yi0,xf,yf;
var Time0,str0;
window.status='pause';
function document.onclick(){
if(window.status=='pause'){
window.status=0;
nest.style.left=xi0;
nest.style.top=yi0;
food.style.left=xf;
food.style.top=yf;
//測試初始化時間用
Time0=(new Date()).getTime();
init(0);
}else{
window.status='pause';
}
}
//窗口大小調整後刷新頁面以調整系統參數
function window.onresize(){
// window.location.href=document.location;
}
//初始化函數
function init(i){
if(window.status!='pause'&&i<Unit){
if(!life){
document.body.appendChild(life=document.createElement(str0));
x=xi0;
y=yi0;
r=Math.random();
v=1/Math.random();
dr=Kr*Math.random();
dv=Kv*Math.random();
}
Move(i);
window.status=i+1;
setTimeout('init('+(i+1)+')',i);
// }else{
// alert('生成耗時:'+((new Date()).getTime()-Time0)+'ms');
}
}
//運動函數
Total=Unit*Path;
P2=2*Math.PI;
function Move(i){
if(window.status!='pause'){
k=i%Unit;
X=x[k];
Y=y[k];
R=r[k];
V=v[k];
if(!life){
str='<div class="ant" style="left:'+X+';top:'+Y+';"></div>';
document.body.appendChild(life=document.createElement(str));
}
obj=life;
R+=dr[k]*(2*Math.random()-1);
V+=dv[k]*(2*Math.random()-1);
X+=Math.sin(P2*R)*V;
Y+=Math.cos(P2*R)*V;
//遇到食物原路返回並減小角度變化
distance=(X-xf)*(X-xf)+(Y-yf)*(Y-yf);
if(distance<R_2){
R+=0.5;
r/=2;
v*=2;
}
distance=(X-xi0)*(X-xi0)+(Y-yi0)*(Y-yi0);
if(distance<R_2){
R+=0.5;
r/=2;
v*=2;
}
/*----------------------------------
/*================================*/
//碰撞邊界反彈
R=(X<x0||X>xM)?-R:R;
R=(Y<y0||Y>yM)?0.5-R:R;
X=x[k]+Math.sin(P2*R)*V;
Y=y[k]+Math.cos(P2*R)*V;
/*================================*/
//溢出邊界重生(類似流星效果)
if(X<x0||X>xM||Y<y0||Y>yM){
X=xi0;
Y=yi0;
}
/*----------------------------------
/*================================*/
//邊界限制
x[k]=X=(X<x0)?x0:(X>xM)?xM-2:X;
y[k]=Y=(Y<y0)?y0:(Y>yM)?yM-2:Y;
r[k]=R>1?R-1:R<0?R+1:R;
v[k]=V=(V<v0)?v0:((V<vM)?V:vM);
/*================================*/
obj.style.left=x[k]=X;
obj.style.top=y[k]=Y;
setTimeout('Move('+(i+Unit)%Total+')',Unit);
}
}
//根據瀏覽器自動載入動畫
switch(navigator.appName.toLowerCase()){
case "netscape":
window.addEventListener("load",document.onclick,false);
break;
case "microsoft internet explorer":
default:
window.attachEvent("onload",document.onclick);
break;
}
</script>
</head>
<body scroll="no">
<div id="food" class="food"></div>
<div id="nest" class="nest"></div>
</body>
</html>
⑺ 蟻群演算法的問題
螞蟻究竟是怎麼找到食物的呢?在沒有螞蟻找到食物的時候,環境沒有有用的信息素,那麼螞蟻為什麼會相對有效的找到食物呢?這要歸功於螞蟻的移動規則,尤其是在沒有信息素時候的移動規則。首先,它要能盡量保持某種慣性,這樣使得螞蟻盡量向前方移動(開始,這個前方是隨機固定的一個方向),而不是原地無謂的打轉或者震動;其次,螞蟻要有一定的隨機性,雖然有了固定的方向,但它也不能像粒子一樣直線運動下去,而是有一個隨機的干擾。這樣就使得螞蟻運動起來具有了一定的目的性,盡量保持原來的方向,但又有新的試探,尤其當碰到障礙物的時候它會立即改變方向,這可以看成一種選擇的過程,也就是環境的障礙物讓螞蟻的某個方向正確,而其他方向則不對。這就解釋了為什麼單個螞蟻在復雜的諸如迷宮的地圖中仍然能找到隱蔽得很好的食物。
當然,在有一隻螞蟻找到了食物的時候,大部分螞蟻會沿著信息素很快找到食物的。但不排除會出現這樣的情況:在最初的時候,一部分螞蟻通過隨機選擇了同一條路徑,隨著這條路徑上螞蟻釋放的信息素越來越多,更多的螞蟻也選擇這條路徑,但這條路徑並不是最優(即最短)的,所以,導致了迭代次數完成後,螞蟻找到的不是最優解,而是次優解,這種情況下的結果可能對實際應用的意義就不大了。
螞蟻如何找到最短路徑的?這一是要歸功於信息素,另外要歸功於環境,具體說是計算機時鍾。信息素多的地方顯然經過這里的螞蟻會多,因而會有更多的螞蟻聚集過來。假設有兩條路從窩通向食物,開始的時候,走這兩條路的螞蟻數量同樣多(或者較長的路上螞蟻多,這也無關緊要)。當螞蟻沿著一條路到達終點以後會馬上返回來,這樣,短的路螞蟻來回一次的時間就短,這也意味著重復的頻率就快,因而在單位時間里走過的螞蟻數目就多,灑下的信息素自然也會多,自然會有更多的螞蟻被吸引過來,從而灑下更多的信息素……;而長的路正相反,因此,越來越多地螞蟻聚集到較短的路徑上來,最短的路徑就近似找到了。也許有人會問局部最短路徑和全局最短路的問題,實際上螞蟻逐漸接近全局最短路的,為什麼呢?這源於螞蟻會犯錯誤,也就是它會按照一定的概率不往信息素高的地方走而另闢蹊徑,這可以理解為一種創新,這種創新如果能縮短路途,那麼根據剛才敘述的原理,更多的螞蟻會被吸引過來。
⑻ 關於蟻群演算法的旅遊路徑優化問題的【英文論文】
這是能幫助 而寫的,
⑼ 蟻群演算法是什麼
蟻群演算法,又稱螞蟻演算法,是一種用來在圖中尋找優化路徑的機率型演算法。 它由Marco Dorigo於1992年在他的博士論文中提出,其靈感來源於螞蟻在尋找食物過程中發現路徑的行為。蟻群演算法是一種模擬進化演算法,初步的研究表明該演算法具有許多優良的性質。針對PID控制器參數優化設計問題,將蟻群演算法設計的結果與遺傳演算法設計的結果進行了比較,數值模擬結果表明,蟻群演算法具有一種新的模擬進化優化方法的有效性和應用價值。
原理
設想,如果我們要為螞蟻設計一個人工智慧的程序,那麼這個程序要多麼復雜呢?首先,你要讓螞蟻能夠避開障礙物,就必須根據適當的地形給它編進指令讓他們能夠巧妙的避開障礙物,其次,要讓螞蟻找到食物,就需要讓他們遍歷空間上的所有點;再次,如果要讓螞蟻找到最短的路徑,那麼需要計算所有可能的路徑並且比較它們的大小,而且更重要的是,你要小心翼翼地編程,因為程序的錯誤也許會讓你前功盡棄。這是多麼不可思議的程序!太復雜了,恐怕沒人能夠完成這樣繁瑣冗餘的程序。
然而,事實並沒有你想得那麼復雜,上面這個程序每個螞蟻的核心程序編碼不過100多行!為什麼這么簡單的程序會讓螞蟻干這樣復雜的事情?答案是:簡單規則的涌現。事實上,每隻螞蟻並不是像我們想像的需要知道整個世界的信息,他們其實只關心很小范圍內的眼前信息,而且根據這些局部信息利用幾條簡單的規則進行決策,這樣,在蟻群這個集體里,復雜性的行為就會凸現出來。這就是人工生命、復雜性科學解釋的規律!那麼,這些簡單規則是什麼呢?
⑽ 請問蟻群演算法和遺傳演算法的優缺點比較(不要一大段一大段的,簡潔概括即可)
遺傳演算法有比較強的全局搜索能力,特別是當交叉概率比較大時,能產生大量的新個體,提高了全局搜索范圍,遺傳演算法適合求解離散問題,具備數學理論支持,但是存在著漢明懸崖等問題。
蟻群演算法適合在圖上搜索路徑問題,計算開銷會大。
兩者都是隨機演算法,只不過遺傳演算法是仿生學的演算法;蟻群演算法是數學演算法,是應用目前最廣的演算法 。針對不同的研究方向,它所體現出來的優缺點是不一樣的,將這兩個演算法混合,優勢互補,提高優化性能,並且分別來求解離散空間的和連續空間的優化問題。
希望可以幫到您,望採納!