【作者】 李宁；

【导师】 孙德宝；

【作者基本信息】 华中科技大学 ， 控制理论与控制工程， 2006， 博士

【摘要】 粒子群优化算法(PSO)是一种基于群智能的优化方法,由Kennedy和Eberhart于1995年提出。同遗传算法类似,它也是一种基于群体叠代的优化算法,系统由一群粒子组成,粒子群在问题空间中进行协同搜索,它没有遗传算法的交叉、变异等操作。它更强调群体内部个体之间的协同与合作,而不是GA所体现的达尔文“适者生存”理论。因为其具有快速性和易于实现等特点,目前成为了计算智能领域的新研究热点,其理论研究工作还处于起步阶段。本文对粒子群优化算法作了深入的理论分析,提出了几种改进算法,并将其应用于工程实践中。论文主要包括以下内容:对PSO算法的思想起源作了深入的阐述,首先简要介绍PSO算法的起源的研究背景和思想根源,然后对群智能理论的发展和主要研究方向作了讨论,并详细分析了PSO和EC的异同。从宏观和微观两个不同层面对PSO算法建立了数学模型,并作了深入的数学分析,首次将Markov链用于PSO算法的分析。在宏观上,首先对PSO算法的基本概念做严格的数学描述,定义粒子状态、粒子群状态、粒子群状态等价类等概念,证明了粒子群状态转移过程是Markov链过程,由此建立了PSO算法的Markov链模型;并在此基础上对PSO算法进行初步的收敛性分析,证明了PSO算法在整体上是无法保证收敛的。该分析方法对PSO的算法理论研究和改进提供了一种新思路,有重要意义。在微观上,利用差分方程及Z变化对单个粒子的速度变化过程、位置变化过程作深入的数学分析,得到了在不考虑随机量且pBest、gBest不变化的假设下,单个粒子运动轨迹收敛的条件不等式;并进一步讨论pBest、gBest变化和随机量对粒子运动轨迹的影响,以及单个粒子运动轨迹与算法收敛性之间的关系,还给出了指导工程实践中PSO参数调整的理论公式和条件。根据对PSO算法的理论分析和研究的结果,提出了两种带变异算子的改进PSO算法:MuPSO1、MuPSO2,和一种新的基于社会信息的改进PSO算法:C-Pg PSO。MuPSO1、MuPSO2算法通过粒子群迭代过程中的一些特征来判断算法是否停滞,在算法停滞时通过加入适量的变异操作来增加粒子群的多样性,从而实现提高收敛率的目的。C-Pg PSO算法的思路则是源于对社会的观察,通过增加一些其它的影响力,来减少因粒子群一直跟随gBest变化而陷入局部最优的机会。为检验改进算法的性能,本文在自主开发的测试平台上对一系列测试函数进行了大规模计算实验。首先对各改进算法的参数敏感性作了分析测试,然后对各改进算法的计算性能进行了对比分析测试和讨论,最后结合理论和实验所得的统计结果验证了改进算法的有效性和实用价值。并通过旋转卫星舱布局优化的实例对MuPSO1算法的性能进行了进一步的证实。以典型的组合问题带时间窗车辆路径问题作为研究对象,研究将PSO算法应用于组合优化的问题。根据车辆路径问题的特点,提出了一种合适的粒子表达方式,将多数约束包含在粒子表达方式中,大大减少不可行解的数量,使得不可行解的可行化计算过程简化,并通过几个实验证明了该表达方式的合理性和有效性。还讨论了将PSO算法应用于组合优化问题中必须考虑的问题,和一些值得注意的处理方法。将粒子群的思路引入多目标优化中,提出了一种基于粒子群的多目标优化算法。将算法已获得的非劣解粒子集合作为精英集,粒子在迭代过程中随机选取精英集中粒子作为gBest,粒子群体通过追随它们来寻找Pareto非劣解集,并利用小生境技术来筛选精英集中的粒子,从而保持所得非劣解集的均匀性,同时还采用边界变异和部分变异策略来提高非劣解的多样性。实验证明该方法是一种快速、有效的多目标优化方法。最后还讨论了可以进一步研究的工作和方向,其中包括群智能理论的扩展和定义、PSO算法的收敛率分析、PSO算法分析的数学手段和PSO算法在组合问题上如何应用等几个方面。更多还原

