【作者】 徐星；

【导师】 李元香；

【作者基本信息】 武汉大学 ， 计算机软件与理论， 2010， 博士

【摘要】 智能是生命世界中最古老、最复杂和最奇妙的话题。古今中外,无数学者都曾对它进行过深入的思考和大胆的探索。半个世纪前,十多位数学、心理学和信息论方面的优秀学者为了利用计算机模拟自然智能尤其是人类智能而提出了“人工智能”这一崭新的学科,在随后几十年的发展过程中,人工智能得到了长足发展并形成了不同学术流派,然而制约人工智能发展的瓶颈也愈发突出。作为传统人工智能的延伸和扩展,计算智能与人工智能技术相互交叉和取长补短,在模拟非线性推理、模糊概念、记忆等方面表现优异。作为一种新的关于智能的描述方法,群智能已逐渐成为计算智能中新的研究热点。粒子群优化算法(PSO)是两种典型的群智能优化算法之一,由于其原理简单,既有传统演化计算技术深刻的背景又有自身独特的优化性能,自从提出以来,一直受到计算智能领域众多学者的广泛关注。鉴于此,计算智能领域的顶级期刊之一《IEEE Transactions on Evolutionary Computation》在2004年刊出了PSO的专刊,Eberhart和Shi在卷首语中指出了PSO今后五个研究热点和方向：算法理论、种群拓扑结构、参数选择与优化、与其他思想融合的混合算法和应用。根据这一指导思想,本文借鉴统计物理和热力学中的机制来设计和改进PSO算法,包括分子力、伊藤过程、扩散现象三个方面,然后把提出的改进PSO算法应用于非线性模型的参数估计,并设计和实现了PSO算法平台。全文主要内容和创新点如下：1.保持粒子的多样性是提高PSO算法性能的关键,受分子运动论思想的启发,提出了基于分子力的粒子群优化算法(MPSO)。类比热力学分子系统,在MPSO中引入了粒子间的分子力、群质心和粒子加速度共三个概念并对粒子的速度更新公式进行了改造。根据粒子与群质心距离的远近,分子力在斥力和引力之间转换并控制粒子的飞行方向以决定粒子是朝着群质心飞行还是远离它,从而有效地协调种群的多样性,使算法能够有效地平衡全局和局部搜索。此外,采用正交试验设计的方法对MPSO额外引进的两个参数进行了选择与优化。2.为了改善PSO的收敛速度,在布朗运动、伊藤过程和伊藤算法的启示下,提出了一类伊藤算法和PSO算法的混合算法。首先提出漂移算子和PSO的混合算法(IPSO1), IPSO1中粒子没有速度属性,引入了吸引子的概念,实验证明IPSO1相对于标准PSO收敛速度有较大提高但稳定性不足。为了解决此问题,在IPSO1基础上采取了两种策略,一是继续引入伊藤算法中的波动算子并利用差分变异算子来设计波动算子,另一是引入热力学选择机制,其中给出了粒子的相对能量、等级熵、自由能分量等定义,进一步的实验结果表明后两种算法在保留了IPSO1收敛速度快特点的同时,并具有良好的健壮性和稳定性。3.鉴于多种群的思想可以有效地提升PSO算法的性能,受自然界扩散和迁徙现象的启发,提出了基于物理学中热扩散机制的双种群粒子群优化算法(DPSO), DPSO中定义了粒子的扩散能、种群温度、粒子的扩散概率共三个概念。两个种群中的粒子根据各自的扩散概率被选入各种群的扩散池中,通过扩散池来实现种群之间信息的共享和扩散,从实验结果可以推断DPSO算法比PSO算法在中后期具有更好的进化能力。4.参数估计是系统辨识和回归分析中非常关键的环节,它关系到非线性模型的应用和推广。把非线性模型的参数估计问题转化成一个无约束的多维函数优化问题,以自然科学和社会科学中广泛使用的渐近回归模型和逻辑斯蒂模型为例,利用前述提出的四种改进PSO算法对两模型进行参数估计。实验中采用了真实数据、无噪声的随机采样数据以及添加了高斯噪声的采样数据,并利用后两类数据分析了参数估计的维数、采样区间和噪声强度对算法性能的影响,研究结果表明PSO算法是一种行之有效的非线性模型的参数估计方法。5.算法平台对于保证算法研究的连续性、成果保存、对比分析等方面起着举足轻重的作用,在分析了设计模式中各模式的适用范围和优缺点的基础上,利用策略模式对PSO算法平台进行设计,采用一系列策略类对不同的PSO算法进行封装,考虑程序的执行效率与方便于图形展示,最后采取了VC与MATLAB混合编程的措施对平台进行实现。更多还原

