蟻群算法聚類(lèi)設(shè)計(jì)第一頁(yè)，共25頁(yè)。主講：周潤(rùn)景教授單位：電子信息工程學(xué)院蟻群算法聚類(lèi)設(shè)計(jì)第二頁(yè)，共25頁(yè)。目錄

算法的提出算法的基本原理模型建立算法的實(shí)現(xiàn)算法改進(jìn)結(jié)論

第三頁(yè)，共25頁(yè)。一.蟻群算法的提出蟻群算法(antcolonyoptimization,ACO)，又稱(chēng)螞蟻算法，是一種用來(lái)尋找優(yōu)化路徑的機(jī)率型算法。它由MarcoDorigo于1992年在他的博士論文中提出，其靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。遺傳算法在模式識(shí)別、神經(jīng)網(wǎng)絡(luò)、機(jī)器學(xué)習(xí)、工業(yè)優(yōu)化控制、自適應(yīng)控制、生物科學(xué)、社會(huì)科學(xué)等方面都得到應(yīng)用。MacroDorigo第四頁(yè)，共25頁(yè)。二.算法的基本原理NestFoodObstacle圖1螞蟻正常行進(jìn)，突然環(huán)境改變，增加了障礙物第五頁(yè)，共25頁(yè)。二.算法的基本原理NestFoodObstacle圖2螞蟻以等同概率選擇各條路徑較短路徑信息素濃度高，選擇該路徑的螞蟻增多第六頁(yè)，共25頁(yè)。二.算法的基本原理圖3螞蟻選路過(guò)程示例EABDHCEABDHCd=0.5d=0.5d=1d=130ants30ants15ants15ants15ants15antst=0EABDHC30ants30ants20ants20ants10ants10antst=1第七頁(yè)，共25頁(yè)。二.算法的基本原理NestFoodObstacle圖4螞蟻?zhàn)罱K繞過(guò)障礙物找到最優(yōu)路徑第八頁(yè)，共25頁(yè)。三.模型建立基于螞蟻構(gòu)造墓地和分類(lèi)幼體的聚類(lèi)分析模型基于螞蟻覓食行為和信息素的聚類(lèi)分析模型

第九頁(yè)，共25頁(yè)。三.模型建立1.基于螞蟻構(gòu)造墓地和分類(lèi)幼體的聚類(lèi)分析模型蟻群構(gòu)造墓地行為和分類(lèi)幼體行為統(tǒng)稱(chēng)之為蟻群聚類(lèi)行為。生物學(xué)家經(jīng)過(guò)長(zhǎng)期的觀察發(fā)現(xiàn)，在螞蟻群體中存在一種本能的聚集行為。螞蟻往往能在沒(méi)有關(guān)于螞蟻整體的任何指導(dǎo)性信息情況下，將其死去的同伴的尸體安放在一個(gè)固定的場(chǎng)所。第十頁(yè)，共25頁(yè)。三.模型建立真實(shí)蟻群的聚類(lèi)行為