【Abstract】 Particle swarm optimization (PSO) is an optimization algorithm based on swarm intelligence developed by Kennedy and Eberhart in 1995. Similar to genetic algorithm, it is based on swarm iteration and consists of a group of particles cooperate to searching in the problem space. However it is unlike genetic algorithm in that there is no crossover and mutation operation. The inner cooperation is more emphasized, rather than the“survival of the fittest”theory of Darwin. Particle swarm optimization algorithm has become a new research hot point in computation intelligence area for the rapid convergence and simple to implementation, while the theory research is still in initial step stage. This thesis has made a deep theory analysis for particle swarm optimization, proposed several improved algorithms and applied it into engineering practice. Several points are included in this paper as follows:The thinking origin of PSO is reviewed thoroughly. Firstly the research background and thinking origin is introduced simply, followed along with the discussion about the development and mainly research direction of swarm intelligence theory. The comparison between PSO and EC is detailedly analyzed too.A deep mathematical analysis is made for PSO respectively from macroscopic and microscopic views. Firstly from macroscopic view, a strict mathematical description is given for the basic conception of PSO algorithm, with the definition of many notions, such as particle state, particle swarm state, particle swarm state equivalence class and so on. The particle swarm state transition equation has proved to be a Markov chain process, based on which, the Markov chain model of PSO is established. In the meantime, an elementary convergence analysis of PSO has finished, which testifies that PSO algorithm has no ability to guarantee the convergence. From microscopic view, difference equation and Z transform are adopted to analyze the velocity change process and position change process of single particle. Assuming that pBest and gBest have no change and ignoring random quantities, we can obtain the conditional expression about the convergence of single particle’s trajectory. A further discussion about the influence pBest、gBest and random quantity put on particle trajectory has been given, as well as the relationship between single particle’s trajectory and algorithm convergence. Theoretical formula and condition adjusting the parameter of PSO in engineering practice have also been offered.According to the theoretical analysis and research result of PSO, two improved PSO with mutation operator (MuPSO1 and MuPSO2) and a new improved PSO based on social information (C-Pg PSO) have been proposed in this paper. MuPSO1 and MuPSO2 judge whether the algorithm is stagnant by some attributes in particle swarm iteration, and if stagnant, then add some proper mutation operators to increase the variety of particle to enhance the convergence. The thinking of C-Pg PSO algorithm comes from social observation. It’s not easy to be trapped into local optimum, for particle swarm follows gBest to change at all times, by adding some other influence. A serial of test functions are tested on some massive computing to appraise the performance of all improved algorithms. First of all, an analysis testing about the sensitivity of parameters is made for all improved algorithms. Then a comparison analysis testing about the calculated performance is given too. At last, combined with theory and the test result above, a further discussion and analysis is provided for the calculated performance and use value of improved algorithms. The performance of MuPSO1 algorithm has been illustrated further by the rotating plane layout optimization instance.The application of PSO algorithm to combination optimization problem is developed, as the investigated subject is the typical combination problem: vehicle routing problem with time window. According to the features of vehicle routing problem, a proper particle expression is put forward, including most of constraint conditions, which leads to the result that the number of non-feasible solutions is reduced sharply, and the feasibility calculation on the non-feasible solution is simplified too. Moreover, the rationality and validity of the expression have been testified by several experiments. Some issues we must take into consideration when applying PSO to the combination optimization problem and remarkable processing methods are mentioned in addition.A multi-objective optimization algorithm has been proposed while the idea of particle swarm is introduced into multi-objective optimization. Take previously nondominiated vectors found by the algorithm as the elitism set. Randomly select particles from the elitism set as gBest in iteration, which are followed by the particle swarm to search Pareto nondominiated set. The niche technique is used to screen out the particles in the elitism set to maintain the uniformity of nondominiated set. At the same time, boundary mutation and portion mutation strategies are adopted to increase the diversity of nondominiated set. Experiments proof that this method is a quick and effective multi-objective optimization method.In the end, a discussion and analysis of promising research way based on this paper is presented, including the extension and definition of swarm intelligence, convergence analysis of PSO algorithm, mathematical techniques of PSO algorithm analysis and application of PSO algorithm for combination optimization problem etc.更多还原