蟻群算法PPT課件

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