【作者】 张新建；

【导师】 贾瑞玉；

【作者基本信息】 安徽大学 ， 计算机软件与理论， 2010， 硕士

【摘要】 蚁群算法是通过对自然界中真实蚂蚁的集体行为的观察、模拟而得到一种仿生优化算法,它具有很好的并行性、分布性。根据蚂蚁群体不同的集体行为特征,蚁群算法可分为受蚂蚁觅食行为启发的模型和受孵化分类启发的模型、受劳动分工和协作运输启发的模型。本文重点研究了前两种蚁群算法模型。受蚂蚁觅食行为启发的模型又称为蚁群优化算法(ACO),是继模拟退火算法、遗传算法、禁忌搜索等之后又一启发式智能优化算法。目前它已成功应用于求解TSP问题、地图着色、路径车辆调度等优化问题。本文针对蚁群算法收敛时间长、易陷入局部最优的缺点,通过对路径上信息素的更新方式作出动态调整、建立信息素平滑机制,进而使得不同路径上的信息素的更新速度有所不同,从而使改进后算法能够有效地缩短搜索的时间,并能对最终解进行优化,避免过早的陷入局部最优。聚类是数据挖掘的重要技术之一,它可按照某种规则将数据对象划分为多个类或簇,使同一类的数据对象有较高的相似度,而不同类的数据对象差异较大。受蚂蚁的觅食过程启发的聚类算法又被称为基于蚂蚁觅食原理的聚类算法。把蚂蚁觅食行为分为搜索食物和搬运食物两个环节,同时把数据对象视为蚂蚁,把聚类中心视为“食物源”,这样数据对象的聚类过程就可以转化为蚂蚁觅食的过程,在信息素的引导下蚂蚁就可以完成数据对象的聚类。但在该算法中没有区分数据对象不同属性的重要性,本文通过采用离差最大化方法,对每个属性根据它的重要性为它赋予一个权值,从而改进了原算法中的距离计算,使得相似的数据对象能快速的聚集到一起,从而避免了大量无效的相似度计算,提高了算法的效率。受孵化分类启发的模型又称为蚂蚁堆形成原理聚类算法。很多种类的蚂蚁都能够将卵和小幼虫紧密地排列成束并放置在巢穴孵化区的中心,而最大的幼虫位于孵化束的外围。Deneubourg等人根据这一现象最先提出了一个基本模型(BM)来模拟该现象,对基本模型比较成功的改进有LF算法。模糊聚类算法思想来源于Ruspini于1969年提出的模糊划分思想,是指在涉及事物之间的模糊界限时按一定要求对事物进行分类的数学方法,本文所介绍的FCM是其中的一种。本文通过分析LF算法和FCM算法的优缺点,以及它们的互补性,提出了基于LF算法的改进FCM算法,即将这两个算法进行融合,同时也采用了离差最大化赋权方法,对算法中的距离计算进行改进,进一步提高了算法的性能。更多还原

【Abstract】 Ant colony algorithm which is inspired by the behavior of ant colony is parallelism, distributed. According to the behavior characteristics of ant colony in different aspects, ant algorithm can be classified as model inspired by ant looking for food behavior and model inspired by brood sorting, model inspired by division of laborj, model inspired by cooperative transport. This dissertation focuses on the two models mentioned above.Model inspired by ant looking for food behavior is also called ants colony optimization (ACO), which is a new kind of evolution computation algorithms based on bionics, and is a new heuristic intelligent optimization algorithm after simulated annealing, genetic algorithm and tabu search. After the algorithm being proposed, ACO has applied into TSP, quadratic assignment, graph coloring, vehicle route successfully. Aiming at solving disadvantages of ACO, this dissertation proposed an ant colony algorithm with dynamic update pheromone. Improved algorithm can shorten searching time, optimize solution finally and avoid the premature fall into local optimum.Clustering is an important technique in data mining, it is a rule in accordance with the data objects into multiple categories or clusters to make the same kind of data objects have a higher degree of similarity, but not quite different kind of data object.Clustering algorithm inspired by ants looking for food behavior is also known as clustering algorithm based on the theory of ants looking for food behavior. In the abstract of the ants in nature looking for food behavior, the behavior of looking for food is divided into two areas of searching food and transporting food, while the data object as ants, the cluster center as a "food source". So the clustering process can be described as ant foraging process. The clustering algorithm does not distinguish between the different attributes of the importance of data objects, this dissertation uses the maximum deviation algorithm, for each attribute according to its importance as it gives a weight. These make similar objects fast clustering, and avoid a lot of useless computation, which improves the efficiency of algorithm. Model inspired by brood sorting can also be called ant clustering model. Many kinds of ants can closely arrange eggs and larvae in a sheaf around the middle of nest area, and the biggest larvae located at the edge of area. Deneubourg and his colleagues were the first to propose the basic model (BM) to simulate this phenomenon. LF algorithm is a successfully improved BM. Fuzzy clustering algorithm is inspired by the theory of Fuzzy partition which is proposed by Ruspini in 1969. The FCM algorithm which is used in the dissertation is one of Fuzzy clustering algorithm. The dissertation analyzes the advantages and disadvantages of the LF algorithm and FCM algorithm, and their complementary analysis, LF algorithm is proposed based on improved FCM algorithm, the forthcoming integration of these two algorithms, but also used to maximize the weighted deviation algorithm, the algorithm in the distance calculation be improved to further enhance the performance of the algorithm.更多还原