DeneubougJL等人也用pheidolepallidula螞蟻?zhàn)隽藢?shí)驗(yàn)。發(fā)現(xiàn)蟻群會(huì)根據(jù)螞蟻幼體的大小將其放置在不同的位置，分別把其堆放在蟻穴周?chē)椭醒氲奈恢?。真?shí)的蟻群聚類(lèi)行為的實(shí)驗(yàn)結(jié)果右圖，四張照片分別對(duì)應(yīng)為實(shí)驗(yàn)初始狀態(tài)、3小時(shí)、6小時(shí)和36小時(shí)的蟻群聚類(lèi)情況。第十一頁(yè)，共25頁(yè)。三.模型建立基本模型經(jīng)過(guò)利用個(gè)體與個(gè)體和個(gè)體與環(huán)境之間的交互作用，實(shí)現(xiàn)了自組織聚類(lèi)，并成功的應(yīng)用于機(jī)器人的控制中(一群類(lèi)似于螞蟻的機(jī)器人在二維網(wǎng)格中隨意移動(dòng)并可以搬運(yùn)基本物體，最終把它們聚集在一起)。該模型成功的應(yīng)用引起了各國(guó)學(xué)者的廣泛關(guān)注和研究的熱潮。LumerE和FaietaB通過(guò)在Denurbourg的基本分類(lèi)模型中引入數(shù)據(jù)對(duì)象之間相似度的概念，提出了LF聚類(lèi)分析算法，并成功的將其應(yīng)用到數(shù)據(jù)分析中。第十二頁(yè)，共25頁(yè)。三.模型建立2.基于螞蟻覓食行為和信息素的聚類(lèi)分析模型螞蟻在覓食的過(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)象。第十三頁(yè)，共25頁(yè)。四.算法的實(shí)現(xiàn)由于蟻群優(yōu)化算法是迭代求取最優(yōu)值，所以事先無(wú)需訓(xùn)練數(shù)據(jù)，故取59組數(shù)據(jù)確定類(lèi)別。流程圖如下：第十四頁(yè)，共25頁(yè)。四.算法的實(shí)現(xiàn)重要程序代碼介紹：1.程序初始化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;%最佳路徑度量值（初值為無(wú)窮大，該值越小聚類(lèi)效果越好）2.信息素矩陣初始化信息素矩陣維數(shù)為N*K（樣本數(shù)*聚類(lèi)數(shù)）初始值為0.01。c=10^-2;tau=ones(N,K)*c;%信息素矩陣，初始值為0.01的N*K矩陣（樣本數(shù)*聚類(lèi)數(shù)）第十五頁(yè)，共25頁(yè)。四.算法的實(shí)現(xiàn)3.螞蟻路徑的選擇及標(biāo)識(shí)定義標(biāo)識(shí)字符矩陣solution_string，維數(shù)為R*N+1，初始值都為0，以信息矩陣中信息素的值確定路徑（即確定分到哪一組），具體方法如下：如果該樣本各信息素的值都小于信息素閾值q，則取信息素最大的為作為路徑。若最大值有多個(gè)，則從相同的最大值中隨機(jī)取一個(gè)，作為路徑。若信息數(shù)大于閾值q，則求出各路徑信息素占該樣本總信息素的比例，以概率確定路徑。4.聚類(lèi)中心選擇聚類(lèi)中心為該類(lèi)所有樣本的各屬性值的平均值。5.偏離誤差計(jì)算偏離誤差的計(jì)算，即各樣本到其對(duì)應(yīng)的聚類(lèi)中心的歐式距離之和MIN。MIN越小，聚類(lèi)效果越好。計(jì)算各只螞蟻的MIN值，找到最小的MIN值，該值對(duì)應(yīng)的路徑為本次迭代的最佳路徑。第十六頁(yè)，共25頁(yè)。四.算法的實(shí)現(xiàn)6.信息素更新對(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á)到要求值。第十七頁(yè)，共25頁(yè)。四.算法的實(shí)現(xiàn)程序運(yùn)行完以后，聚類(lèi)結(jié)果如圖所示。從圖中可以看出基本蟻群聚類(lèi)法的分類(lèi)效果不太好。第十八頁(yè)，共25頁(yè)。四.算法的實(shí)現(xiàn)程序運(yùn)行結(jié)果：t=1001time=23.4018cluster_center=1.0e+03*1.37102.61871.88721.39502.49972.11241.14382.61962.06131.60242.16732.0350best_solution_function_value=6.3409e+04index1=34614192734374144484957index2=12791523244043455058index3=5812131718282932383946545556index4=1至15列10111620212225263031333536424716至19列

525359第十九頁(yè)，共25頁(yè)。五.算法改進(jìn)基于遺傳變異的算法改進(jìn)第二十頁(yè)，共25頁(yè)。五.算法改進(jìn)改進(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第二十一頁(yè)，共25頁(yè)。五.算法改進(jìn)程序運(yùn)行完后，仿真結(jié)果如圖所示。從圖中可以看出MMAS聚類(lèi)效果比基本蟻群聚類(lèi)效果要好，但分類(lèi)效果還不是太好，說(shuō)明該三元色不適合使用該算法分類(lèi)。第二十二頁(yè)，共25頁(yè)。五.算法改進(jìn)程序運(yùn)行結(jié)果：t=1001time=84.9270cluster_center=1.0e+03*1.90952.34531.67050.47093.10522.26641.70532.02212.13051.62032.15572.0522best_solution_function_value=4.1595e+04index1=1至15列13814151922242633363941434516列47第二十三頁(yè)，共25頁(yè)。五.算法改進(jìn)index2=1至15列256910121323272829