資源描述：
《蟻群算法聚類(lèi)設(shè)計(jì).pptx》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、主講：周潤(rùn)景教授單位：電子信息工程學(xué)院蟻群算法聚類(lèi)設(shè)計(jì)目錄算法的提出算法的基本原理模型建立算法的實(shí)現(xiàn)算法改進(jìn)結(jié)論一.蟻群算法的提出蟻群算法(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二.算法的基本原理NestFoodObstacle圖
2、1螞蟻正常行進(jìn)，突然環(huán)境改變，增加了障礙物二.算法的基本原理NestFoodObstacle圖2螞蟻以等同概率選擇各條路徑較短路徑信息素濃度高，選擇該路徑的螞蟻增多二.算法的基本原理圖3螞蟻選路過(guò)程示例EABDHCEABDHCd=0.5d=0.5d=1d=130ants30ants15ants15ants15ants15antst=0EABDHC30ants30ants20ants20ants10ants10antst=1二.算法的基本原理NestFoodObstacle圖4螞蟻?zhàn)罱K繞過(guò)障礙物找到最優(yōu)路徑三.模型建立基于螞
3、蟻構(gòu)造墓地和分類(lèi)幼體的聚類(lèi)分析模型基于螞蟻覓食行為和信息素的聚類(lèi)分析模型三.模型建立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)所。三.模型建立真實(shí)蟻群的聚類(lèi)行為DeneubougJL等人也用pheidolepallidula螞蟻?zhàn)隽藢?shí)驗(yàn)。發(fā)現(xiàn)蟻群會(huì)根據(jù)螞蟻幼體的大小將其放置在不同的位置，分別把其堆放在蟻穴周?chē)椭醒氲奈?/p>
4、置。真實(shí)的蟻群聚類(lèi)行為的實(shí)驗(yàn)結(jié)果右圖，四張照片分別對(duì)應(yīng)為實(shí)驗(yàn)初始狀態(tài)、3小時(shí)、6小時(shí)和36小時(shí)的蟻群聚類(lèi)情況。三.模型建立基本模型經(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ù)分析中。三.模型建
5、立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)象。四.算法的實(shí)現(xiàn)由于蟻群優(yōu)化算法是迭代求取最優(yōu)值，所以事先無(wú)需訓(xùn)練數(shù)據(jù)，故取59組數(shù)據(jù)確定類(lèi)別。流程圖如下：四.算法的實(shí)現(xiàn)重要程序代
6、碼介紹：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ù)
7、）四.算法的實(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。
8、MIN越小，聚類(lèi)效果越好。計(jì)算各只螞蟻的MIN值，找到最小的MIN值，該值對(duì)應(yīng)的路徑為本次迭代的最佳路徑。四.算法的實(shí)現(xiàn)6.信息素更新對(duì)信息素矩陣進(jìn)行更新，更新方法為：新值為原信息素值乘以(1-rho)，rho為信息素蒸發(fā)率，在加上最小偏差值的倒數(shù)。程序如下：fori=1:Ntau(i,best_sol
