【正文】 信息素矩陣、與問題相關的某種特征模式。在每組中，一個處理器負責構建螞蟻的行程，并代表組內每個奴隸評估解決方案的元素。這個操作的計算量非常大，尤其是需要訪問約束條件時。主處理器負責接收用戶輸入，將螞蟻放在隨機的的路徑起點，并執(zhí)行全局信息素更新和產生輸出。如何定義表現(xiàn)最好的蟻群是一個問題，因為有許多可供使用的不同的度量標準。任何參數(shù)都可以經(jīng)過處理器加以更改。策略：并行策略的選擇對于蟻群算法的并行實現(xiàn)至關重要。 PACOA基本思想與策略思想：蟻群算法并行化的基本思想是把原來的串行算法中的1個蟻群(m只螞蟻)分為P個子蟻群，每個子蟻群分配1個處理機。蟻群算法是一種智能優(yōu)化算法，已經(jīng)成功解決了多種優(yōu)化問題?，F(xiàn)實中的螞蟻是并行的搜尋食物，并逐漸形成一條從蟻穴到食物的最短路徑，蟻群算法繼承了真實螞蟻的這種并行機制。4 并行的聚類蟻群優(yōu)化算法PACOA PACOA算法的基本思想產生的背景在很多工業(yè)調度問題的環(huán)境中，某些優(yōu)化的算法需要相當長的時間周期，并且甚至在有限的時間內不能產生出一個令人滿意的結果和可行的解決方案，對于這類問題，用元啟發(fā)模型已經(jīng)能夠提供有效的解決方案，而基于聚類蟻群優(yōu)化的元啟發(fā)算法已經(jīng)運行到這類的工業(yè)調度的問題。用戶不必處理迭代劃分、數(shù)據(jù)共享、線程調度及同步等低級別的細節(jié)。OpenMP是通過與標準Fortran，C和C++結合進行工作的，對于同步共享變量、合理分配負載等任務，都提供了有效的支持，具有簡單通用、開發(fā)快速的特點。對不同的語言，有不同的OpenMP標準，現(xiàn)在基于C/C++。 OpenMP產生背景OpenMP是國際上繼MPI之后于I998年推出的工業(yè)標準。MPI Comm_size（）函數(shù)獲取通信域中的進程個數(shù)，由size返回。它們構成了MPICH庫的最小子集，利用這6個函數(shù)就可以編寫出基本的并行程序。MPI最終目的是為進程間通信服務。 MPI與OPENMP并行編程 MPI介紹MPI(Message Passing Interface)是一個工業(yè)標準，該標準是為統(tǒng)一不同的大規(guī)模并行處理機制造商的消息傳遞接口而制訂的。運行在SIMD機器模型上的并行算法屬于同步并行算法，其處理機之間的同步由硬件實現(xiàn)。并行算法可以分為數(shù)值并行算法和非數(shù)值并行算法，或同步并行算法以及異步并行算法和分布式并行算法，或SI肋／MI如并行算法和VLSI并行算法等。并行計算機系統(tǒng)除了少數(shù)的專用SIMD系統(tǒng)外，絕大部分是MIMD系統(tǒng)。根據(jù)對象的空間分布狀態(tài)指導螞蟻間的相互作用完成聚類的，如基于螞蟻堆的形成原理的聚類方法都是根據(jù)對象在網(wǎng)格上的分布情況實現(xiàn)的；其中基于螞蟻的混合聚類方法，交替使用聚類蟻群方法和kmeans算法，加速算法收斂并提高了聚類質量。表示螞蟻被接受程度，如果具有相同標簽的螞蟻相遇或兩只螞蟻彼此接受對方，增加，否則螞蟻不接受時減少。模板是由螞蟻的基因和接受閥值組成的，前者對應于數(shù)據(jù)集的對象且在算法過程中不斷變化，后者是在初始化階段獲得的，它是螞蟻與其它螞蟻相遇期間觀察到的最大相似度和平均相似度的函數(shù)，它是動態(tài)的，螞蟻每次和其它螞蟻相會后對它進行修改[3942]。標簽是由螞蟻基因及螞蟻間不斷交換化學物質決定的。對每只螞蟻都定義一個相似度閥值和相異度閥值，并且由進行局部更新，用來判斷螞蟻表示的數(shù)據(jù)與其它螞蟻表示的數(shù)據(jù)的相似或相異程度。每對數(shù)據(jù)的相似度值在之間（表示數(shù)據(jù)集內的對象個數(shù)），0意味著完全不同，1表示他們相同。假設螞蟻能夠到達樹的任何地方并能粘在該結構的任何位置，不過在結構樹形成的過程中由于受對象間的作用，螞蟻更趨于固定在樹枝的末端[3536]。螞蟻覓食原理應用到數(shù)據(jù)聚類中，可以將數(shù)據(jù)視為具有不同屬性的螞蟻，聚類中心既是螞蟻所要尋找的“食物源”，那么數(shù)據(jù)聚類過程可以看作螞蟻尋找食物源的過程。螞蟻在運動過程中，能夠在它所經(jīng)過的路徑上留下信息素，而且螞蟻在運動過程中能感知信息素的存在及其強度，并指導自己運動方向，螞蟻傾向于朝著信息素強度高的方向上移動。與這個方法相似的另一種是與模糊C均值相結合的方法[30]，基于相對簡單智能體直接或間接的反饋完成聚類。這次是對對象堆上而不是單個對象運用算法.?；旌暇垲愃惴ˋntClass主要包括四個步驟：（1）在所要聚類的對象上進行聚類蟻群；（2）利用初始劃分結果進行K均值算法；（3）在堆上運用聚類蟻群；（4）對對象堆再次運用K均值算法。而在混合聚類算法中，Monmarche建議一個網(wǎng)格單元內可以放置多個對象，每只螞蟻的搬運能力為，代替過去一只螞蟻一次只能搬運一個對象。利用這種方法擺脫了大多數(shù)聚類方法對數(shù)據(jù)的聚類基本特征先驗信息的依賴，通過兩階段的算法結構即可實現(xiàn)對數(shù)據(jù)的聚類。傳統(tǒng)的算法大都是伴隨著某一特定的問題模式，有著相當多的限制條件，而聚類蟻群算法則沒有這些缺點。由于螞蟻等群居類昆蟲具有分布式、自組織、信息素(pheromone)通信、合作等性能，模擬其智能行為的蟻群算法能夠解決許多復雜的問題， 聚類蟻群算法分類 螞蟻行為 相應的算法 螞蟻覓食 螞蟻聚類算法 螞蟻自我聚集 AntTree算法 螞蟻堆積尸體 AntClass算法 螞蟻構建巢穴 AntClust算法 因此對它的研究逐漸受到越來越多的學者的關注，并提出許多聚類蟻群算法。因為傳統(tǒng)聚類方法在高維數(shù)據(jù)集中進行聚類時，主要遇到兩個問題。 聚類算法的比較算法類型 空間時間備注單連接層次O(n2)O(kn2)非增量的平均連接層次O(n2)O(kn2)非增量的全連接層次O(n2)O(kn2)非增量的K均值劃分O(n)O(nkt)迭代的。但不適合發(fā)現(xiàn)非凹面狀的簇。劃分聚類法 (partitioning clustering methods)劃分聚類法，又成為動態(tài)聚類法，逐步聚類法，其實基本思想，是在一個平面層次上對所有的樣本點先做出某種較為粗略的劃分，然后按照某種最優(yōu)的準咋進行修正，通過算法的迭代執(zhí)行，,其中最為典型的K均值算法(Kmeans)。單元分裂方法在每一步選出一個變量對整個類進行細分，”擁有”這個值的歸為一類，”沒有”為另一類。由于每一步對一個k元素的簇,需要考慮2k1種分化情況,所有運算量非常大，而顯得不使用。全連接和平均里阿杰同樣無法還原類結構，且傾向于產生球形的類。這個方法傾向與合并差異小的兩個簇.(距離)介于單連接和全連接之間。單連接也可以用于分裂式聚類，用來分開最近距離最遠的兩組。這個方法使用數(shù)據(jù)的相似度矩陣或距離矩陣，定義簇間距離之間數(shù)據(jù)的最小距離。（1）凝聚算法凝聚算法:在初始時，每一個成員都組成一個單獨的簇,組以后的迭代過程中，再把那些相互臨近的簇合并成一個簇，直到所有成員組成一個簇為止。典型方法有k均值等方法。 目前，聚類的方法算法很多，但大體上可以分為兩類即分層聚類和劃分聚類。交叉算子的加入提高了螞蟻在一次搜索中搜索到更好的路徑的能力，同時也增加了解的多樣性。 （） （）式中：來表示信息素物質的持久性；1－ρ表示信息素物質的消逝程度；為局部的最優(yōu)螞蟻的路徑長度；為全局最優(yōu)螞蟻的路徑長度；、為整型變量，分別代表用局部最優(yōu)螞蟻和全局最優(yōu)螞蟻更新信息素的權重，其和為一常數(shù)。在螞蟻搜索路徑點的過程中，有可能進入這樣的柵格它到與之相鄰的柵格點的信息素值均為零，此時可加一個回饋信息，使螞蟻回到上一次搜索的路徑點，并將此柵格置為威脅柵格。設表示柵格i到終點G的距離。規(guī)劃任務為搜索一條由S點到G點的最優(yōu)路徑，其目標函數(shù)可由式（）表示， （）式中：、為路徑點的坐標信息，為路徑點的個數(shù)。4)對蟻群搜索到的路徑進行交叉運算，記錄全局最優(yōu)螞蟻的路徑信息。在自然界中螞蟻的這種尋徑過程表現(xiàn)為正反饋的過程，與人工蟻群的尋優(yōu)過程非常一致。，A為出發(fā)點（即蟻穴），B為食物源，從圖上可見螞蟻要獲得食物有兩條路可走，我們可以很容易的比較出路徑ACB較路徑ADB長，然而螞蟻是不知道這一點的。并通過大量實驗從各方面進行研究，實驗表明PACOA算法不僅是有效的，而且其性能優(yōu)于之前的聚類蟻群算法。 在某群體中若存在眾多無智能的個體，它們通過相互之間的簡單合作所表現(xiàn)出來的智能行為即稱為集群智能（Swarm Intelligence）。 在網(wǎng)絡路由處理中，網(wǎng)絡的流量分布不斷變化，網(wǎng)絡鏈路或結點也會隨機地失效或重新加入。而新加入的這個行列的蟻群算法正在開始嶄入頭角，為復雜困難的系統(tǒng)優(yōu)化問題提供了新的具有競爭力的求解算法，這種由歐洲學者提出并加以改進的新穎系統(tǒng)優(yōu)化思想，正在吸引著越來越多的學者的關注和研究。特別是，計算機科學與技術的迅速發(fā)展，從根本上改變了人類的生產與生活。4）蟻群算法具有較強的魯棒性。3） 蟻群算法是一種正反饋的算法。當算法開始的初期，單個的人工螞蟻無序的尋找解，算法經(jīng)過一段時間的演化，人工螞蟻間通過信息激素的作用，自發(fā)的越來越趨向于尋找到接近最優(yōu)解的一些解，這就是一個無序到有序的過程。蟻群算法與其他搜索算法相結合，來改進蟻群算法是一條重要途徑。生物界中的螞蟻有能力在沒有任何可見提示下找出從蟻穴到食物源的最短路徑，并且能夠隨環(huán)境的變化而變化去搜索新路徑，產生新選擇，其機理在于螞蟻在其走過的路徑上釋放一種信息素，信息素承載著路況信息，螞蟻在行進過程中能夠感知這種信息素的存在和其強度，并指導自己的行進方向，使螞蟻傾向于向信息素強度高的方向爬行。從1998年他與其它學者開始組織兩年一次的關于蟻群算法和群體智能的國際會議。 無信息素的螞蟻路徑此時對于從蟻巢出發(fā)來到C點的螞蟻來說，由于A側的信息素濃度高，B側的信息素較低，就傾向于選擇A側的路徑。比如經(jīng)典的“二元橋實驗”中，經(jīng)過一定時間，從食物源返回的螞蟻到達D點同樣也碰到障礙物，也需要進行選擇。蟻群系統(tǒng)的特點是：（1）群體中相互作用的個體是分布式的，這樣更適應當前的分布式環(huán)境下的工作狀態(tài)；（2）蟻群中沒有集中控制，而是無人監(jiān)督的學習，這樣使之更具有魯棒性，不會因為某一個或某幾個個體出現(xiàn)故障而影響整個問題的求解；（3）可以不通過個體直接通信而是通過非直接通信進行合作，系統(tǒng)具有更好的擴充性；（4）系統(tǒng)中的每個個體的能力十分簡單，每個個體執(zhí)行的時間比較短，并且實現(xiàn)也比較簡單，具有簡單性。在商業(yè)上，聚類可以幫助市場分析人員從消費者數(shù)據(jù)庫中區(qū)分出不同的消費群體來，并且概括出每一類消費者的消費模式或者說習慣。數(shù)據(jù)挖掘是一種決策支持過程，它主要基于人工智能、機器學習、模式識別、統(tǒng)計學、數(shù)據(jù)庫、可視化技術等，高度自動化地分析企業(yè)的數(shù)據(jù)，做出歸納性的推理，從中挖掘出潛在的模式，幫助決策者調整市場策略，減少風險，做出正確的決策。另外，由于缺少有效的信息提取方法，使人們淹沒在數(shù)據(jù)的海洋中卻又感到信息的貧乏。本文提出了并行性和聚類蟻群相結合的方法，給出了一種并行蟻群算法，該算法使用并行搜索，并且采用根據(jù)目標函數(shù)值自動調整螞蟻搜索路徑和基于目標函數(shù)值的啟發(fā)式信息素分配策略。近幾十年來，國內外的學術者提出了諸多的聚類算法，力圖尋找最優(yōu)方案。聚類分析又稱群分析，它是研究樣品或指標分類問題的一種統(tǒng)計分析方法，它是由若干模式組成的，以相似性為基礎，在一個聚類中的模式之間比不在同一聚類中的模式之間具有更多的相似性，是重要的數(shù)據(jù)挖掘技術。而通過研究發(fā)現(xiàn)人工蟻群算法本質上是一個并行系統(tǒng)，因此，研究并行蟻群算法對于提高運算速度具有重要的意義，在歸納總結的基礎上，本文了將并行算法和聚類蟻群算法相結合，提出了一種新的聚類蟻群優(yōu)化算法，同時將改良后的優(yōu)化算法針對傳統(tǒng)的TSP問題、二次分配問題進行了對比，實驗結果表明該算法不僅是有效的，而且其性能更加的優(yōu)越。 Clustering；Ant Colony Optimization目 錄摘 要 6Abstract 7緒論： 10 研究背景 10 蟻群基本習性與覓食行為策略 10 聚類蟻群算法的思想與特點 13 蟻群優(yōu)化算法的意義及應用 14 本文主要研究的內容及論文組織 152 聚類蟻群算法 16 16 聚類算法 20 主要聚類蟻群算法 23 K均值混合聚類算法 23 基于螞蟻覓食原理的聚類算法 24 基于化學識別系統(tǒng)的聚類蟻群算法 26 小結 273 并行算法概述 29 并行計算機 29 并行算法 29 MPI與OPENMP并行編程 304 并行的聚類蟻群優(yōu)化算法PACOA 32 PACOA算法的基本思想產生的背景 32 PACOA基本思想與策略 32 PACOA算法步驟和基本實現(xiàn) 355 PACOA性能的仿真研究 42 實驗介紹 42 仿真實驗結果與數(shù)據(jù)分析 42 小結與參數(shù)分析 456 結論與展望 47參考文獻 49緒論： 研究背景隨著因特網(wǎng)技術的發(fā)展，特別是人類生產和采集數(shù)據(jù)能力的增長，人們能以更加快速、容易、廉價的方式獲取和存儲數(shù)據(jù)，這就使得數(shù)據(jù)和信息量呈指數(shù)形式增長。數(shù)據(jù)挖掘（Data Mining，DM）又稱數(shù)據(jù)庫中的知識發(fā)現(xiàn)（Knowledge Discover in Database，KDD），是目前人工智能和數(shù)據(jù)庫領域研究的熱點問題，所謂數(shù)據(jù)挖掘是指從數(shù)據(jù)庫的大量數(shù)據(jù)中揭示出隱含的、先前未知的并有潛在價值的信息的非平凡過程。對聚類的研究始于60年代，而聚類的用途是很廣泛的。 蟻群基本習性與覓食行為策略螞蟻是一種最古老的社會性昆蟲，它的起源可以追溯到1億年前，大約與恐龍同一時代，螞蟻的個體結構和行為很簡單，單個工蟻能做的各種動作不超過50個，其中大部分都是傳遞信息，但由這些簡單的個體所構成的整個群體蟻群，卻表現(xiàn)出高度結構的社會組織，在很