蟻群算法聚類設計.pptx

《蟻群算法聚類設計.pptx》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、主講：周潤景教授單位：電子信息工程學院蟻群算法聚類設計目錄算法的提出算法的基本原理模型建立算法的實現(xiàn)算法改進結論一.蟻群算法的提出蟻群算法(antcolonyoptimization,ACO)，又稱螞蟻算法，是一種用來尋找優(yōu)化路徑的機率型算法。它由MarcoDorigo于1992年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。遺傳算法在模式識別、神經(jīng)網(wǎng)絡、機器學習、工業(yè)優(yōu)化控制、自適應控制、生物科學、社會科學等方面都得到應用。MacroDorigo二.算法的基本原理NestFoodObstacle圖

2、1螞蟻正常行進，突然環(huán)境改變，增加了障礙物二.算法的基本原理NestFoodObstacle圖2螞蟻以等同概率選擇各條路徑較短路徑信息素濃度高，選擇該路徑的螞蟻增多二.算法的基本原理圖3螞蟻選路過程示例EABDHCEABDHCd=0.5d=0.5d=1d=130ants30ants15ants15ants15ants15antst=0EABDHC30ants30ants20ants20ants10ants10antst=1二.算法的基本原理NestFoodObstacle圖4螞蟻最終繞過障礙物找到最優(yōu)路徑三.模型建立基于螞

3、蟻構造墓地和分類幼體的聚類分析模型基于螞蟻覓食行為和信息素的聚類分析模型三.模型建立1.基于螞蟻構造墓地和分類幼體的聚類分析模型蟻群構造墓地行為和分類幼體行為統(tǒng)稱之為蟻群聚類行為。生物學家經(jīng)過長期的觀察發(fā)現(xiàn)，在螞蟻群體中存在一種本能的聚集行為。螞蟻往往能在沒有關于螞蟻整體的任何指導性信息情況下，將其死去的同伴的尸體安放在一個固定的場所。三.模型建立真實蟻群的聚類行為DeneubougJL等人也用pheidolepallidula螞蟻做了實驗。發(fā)現(xiàn)蟻群會根據(jù)螞蟻幼體的大小將其放置在不同的位置，分別把其堆放在蟻穴周圍和中央的位

4、置。真實的蟻群聚類行為的實驗結果右圖，四張照片分別對應為實驗初始狀態(tài)、3小時、6小時和36小時的蟻群聚類情況。三.模型建立基本模型經(jīng)過利用個體與個體和個體與環(huán)境之間的交互作用，實現(xiàn)了自組織聚類，并成功的應用于機器人的控制中(一群類似于螞蟻的機器人在二維網(wǎng)格中隨意移動并可以搬運基本物體，最終把它們聚集在一起)。該模型成功的應用引起了各國學者的廣泛關注和研究的熱潮。LumerE和FaietaB通過在Denurbourg的基本分類模型中引入數(shù)據(jù)對象之間相似度的概念，提出了LF聚類分析算法，并成功的將其應用到數(shù)據(jù)分析中。三.模型建

5、立2.基于螞蟻覓食行為和信息素的聚類分析模型螞蟻在覓食的過程中，能夠分為搜索食物和搬運食物兩個環(huán)節(jié)。每個螞蟻在運動過程中都將會在其所經(jīng)過的路徑上留下信息素，而且能夠感知到信息素的存在及其強度，比較傾向于向信息素強度高的方向移動，同樣信息素自身也會隨著時間的流逝而揮發(fā)，顯然某一路徑上經(jīng)過的螞蟻數(shù)目越多，那么其信息素就越強，以后的螞蟻選擇該路徑的可能性就比較高，整個蟻群的行為表現(xiàn)出了信息正反饋現(xiàn)象。四.算法的實現(xiàn)由于蟻群優(yōu)化算法是迭代求取最優(yōu)值，所以事先無需訓練數(shù)據(jù)，故取59組數(shù)據(jù)確定類別。流程圖如下：四.算法的實現(xiàn)重要程序代

6、碼介紹：1.程序初始化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;%最佳路徑度量值（初值為無窮大，該值越小聚類效果越好）2.信息素矩陣初始化信息素矩陣維數(shù)為N*K（樣本數(shù)*聚類數(shù)）初始值為0.01。c=10^-2;tau=ones(N,K)*c;%信息素矩陣，初始值為0.01的N*K矩陣（樣本數(shù)*聚類數(shù)

7、）四.算法的實現(xiàn)3.螞蟻路徑的選擇及標識定義標識字符矩陣solution_string，維數(shù)為R*N+1，初始值都為0，以信息矩陣中信息素的值確定路徑（即確定分到哪一組），具體方法如下：如果該樣本各信息素的值都小于信息素閾值q，則取信息素最大的為作為路徑。若最大值有多個，則從相同的最大值中隨機取一個，作為路徑。若信息數(shù)大于閾值q，則求出各路徑信息素占該樣本總信息素的比例，以概率確定路徑。4.聚類中心選擇聚類中心為該類所有樣本的各屬性值的平均值。5.偏離誤差計算偏離誤差的計算，即各樣本到其對應的聚類中心的歐式距離之和MIN。

8、MIN越小，聚類效果越好。計算各只螞蟻的MIN值，找到最小的MIN值，該值對應的路徑為本次迭代的最佳路徑。四.算法的實現(xiàn)6.信息素更新對信息素矩陣進行更新，更新方法為：新值為原信息素值乘以(1-rho)，rho為信息素蒸發(fā)率，在加上最小偏差值的倒數(shù)。程序如下：fori=1:Ntau(i,best_sol