【正文】 碩士學位論文基于并行處理的聚類蟻群算法的研究Based on parallel processing of the ant clustering algorithm of flocking 摘 要聚類就是將數據對象劃分到不同組（或簇）中，使得屬于同簇內的數據對象具有相似性，而不同簇的數據對象具有相異性。聚類分析又稱群分析，它是研究樣品或指標分類問題的一種統計分析方法，它是由若干模式組成的，以相似性為基礎，在一個聚類中的模式之間比不在同一聚類中的模式之間具有更多的相似性，是重要的數據挖掘技術。近幾十年來，國內外的學術者提出了諸多的聚類算法，力圖尋找最優(yōu)方案。隨著蟻群算法研究的興起，人們發(fā)現采用蟻群模型進行聚類能夠更加有力的解決現實問題。 本文主要先研究了業(yè)界一些蟻群算法和聚類算法，充分深入了解了有關聚類蟻群算法的基本原理和特性。而通過研究發(fā)現人工蟻群算法本質上是一個并行系統，因此，研究并行蟻群算法對于提高運算速度具有重要的意義，在歸納總結的基礎上，本文了將并行算法和聚類蟻群算法相結合，提出了一種新的聚類蟻群優(yōu)化算法，同時將改良后的優(yōu)化算法針對傳統的TSP問題、二次分配問題進行了對比，實驗結果表明該算法不僅是有效的，而且其性能更加的優(yōu)越。本文提出了并行性和聚類蟻群相結合的方法，給出了一種并行蟻群算法，該算法使用并行搜索，并且采用根據目標函數值自動調整螞蟻搜索路徑和基于目標函數值的啟發(fā)式信息素分配策略。為人們研究聚類提供了新思路和新途徑，因此本文的研究具有一定的理論和實踐意義。關鍵詞：并行性；聚類蟻群；優(yōu)化Abstract Clustering is dividing data object into different groups (or cluster), make belong to same cluster the data objects with the similarity. However different data objects in clusters have different attribute. Clustering analysis, also called study of analysis, it studies a statistical analysis method of sample or index classification problem. It is posed by several mode based on similarity, and in mode of cluster has more similarity than that in the different clusters between. It is an important data mining technology. In recent decades, the domestic and international academic proposed many clustering algorithms, and tries to find the optimal scheme. With the rise of ant colony algorithm, people found using ant colony optimization model clustering can solve practical problem more powerfullyFirstly this paper studied some ant colony algorithm and clustering algorithm, fully understanding the basic principle of flocking and characteristics of ant clustering algorithm. And through the researches show that people ants swarm algorithm is essentially a parallel system, therefore, Studying the parallel ant colony algorithm has an important meaning to improve speed. On the basis of summarization, bining industrial scheduling problem, this paper will bine the parallel algorithm and ant clustering algorithm, and proposes a new ant algorithm. What is more, the kind of optimization will improved algorithm for traditional TSP problem, quadratic assignment problem and industrial scheduling problem of parison, the experimental results show that the algorithm is not only effective but also with its more superior performance.This paper puts forward such parallelism and ant cluster method bining, and presents a parallel ant colony algorithm, which use parallel search, and based on the objective function values automatically adjust the ant search path and based on the objective function value heuristic pheromone distribution strategy. It provides some new ideas and new ways for people to study clustering, thus this study has certain theoretical and practical significance.Key words: Parallelization。 Clustering；Ant Colony Optimization目 錄摘 要 6Abstract 7緒論： 10 研究背景 10 蟻群基本習性與覓食行為策略 10 聚類蟻群算法的思想與特點 13 蟻群優(yōu)化算法的意義及應用 14 本文主要研究的內容及論文組織 152 聚類蟻群算法 16 16 聚類算法 20 主要聚類蟻群算法 23 K均值混合聚類算法 23 基于螞蟻覓食原理的聚類算法 24 基于化學識別系統的聚類蟻群算法 26 小結 273 并行算法概述 29 并行計算機 29 并行算法 29 MPI與OPENMP并行編程 304 并行的聚類蟻群優(yōu)化算法PACOA 32 PACOA算法的基本思想產生的背景 32 PACOA基本思想與策略 32 PACOA算法步驟和基本實現 355 PACOA性能的仿真研究 42 實驗介紹 42 仿真實驗結果與數據分析 42 小結與參數分析 456 結論與展望 47參考文獻 49緒論： 研究背景隨著因特網技術的發(fā)展，特別是人類生產和采集數據能力的增長，人們能以更加快速、容易、廉價的方式獲取和存儲數據，這就使得數據和信息量呈指數形式增長。另外，由于缺少有效的信息提取方法，使人們淹沒在數據的海洋中卻又感到信息的貧乏。這種現象使人們產生對自動地從大量數據庫中尋找有用的信息和知識的迫切需求。在這種現實需求的驅動下，數據挖掘便應運而生了。數據挖掘（Data Mining，DM）又稱數據庫中的知識發(fā)現（Knowledge Discover in Database，KDD），是目前人工智能和數據庫領域研究的熱點問題，所謂數據挖掘是指從數據庫的大量數據中揭示出隱含的、先前未知的并有潛在價值的信息的非平凡過程。數據挖掘是一種決策支持過程，它主要基于人工智能、機器學習、模式識別、統計學、數據庫、可視化技術等，高度自動化地分析企業(yè)的數據，做出歸納性的推理，從中挖掘出潛在的模式，幫助決策者調整市場策略，減少風險，做出正確的決策。聚類則是數據挖掘領域中的一個重要分支，是人們認識和探索事物之間內在聯系的有效手段，它不僅可以作為獨立的數據挖掘工具來發(fā)現數據庫中數據分布的一些深入信息，而且可以作為其它數據挖掘算法的預處理步驟。所謂聚類就是將數據對象分組成為多個類或簇，使得在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。對聚類的研究始于60年代，而聚類的用途是很廣泛的。在商業(yè)上，聚類可以幫助市場分析人員從消費者數據庫中區(qū)分出不同的消費群體來，并且概括出每一類消費者的消費模式或者說習慣。聚類分析的算法可以分為劃分法（Partitioning Methods）、層次法（Hierarchical Methods）、基于密度的方法（densitybased methods）、基于網格的方法（gridbased methods）、基于模型的方法（ModelBased Methods）。近年來隨著數據挖掘研究的深入，涌現出大量新的聚類算法，但是對大型數據庫的有效的聚類分析方法仍然是一個具有挑戰(zhàn)性的研究問題。 蟻群基本習性與覓食行為策略螞蟻是一種最古老的社會性昆蟲，它的起源可以追溯到1億年前，大約與恐龍同一時代，螞蟻的個體結構和行為很簡單，單個工蟻能做的各種動作不超過50個，其中大部分都是傳遞信息，但由這些簡單的個體所構成的整個群體蟻群，卻表現出高度結構的社會組織，在很多情況下能夠完成遠遠超出螞蟻個體能力的復雜任務，作為社會昆蟲的一種，螞蟻社會成員除有組織有分工以外，還有相互的通訊和信息傳遞，蟻群有著獨特的信息系統，其中包括視覺信號，聲音通訊信號和更為獨特的信息素。蟻群系統的特點是：（1）群體中相互作用的個體是分布式的，這樣更適應當前的分布式環(huán)境下的工作狀態(tài)；（2）蟻群中沒有集中控制，而是無人監(jiān)督的學習，這樣使之更具有魯棒性，不會因為某一個或某幾個個體出現故障而影響整個問題的求解；（3）可以不通過個體直接通信而是通過非直接通信進行合作，系統具有更好的擴充性；（4）系統中的每個個體的能力十分簡單，每個個體執(zhí)行的時間比較短，并且實現也比較簡單，具有簡單性。覓食行為是蟻群一個重要而有趣的行為，據昆蟲學家的觀察和研究發(fā)現，生物世界中的螞蟻有能力在沒有任何可見提示下找出從蟻穴到食物源的最短路徑，并且能夠隨環(huán)境的變化而變化地搜索新的路徑，產生新的選擇。螞蟻能在其走過的路徑上分泌一種化學物質Pheromone__信息素，螞蟻在運動過程中能夠感知這種物質的存在及其強度，并以此指導自己的運動方向，使螞蟻傾向于朝著該物質強度高的方向移動。信息素軌跡可以使螞蟻找到它們返回食物源的路徑，其他螞蟻也可以利用該軌跡找到由同伴發(fā)現的食物源的位置。比如經典的“二元橋實驗”中，經過一定時間，從食物源返回的螞蟻到達D點同樣也碰到障礙物，也需要進行選擇。此時A, B兩側的信息素濃度相同，它們仍然一半向左，一半向右。但是當A側的螞蟻已經完全繞過障礙物到達C點時，B側的螞蟻由于需走的路徑更長，還不能到達C點。如圖1所示。 無信息素的螞蟻路徑此時對于從蟻巢出發(fā)來到C點的螞蟻來說，由于A側的信息素濃度高，B側的信息素較低，就傾向于選擇A側的路徑。這樣的結果是A側的螞蟻越來越多，最終所有螞蟻都選擇這條較短的路徑。如圖2所示。 有信息素的螞蟻路徑根據螞蟻的“尋找食物”的群體行為，在法國巴黎召開的第一屆歐洲人工生命會議上最早的提出了蟻群算法的基本模型。從1998年他與其它學者開始組織兩年一次的關于蟻群算法和群體智能的國際會議。1999年進化計算大會召開了蟻群算法專題會議。期刊《下一代計算系統》在2000年為蟻群算法作了一次專輯。 聚類蟻群算法的思想與特點蟻群算法是受生物界中螞蟻覓食行為啟發(fā)而來。生物界中的螞蟻有能力在沒有任何可見提示下找出從蟻穴到食物源的最短路徑，并且能夠隨環(huán)境的變化而變化去搜索新路徑，產生新選擇，其機理在于螞蟻在其走過的路徑上釋放一種信息素，信息素承載著路況信息，螞蟻在行進過程中能夠感知這種信息素的存在和其強度，并指導自己的行進方向，使螞蟻傾向于向信息素強度高的方向爬行。這無疑非常適合動態(tài)航跡規(guī)劃問題。蟻群算法最重要的特點就是創(chuàng)造性地使用了啟發(fā)信息，即通過引入信息素播撒機制，將之前搜索到的最優(yōu)解用于指導后續(xù)的搜索。在蟻群算法的眾多改進算法中，對信息素播撒機制的改進是研究者最為關注的一點。蟻群算法與其他搜索算法相結合，來改進蟻群算法是一條重要途徑。它有如下的幾個特點：1）蟻群算法是一種自組織的算法。在系統論中，自組織和它組織是組織的兩個基本分類，其區(qū)別在于組織力或組織指令是來自于系統的內部還是來自于系統的外部，來自于系統內部的是自組織，來自于系統外部的是它組織。蟻群算法充分體現了這個過程，以螞蟻群體優(yōu)化為例子說明。當算法開始的初期，單個的人工螞蟻無序的尋找解，算法經過一段時間的演化，人工螞蟻間通過信息激素的作用，自發(fā)的越來越趨向于尋找到接近最優(yōu)解的一些解，這就是一個無序到有序的過程。2）蟻群算法是一種本質上并行的算法。每只螞蟻搜索的過程彼此獨立，僅通過信息激素進行通信。所以蟻群算法則可以看作是一個分布式的多agent系統，它在問題空間的多點同時開始進行獨立的解搜索，不僅增加了算法的可靠性，也使得算法具有較強的全局