【Abstract】 Intelligence is the oldest, most complex and most wonderful topic of the living world. At all times and in all countries, numerous scholars have conducted a panoramic and profound study of it. Half a century ago, a dozen excellent scholars of math, psychology and information theory, to simulate natural intelligence, especially human intelligence with computer, proposed the new subject - "Artificial Intelligence". In the subsequent decades of the development process, this new subject has achieved a considerable progress and formed different academic schools; however, the bottleneck restricting the development of artificial intelligence has also become more and more prominent. As an extension and expansion of traditional artificial intelligence, Computational Intelligence and Artificial Intelligence technology intersect and complement each other, showing an outstanding performance in simulating non-linear reasoning, fuzzy concept, memory, and so on. As a new description method on Intelligence, Swarm Intelligence has gradually become the new hotspot of Computational Intelligence.Particle swarm optimization (PSO) is one of the two typical swarm intelligence optimization algorithms. Because of its simple in principle, both the profound background of the traditional evolutionary computation technology and its own unique optimization performance, it has attracted a wide attention from many scholars in the field of Computational Intelligence even since first proposed. Due to this, "IEEE Transactions on Evolutionary Computation", one of the top journals of computational intelligence, published the PSO’s special issue in 2004. Eberhart and Shi in the preface put forward five directions and focuses for future PSO research: algorithm theory, population topology structure, parameter selection and optimization, hybrid algorithms with the other evolutionary computation techniques and applications. Based on this guideline, the mechanism of statistical physics and thermodynamics, which consists of the molecular force, ITO process, and diffusion phenomenon, is utilized to design and modify the PSO algorithm in this paper. And then the improved PSO algorithms are applied to non-linear model parameters estimation, and lastly the PSO algorithm platform is designed and implemented. The main content and innovation points of the dissertation are as follows:Firstly, to maintain the diversity of particles is crucial to improve the performance of PSO algorithm. Enlightened by molecular kinetic theory, the particle swarm optimization algorithm based on the molecular force (MPSO) is put forward. To make an analogy to thermodynamic molecular system, in the MPSO, molecular force between particles, swarm centroid and particle acceleration are introduced and thus particle’s velocity updating formula is modified. The molecular force between itself and swarm centroid is presented as an attractive or repulsive force determined by the distance of them, and decides the particle to move towards the swarm centroid or to keep away from it for maintenance of diversity, hence the MPSO could effectively balance the global and local search. In addition, orthogonal test design method is applied to select and optimize the two additional parameters introduced in MPSO.Secondly, in order to improve the convergence rate of PSO, with the inspiration of the Brownian motion, ITO process, and ITO algorithm, a series of hybrid algorithms which mix ITO algorithm and PSO algorithm are proposed. In the first place, the PSO mixed with drift operator (ISPO1) is proposed. There is no speed attribute for particle of IPSO1, and the attractor concept is also introduced. It is proved that IPSO1 is much improved in convergence rate but is still short of sufficient stability comparing to the standard PSO. To solve this problem, the two strategies are taken on the basis of IPSO1. On the one hand, the fluctuation operator of ITO algorithm is introduced constantly and differential mutation operator is used to design the fluctuation operator. On the other hand, thermodynamic selection mechanism, which gives the particle relative energy, level entropy, free energy component, is introduced as well. And further experimental results show that the latter two algorithms retain the fast convergence characteristics of IPSO1, at the same time, possessing better robustness and stability.Thirdly, in view of that the thought of multi-populations can effectively improve the performance of PSO algorithm. Inspired by the phenomenon of the diffusion and migration, the double-swarms particle swarm optimization algorithm (DPSO) is proposed based on the heat diffusion mechanism. Particle diffusion energy, population temperature, and particle diffusion probability are defined in DPSO algorithm. During the evolution of DPSO, the particle of each swarm is chosen into the diffusion pool of each swarm. The diffusion pool of both swarms exchanged and shared information. It can be inferred from the experimental results that the DPSO algorithm has a better evolutionary capability than PSO in the later period.Fourthly, parameter estimation is the critical part of system identification and regression analysis and it relates to the application and promotion of nonlinear model. The parameter estimation problem of nonlinear model is transformed into an unconstrained multi-dimensional function optimization problem, and the four proposed PSO algorithms mentioned above are used to solve this problem, just taking the asymptotic regression model and the logistic model for example which are widespread in natural sciences and social sciences. There are real data, random sample data without noise, and sample data with Gaussian noise in the experiments. The latter two kinds of data are applied to analyze the impact of dimensions of parameter estimation, sampling interval and noise intensity on the algorithm performance, and experimental results show that PSO algorithm is an effective nonlinear model parameter estimation method.Finally, algorithm platform plays a decisive role in ensuring the continuity of algorithms research, saving the research results and conducting comparative analysis, etc. Based on the analysis of both the scope of application and advantages, disadvantages of all design patterns, the strategy pattern is used to design the PSO algorithm platform. A set of strategies classes is applied to package different PSO algorithms. Considering the implementation efficiency of programs and convenience in the graphical display, the mixed programming technology with VC and MATLAB is utilized to implement the platform.更多还原