基于PAM和均匀设计的并行粒子群优化算法

摘要

聚类技术是数据挖掘中的一个重要方法，PAM（Partitioning Around Medoids）是基于分区的聚类算法的一种，它试图将n个数据对象分成k个部分。在并行粒子群PSO（Particle Swarm Optimization）算法中，需要划分整个种群为几个相互不重叠的子种群。因此，引入PAM来划分整个种群。通过聚类，相同子种群的粒子相对集中，从而能够较容易地相互学习。这使得有限的时间能够花费在最有效的搜索上，以便提高算法的搜索效率。为了均匀地探测整个解空间，引入均匀设计来产生初始种群，使种群成员均匀地分散在可行解空间中。进化过程中，均匀设计也被引入来替换种群中的较差个体。提出基于PAM和均匀设计的并行粒子群算法，它结合并充分利用了二者的优点。对几个测试问题的实验结果证明，提出的算法比传统的并行粒子群算法具有更高的性能和更好的收敛准确性。%Clustering technique is an important method in data mining. PAM(Partitioning Around Medoids)is one of clustering algorithms based on partitioning methods. It attempts to divide n data objects into k partitions. In the parallel PSO(Particle Swarm Optimization)algorithms, it needs to divide the swarm into several sub-swarms non-overlapping with each other. Therefore, PAM is introduced to divide the swarm. Clustering makes sure particles within the same sub-swarm are relatively concentrative, so that they can be easier to learn each other. This makes the limited time be spent on the most effectively searching, so as to improve the searching efficiency of an algorithm. In order to evenly explore the whole solution spaces, uniform design is introduced to generate an initial population. This is to ensure that the population members are scattered uniformly over the feasible solution space. In evolution, uniform design is also introduced to replace some worse individuals. This paper presents a parallel PSO algorithm employing PAM and uniform design. It combines and takes full advantage of the merits of the two. The experimental results performed on several test problems demonstrate that the proposed algorithm has higher performance and convergence accuracy than traditional parallel PSO.