【作者】 姜浩；

【导师】 崔荣一；

【作者基本信息】 延边大学 ， 计算机应用技术， 2009， 硕士

【摘要】 粒子群算法(Particle Swarm Optimization,PSO)源于鸟群捕食行为的研究,是一种新的群体智能优化算法,作为群智能算法的重要分支,在演化计算领域发挥着举足轻重的作用。PSO算法一经提出,因其自身的优良特性,引起学者们的极大的关注,目前已在组合优化、神经网络、机器人路径规划等领域获得了广泛应用。粒子群算法发展至今,虽取得大量研究成果,但它自身的缺陷仍值得继续研究。近十几年来,人们利用信息技术生产和搜集数据的能力大幅度提高,很多领域都积累了大量的数据。为了从数据中发现有价值的知识和规律,人们结合数据库、统计学及机器学习等技术,提出数据挖掘来解决这一难题。聚类分析技术是数据挖掘中的重要内容和挖掘方法,是各学科研究的重要工具。本论文针对PSO算法多样性缺失的缺陷,提出改进策略。由于聚类分析中的数据分类可以看作是一种分组的策略,原始PSO算法不适应求解此类问题,因此提出另一种改进策略,来使粒子群算法适应聚类分析的要求。并通过对图像分割的实验,验证算法的应用价值。本文的工作内容如下:(1)提出了动态种群规模的PSO算法。随机选取一些粒子,利用遗传算子按照一定的概率生成新个体,以新个体来改善种群的多样性。由于遗传算子每次迭代都可能生成一定规模的新个体,所以种群规模始终上升。为控制种群规模,引入疾病算子。当种群规模超过预先设置好的阈值时,将种群规模降为初始状态。(2)为求解聚类问题,将PSO算法修改为离散化PSO。首先,将粒子编码为样本的分类情况,粒子维数为样本个数,粒子的每一维代表当前样本的所属的类号;然后,定义粒子之间的距离;最后,修改更新公式,使粒子的每一维类号能够朝向最优解进化。(3)将新算法用来进行图形分割的实验,以此来验证算法的应用价值和算法的有效性。实验结果证明,动态种群规模可以很好的改善种群的多样性,为算法搜索全局最优解提供帮助。基于这动态种群粒子群算法的聚类分析方法不仅可以得到很好的数据集聚类结果,而且将聚类分析问题分割为聚类方法和聚类评价,使算法具有一定的通用性。同时算法在图像分割上得到了良好的结果,有一定的应用价值。更多还原

【Abstract】 Originated from the research of birds’ predatory behavior, particle swarm optimization (PSO) algorithm is a new swarm intelligent algorithm. As an part of swarm intelligent algorithms, PSO plays an important role in the field of evolutionary computation. Due to the excellent characteristics of the algorithm, PSO has attracted wide attentions of scholars. So that it has been extensively applied in many fields such as combinatorial optimization, neural network and robot path planning etc. Although the research of PSO has gained great achievements, it is still worth to be further investigated because of its defaults.In the past decade, the ability of human being to produce and search data with information technique has been greatly improved. Therefore, huge amount of data was accumulated in many fields. To find valuable knowledge and regularity from data, data base, statistics and machine learning are combined to generate data mining technique for solving the question. Cluster analysis is an important tool in subject research, whose contents and methods belong to data mining field.In accordance with the loss variety of PSO, an improved algorithm is proposed in this dissertation. In cluster analysis, data classification is taken as a grouping strategy. While traditional PSO does not fit for solving this kind of problem, the algorithm is improved to meet the demand of cluster analysis. Furthermore, the validity of the algorithm is tested by an image segmentation experiment. The main works are listed as follows:Firstly, a new PSO based on dynamic population size is presented. The first step in the algorithm is to randomly choose some particles to generate new individuals by genetic operators. And then, new individuals are used to improve the variety of population. Because new amount of individuals are generated after every iteration, the population size keeps increasing. To control population size, disease operator is introduced. While the population size exceed presetting threshold, the population size decrease to original state.Then, to solve discrete optimization problem, PSO algorithm is modified to discrete one. At first, particle was encoded to sample’s classification, take dimensions of particle as numbers of sample and every dimension as class number of current sample. After defining the distance between particles, iterative formula is updated to impel every class number to evolve the direction of optimal solution.Finally, the new algorithm is used to image segmentation to test its validity. Meanwhile characters of the algorithm are also summarized.The experimental results show that the population variety can be improved by dynamic population size which does good to searching optimal solution. Based on the dynamic population size PSO, the cluster analysis algorithm can better classify dataset properly. Further more, dividing cluster analysis into cluster and evaluation makes the algorithm generality. Meanwhile, the algorithm is of some application value which is proved by good results of image segmentation.更多还原