《粒子群算法的拓扑结构分析与研究》由会员分享，可在线阅读，更多相关《粒子群算法的拓扑结构分析与研究（58页珍藏版）》请在金锄头文库上搜索。
1、太原理工大学 硕士学位论文 粒子群算法的拓扑结构分析与研究 姓名：杨朋樽 申请学位级别：硕士 专业： 指导教师：田玉玲 20100401 太原理工大学硕士研究生学位论文 I 粒子群算法的拓扑结构分析与研究 摘 要 作为一种新的群体智能方法，粒子群算法是一个非常有前景的工具， 在处理高维函数以及工程设计领域的问题时尤其有用。该算法的灵感来源 于社会心理学和人工生命，致力于模拟个体间的社会交互，具有收敛速度 快、通用性强等优势，自1995年被提出之后得到了数值优化领域的广泛关 注。 如何加快粒子群算法的收敛速度和避免出现早熟收敛，一直是大多数 研究者关注的重点。克服早熟收敛的措施主要是设法保持种群
2、的多样性， 或引入跳出局部最优点的机制。在加快收敛速度方面，主要的工作集中在 如何选择最优算法方面。但这些研究者多数属于纯科学计算或工程应用领 域，他们只专注于结果而不探究原因，很少有人深入考虑粒子群算法的社 会心理学渊源。 本文在研究过程中，注重算法的理论分析和实验验证相结合。针对标 准的粒子群优化算法在种群中传播速度过快，易陷入局部最优解的缺陷， 本文提出基于KRTG的动态拓扑结构的粒子群算法，该算法从粒子间的邻域 结构出发，动态地调整种群的拓扑结构，增加种群的多样性，使算法收敛 于全局最优解。 文章对粒子群算法作了较为深入的研究，着重从粒子间的拓扑结构对 粒子群算法的影响作了详尽的分析与
3、总结，试图在已有粒子群的拓扑结构 的基础上做出一些突破或改进。相关文献已经证明粒子群的拓扑结构对其 算法的性能有很大影响。 本文的核心工作是研究了一种基于KRTG的动态拓扑结构的粒子群算 法，并采用K均值聚类算法对其加以优化改进。文中首先介绍了一些关于粒 太原理工大学硕士研究生学位论文 II 子群优化算法理论的基本知识，并对粒子群理论的研究工作进行了总结； 其次， 本文在现有粒子群算法的基础上提出了一种基于KRTG的动态拓扑策 略，详尽给出了算法中拓扑结构的个体自适应策略、全局更新策略以及邻 域搜索策略等过程，并采用应用离散时间的系统方程收敛定理，进行分析 论证本文算法的理论优势及其收敛性；最
4、后，通过求解各种多维函数的最 优解，以及本文的粒子群算法、免疫粒子群算法IPSO与基于最小世界理论 的WPSO算法进行比较实验，通过实验证明了该算法的可行性和有效性。 关键词: 粒子群算法，拓扑结构，KRTG，适应度 太原理工大学硕士研究生学位论文 III ANALYSIS AND RESEARCH ON THE TOPOLOGICAL STRUCTURE OF PARTICLE SWARM ALGORITHM ABSTRACT As a newly developed swarm intelligence paradigm, particle swarm algorithm is a ver
5、y promising optimization tool, with many advantages in high-dimensional problems or engineering design field. The main idea of this algorithm originated from Social Psychology and Artificial Life as a simuluation of socion-cognitive process. Because of its high convergence rate and excellent general
6、ization, particle swarm algorithm has attracted much attention since it was first proposed in 1995. In some literatures, most researchers have focused their effrots on how to promote the convergence rate and avoid the premature convergence problem. Introducing new mechanisms to ensure the diversity
7、of swarm population or escape from local minima may be useful on reliveving premature convergence of the algorithm. As to improving convergence rate, much work focus on tuning strategy patameters, or modifying the original framework with ideas inspired from other meta-heuristics. As most researchers
8、 of this field are with pure scientific computing or engineering applications background, they care more about the results other than probe into the real cause, not to mention consider social psychology origins of the algorithm. We attach importcance to both theroetical analysis and experimental dem
9、onstration in the research. The paper made a detailed analysis and summary, which focuses on the impact of the topological structure. This paper attempts to make on the basis of some breakthrough or improvement for the topology 太原理工大学硕士研究生学位论文 IV structure of particle swarm optimization algorithm. M
10、ore importantly, relevant literatures have been proved that the topological structure had a great influence on performance of the algorithm about particle swarm. This paper focuses on studying a dynamics topology structure based on random particle swarm optimization, which uses of K means clustering
11、 algorithm to optimize to improve it. Firstly, this paper intruoduces some theories and basic knowledge on particle swarm optimization algorithm, and research achievements of PSO algorithm are summarized; Secondly, the dynamic topology strategy is presented, on the basis of existing PSO algorithm, a
12、nd the process of individual adaptive strategy, global update strategy and the neighborhood searching strategy and so on which are in the topology of the algorithm is given in detail. In addition, the theoretical advantages of this algorithm and its convergence are analyzed and demonstrated by using
13、 theorem which is discrete time system equation convergence theorem; Finally, in order to solve the optimal solution of a variety of multi-dimensional functions, the algorithm compares with the WMPSO and immune PSO algorithm from experiment, the experiments have proved the feasibility and effectiven
14、ess of the algorithm. KEY WORDS: particle swarm algorithm, topology structure, KRTG, fittess 太原理工大学硕士研究生学位论文 1 第一章 绪论 1.1 课题的背景和意义 粒子群优化算法PSO（Particle Swarm Optimization，简称PSO）是一种全局优化技术， 是属于群集智能算法的范畴。 粒子群算法启发于观察鸟群或鱼群行动时,能通过个体间特 别的信息传递方式，使整个团体朝预期较适合的方向、目标而去,这个概念是模仿生物行 为的反应来寻求完成群体最大利益的方法。 粒子群算法在多维空间函数
15、寻优、动态目标寻优等方面有着收敛速度快、解质量高、 鲁棒性好等优点 1。但是一旦维数上升, 其优化性能便急剧下降, 极易陷入局部最优解， 其主要原因是最优解在种群中的传播速度过快，以至于丧失了探索新区域的能力，因此 近几年来很多学者均致力于粒子群算法的改进工作。目前，对粒子群优化算法的改进主 要体现在以下几个方面：参数的改进和优化、惯性权值和加速因子的改进、混合粒子群 PSO算法、邻域拓扑结构等。 本文着重从粒子群的粒子关系入手，通过改进粒子群的拓扑结构来提高粒子群算法 的性能。 有关文献 2已通过实验证明不同的种群结构由于其自身的特性, 对粒子群中信息 的传递及种群的多样性变化有着较大的影响
16、。不同的粒子群邻居的拓扑结构是对不同类 型社会的模拟,如何选择拓扑结构以使粒子群算法有最佳性能是尚待研究的问题 3。 针对粒子群算法的拓扑结构改进，传统的方法主要有两种：静态拓扑结构和动态拓 扑结构。在静态拓扑结构方面， 有代表性的是Mendes和Kennedy在1998年用模拟退火算 法结合启发式搜索算法确定了PSO算法的5种基本拓扑结构 4。动态拓扑方面主要集中在 计算粒子间的距离和小世界理论上，比较有代表性的是王雪飞的小世界理论法和suguran 的最短距离法。 上述对粒子群算法的拓扑结构的改进虽然在一定程度上提高了算法的性能，但也出 现了以下缺点。其一，静态的拓扑结构限制了粒子自适应环境能力。其二，上述的动态 拓扑结构在建立过程中， 忽略了种群密度这个重要因素。 相关文献 5已经证明粒子群的种 群密度对算法的收敛性有很大影响。基于上述问题，受到蚁群算法中依适应度选择路径 的随机择优方案的启发, 为保证算法运行过程中粒子群的多样性, 并保证优秀解的影响 力本文提出基于 KRTG 的粒子群算法来动态改变粒子群拓扑结构的思想。该算法能动态 太原理工大学硕士研
