1学 位 论文基于并行处理的聚类蚁群算法的研究基于并行处理的聚类蚁群算法的研究Based on parallel processing of the ant clustering algorithm of flocking 2摘 要聚类就是将数据对象划分到不同组（或簇）中，使得属于同簇内的数据对象具有相似性，而不同簇的数据对象具有相异性。 聚类分析又称群分析，它是研究样品或指标分类问题的一种统计分析方法 ，它是由若干模式组成的，以相似性为基础，在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性 ，是重要的数据挖掘技术。近几十年来，国内外的学术者提出了诸多的聚类算法，力图寻找最优方案。随着蚁群算法研究的兴起，人们发现采用蚁群模型进行聚类能够更加有力的解决现实问题。本文主要先研究了业界一些蚁群算法和聚类算法，充分深入了解了有关聚类蚁群算法的基本原理和特性。而通过研究发现人工蚁群算法本质上是一个并行系统，因此，研究并行蚁群算法对于提高运算速度具有重要的意义，在归纳总结的基础上，本文了将并行算法和聚类蚁群算法相结合，提出了一种新的聚类蚁群优化算法，同时将改良后的优化算法针对传统的TSP 问题、二次分配问题进行了对比，实验结果表明该算法不仅是有效的，而且其性能更加的优越。本文提出了并行性和聚类蚁群相结合的方法，给出了一种并行蚁群算法，该算法使用并行搜索，并且采用根据目标函数值自动调整蚂蚁搜索路径和基于目标函数值的启发式信息素分配策略。为人们研究聚类提供了新思路和新途径，因此本文的研究具有一定的理论和实践意义。关键词：并行性；聚类蚁群；优化关键词：并行性；聚类蚁群；优化3Abstract 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 composed 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, combining industrial scheduling problem, this paper will combine 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 comparison, 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 combining, 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 Optimization4目目 录录摘 要 .6Abstract.7绪论： .101.1 研究背景 .101.2 蚁群基本习性与觅食行为策略.101.3 聚类蚁群算法的思想与特点 .131.4 蚁群优化算法的意义及应用 .141.5 本文主要研究的内容及论文组织 .152 聚类蚁群算法 .162.1 基本蚁群算法的模型特征 .162.2 聚类算法 .202.3 主要聚类蚁群算法 .232.3.1 K 均值混合聚类算法 .232.3.2 基于蚂蚁觅食原理的聚类算法.242.3.3 基于化学识别系统的聚类蚁群算法.262.4 小结 .273 并行算法概述 .293.1 并行计算机 .293.2 并行算法 .293.3 MPI 与 OPENMP 并行编程 .304 并行的聚类蚁群优化算法 PACOA.324.1 PACOA 算法的基本思想产生的背景 .324.2 PACOA 基本思想与策略 .