蟻群算法PPT課件

.,1,蟻群算法的基本原理及其改進算法,專業(yè)：控制工程年級：2009級姓名：胡訓智學號：30956060指導老師：周潤景教授,.,2,算法的提出算法的基本原理模型建立算法的實現(xiàn)算法改進結論參考文獻,.,3,蟻群算法的提出,蟻群算法(antcolonyoptimization,ACO)，又稱螞蟻算法，是一種用來尋找優(yōu)化路徑的機率型算法。它由MarcoDorigo于1992年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。,MacroDorigo,.,4,基本原理,圖1螞蟻正常行進，突然環(huán)境改變，增加了障礙物,.,5,基本原理,圖2螞蟻以等同概率選擇各條路徑較短路徑信息素濃度高，選擇該路徑的螞蟻增多,.,6,基本原理,圖3螞蟻選路過程示例,.,7,基本原理,圖4螞蟻最終繞過障礙物找到最優(yōu)路徑,.,8,模型建立,基于螞蟻構造墓地和分類幼體的聚類分析模型基于螞蟻覓食行為和信息素的聚類分析模型,.,9,基于螞蟻構造墓地和分類幼體的聚類分析模型,蟻群構造墓地行為和分類幼體行為統(tǒng)稱之為蟻群聚類行為。生物學家經(jīng)過長期的觀察發(fā)現(xiàn)，在螞蟻群體中存在一種本能的聚集行為。螞蟻往往能在沒有關于螞蟻整體的任何指導性信息情況下，將其死去的同伴的尸體安放在一個固定的場所。,.,10,真實蟻群的聚類行為,DeneubougJL等人也用pheidolepallidula螞蟻做了實驗。發(fā)現(xiàn)蟻群會根據(jù)螞蟻幼體的大小將其放置在不同的位置，分別把其堆放在蟻穴周圍和中央的位置。真實的蟻群聚類行為的實驗結果右圖，四張照片分別對應為實驗初始狀態(tài)、3小時、6小時和36小時的蟻群聚類情況。,.,11,基于螞蟻構造墓地和分類幼體的聚類分析模型,基本模型經(jīng)過利用個體與個體和個體與環(huán)境之間的交互作用，實現(xiàn)了自組織聚類，并成功的應用于機器人的控制中(一群類似于螞蟻的機器人在二維網(wǎng)格中隨意移動并可以搬運基本物體，最終把它們聚集在一起)。該模型成功的應用引起了各國學者的廣泛關注和研究的熱潮。LumerE和FaietaB通過在Denurbourg的基本分類模型中引入數(shù)據(jù)對象之間相似度的概念，提出了LF聚類分析算法，并成功的將其應用到數(shù)據(jù)分析中。,.,12,基于螞蟻覓食行為和信息素的聚類分析模型,螞蟻在覓食的過程中，能夠分為搜索食物和搬運食物兩個環(huán)節(jié)。每個螞蟻在運動過程中都將會在其所經(jīng)過的路徑上留下信息素，而且能夠感知到信息素的存在及其強度，比較傾向于向信息素強度高的方向移動，同樣信息素自身也會隨著時間的流逝而揮發(fā)，顯然某一路徑上經(jīng)過的螞蟻數(shù)目越多，那么其信息素就越強，以后的螞蟻選擇該路徑的可能性就比較高，整個蟻群的行為表現(xiàn)出了信息正反饋現(xiàn)象。,.,13,程序流程圖,.,14,程序初始化,X=load(data.txt);N,n=size(X);%N=測試樣本數(shù);n=測試樣本的屬性數(shù);K=4;%K=組數(shù);R=100;%R=螞蟻數(shù);t_max=1000;%t_max=最大迭代次數(shù);best_solution_function_value=inf;,.,15,信息素矩陣初始化,信息素矩陣維數(shù)為N*K（樣本數(shù)*聚類數(shù)）初始值為0.01。c=10-2;tau=ones(N,K)*c;%信息素矩陣，初始值為0.01的N*K矩陣（樣本數(shù)*聚類數(shù)）,.,16,螞蟻路徑的選擇及標識,定義標識字符矩陣solution_string，維數(shù)為R*N+1，初始值都為0，以信息矩陣中信息素的值確定路徑（即確定分到哪一組），具體方法如下：如果該樣本各信息素的值都小于信息素閾值q，則取信息素最大的為作為路徑。若最大值有多個，則從相同的最大值中隨機取一個，作為路徑。若信息數(shù)大于閾值q，則求出各路徑信息素占該樣本總信息素的比例，以概率確定路徑。,.,17,聚類中心選擇,聚類中心為該類所有樣本的各屬性值的平均值。,.,18,偏離誤差計算,偏離誤差的計算，即各樣本到其對應的聚類中心的歐式距離之和MIN。MIN越小，聚類效果越好。計算各只螞蟻的MIN值，找到最小的MIN值，該值對應的路徑為本次迭代的最佳路徑。,.,19,信息素更新,對信息素矩陣進行更新，更新方法為新值為原信息素值乘以(1-rho)，rho為信息素蒸發(fā)率，在加上最小偏差值的倒數(shù)。fori=1:Ntau(i,best_solution(1,i)=(1-rho)*tau(i,best_solution(1,i)+1/tau_F;信息數(shù)更新之后，再根據(jù)新的信息數(shù)矩陣，判斷路徑。進行迭代運算。直到達到最大迭代次數(shù)，或偏離誤差達到要求值。,.,20,參數(shù)調試（螞蟻數(shù)R最大迭代次數(shù)t_max）,.,21,MIN=30690,實驗結果,此時的聚類效果還未最佳，應繼續(xù)迭代。,.,22,實驗結果,t=3915time=229.4707best_solution_function_value=1.9726e+004index1=6151619243335index2=118223034424748index3=238910131417212326272931394043464951index4=45711122025283236373841444550該算法的聚類結果跟標準聚類結果相同。,.,23,實驗結果,MIN=19726,此時已達到較好的聚類效果,.,24,算法改進,基于遺傳變異的算法改進,.,25,改進代碼,pls=0.1;%局部尋優(yōu)閾值pls（相當于變異率）solution_temp=zeros(L,N+1);k=1;while(k=L)solution_temp(k,:)=solution_ascend(k,:);rp=rand(1,N);%產(chǎn)生一個1*N(51)維的隨機數(shù)組，fori=1:Nifrp(i)=pls%某值小于pls則隨機改變其對應的路徑標識current_cluster_number=setdiff(1:K,solution_temp(k,i);rrr=randint(1,1,1,K-1);change_cluster=current_cluster_number(rrr);solution_temp(k,i)=change_cluster;endend,.,26,參數(shù)調試（局部尋優(yōu)參數(shù)pls）,.,27,改進后聚類效果對比,.,28,改進后聚類效果對比,基于遺傳算法的改進之后縮短了迭代次數(shù)，減少了計算量。聚類的效果要優(yōu)于基本的蟻群算法。,.,29,結論,該算法的聚類結果跟標準聚類結果完全相同；蟻群算法不僅能夠智能搜索、全局優(yōu)化，而且具有穩(wěn)健性、魯棒性、正反饋、分布式計算、易與其它算法相結合等特點。利用正反饋原理，可以加快進化過程:分布式計算使該算法易于并行實現(xiàn)，個體之間不斷進行信息交流和傳遞，有利于找到較好的解；該算法易與多種啟發(fā)式算法結合，可改善算法的性能；由于魯棒性強，故在基本蟻群算法模型的基礎上進行改進，便可用于其它問題。因此，蟻群算法的問世為諸多領域解決復雜優(yōu)化問題提供了有力的工具。,.,30,參考文獻,趙霞，“MAX一MIN螞蟻系統(tǒng)算法及其收斂性證明，I，計算機工程與應用，2006(8.)朱慶保，楊志軍，基于變異和動態(tài)信息素更新的蟻群優(yōu)化算法.軟件學報，2004(2).王劍，李平，楊春節(jié)，“蟻群算法的理論與應用”，機電工程，2003(5).JuliaHandl，JoshuaKnowles，MareoDorigo.Ant-basedclusteringandtoPograPhiemappingJArtificialLife，2008，12(1)吳斌,史忠植.一種基于蟻群算法的TSP問題分段求解算法J.計算機學報,2001,24(12).,.,31,參考文獻,吳慶洪,張紀會,徐心和.具有變異特征的蟻群算法J.計算機研究與發(fā)展,1993,36(10):1240-1245.朱慶保,楊志軍.基于變異和動態(tài)信息素更新的蟻群優(yōu)化算法J.軟件學報