【作者】 刘建华；

【导师】 樊晓平；

【作者基本信息】 中南大学 ， 控制科学与工程， 2009， 博士

【摘要】 粒子群算法在仿真生物群体社会活动的基础上,通过模拟群体生物相互协同寻优能力,从而构造出一种新的智能优化算法。但粒子群算法本身来源于生物群体现象,其理论基础并不完备。而且由于其属于随机的近似优化算法,主要应用于连续区域,因此该算法存在早熟收敛和对离散性的问题难以应用的缺点。因此,对粒子群算法的理论分析、算法改进及离散性问题的研究具有重要意义的。本文在前人工作的基础上对标准粒子群算法和离散二进制粒子群算法进行分析、改进,获得以下结果:(1)粒子群算法是一种启发式随机优化算法,每个粒子追逐自身最优粒子和全局最优位置搜索,并且追逐时带有随机因素。粒子群算法在这种随机搜索过程中,粒子最终会收敛于群体最优粒子。本文在增加随机性和粒子最优点更新的条件下,理论上证明了粒子的轨迹收敛于群体最优粒子位置。根据分析的理论结果,进一步说明了算法权重选择的原理。(2)由于粒子轨迹最终收敛于群体最优粒子,本文定义一个粒子间的相似度概念,设计计算群体粒子的多样性的概念公式—聚集度—通过计算群体粒子与群体最优粒子的平均相似度,度量粒子群的多样性程度。根据群体聚集度及其与群体最优粒子相似度,每个粒子随机产生变异,由此,构造了一种对标准PSO算法的改进算法,提高算法的全局搜索能力、避免早熟收敛,有效地提高标准PSO算法的性能。(3)标准PSO算法的权重是平衡算法全局搜索与局部搜索能力的参数,其取值影响算法的性能。标准PSO算法的权重采用从早期偏大到晚期偏小的线性递减方法,但每个粒子的权重大小一样。本文根据粒子与群体最优粒子的相似度,对不同粒子赋予不同权重,使每个粒子的权重不同,并且随着算法迭代而动态变化,这样构造一种权重动态变化的粒子群算法。经仿真实验验证,该方法有效。(4)PSO算法的理论分析构造了一个数学模型,数学模型从数学角度清楚地体现算法本身的数学含义。本文利用此数学模型代替原始PSO算法速度及位置的更新公式,得到一种新的进化算法,并且分析新的进化算法参数的选择。新算法形式能直接体现PSO算法的数学思想。经仿真试验检验,新算法效果不会差于标准PSO算法。本文将新的算法应用于求解单交叉口信号灯的时间优化分配,实验仿真结果表明,本文的算法在静态环境下很有效的。(5)二进制离散PSO算法为求解二进制的离散组合优化问题而构造一种PSO算法。本文从位改变率、速度的期望值及遗传算法模式概念等三个方面对其进行分析。本文得到:二进制PSO算法不收敛于群体最优粒子,其位值随着迭代运行而越来越随机。因此,二进制PSO算法缺乏局部探测性且具有偏强的全局开拓性。本文对原始二进制PSO算法进行改进,使其产生符合PSO算法思想(跟随群体最优粒子)的形式。将改进的方法应用于求解0/1背包问题。通过实验对比,新改进的二进制PSO算法提高了原始二进制PSO算法的性能。更多还原

【Abstract】 Particle Swarm Optimization is an intelligence algorithm constructed by the simulation of biologic swarm social activity, which imitated cooperative ability of searching optimal location of biologic swarm and is developed as an optimization algorithm. But, because it is a stochastic approximate algorithm, the theory of Particle Swarm Optimization is incomplete, and there exist deficiencies on premature convergence and difficulty of application in discrete problem. So, the research on the theory analysis, improvement and discrete problem of particle swarm optimization is very significant. In this thesis, we have analyzed and improved standard particle swarm optimization and binary particle swarm optimization. We have following conclusions:Particle swarm optimization is a stochastic algorithm with heuristic information, each particle fly following the self optimal location and global optimal location with stochastic factor. It has been analyzed that the particles converge to the global optimal location with stochastic iteration going on. In the condition of adding stochastic factor and the optimal particle updation, it has been proved that the particle trajectories will converge to the swarm optimal location in this thesis.During the running of the algorithm, the particles become more and more similar, and cluster into the best particle in the swarm, which make the swarm premature convergence around the local solution. In this thesis, a new conception, collectivity, is proposed which is based on similarity between the particle and the current global best particle in the swarm. And the collectivity was used to randomly mutate the position of the particles, which make swarm keep diversity in the search space. Experiments on benchmark functions show that the new algorithm outperforms the standrard PSO and other improved PSO.In fact, PSO is a random evolution algorithm. However, during the evolution of the algorithm, the magnitude of inertia weight has impact on the exploration and exploitation of PSO, which is a contradiction. In this thesis, a new PSO algorithm, called as DPSO, is proposed in which the inertia weight of every particle will be changed dynamically with the distance between the particle and the current optimal position. Experiments on benchmark functions show that DPSO outperform standard PSO.The current theory of PSO has constructed a mathematic modal, which can give a clear essence of PSO from mathematic view.In this thesis, the velocity and location updating equation are replaced by the mathematic equation, and get a new evolutionary algorithm. By select appropriate parameters, the performance of new algorithm is not inferior to standard PSO by simulation on benchmark functions. The new algorithm was applied to the real-time dynamic model on multiphase traffic flows. A simulation experiment for the traffic model at a four-phase intersection is also performed in this thesis. The results show that the method is effective.Binary PSO is a new method to solve discrete problem, which is applied in many area. In this thesis, Binary PSO has been analyzed through bit change rate, velocity expected value and genetic algorithm pattern theory. It has been found that binary PSO is not converge to global optimal particle, and the bit is more and more stochastic with iteration going on, so it is lack of local exploration. So, an improved binary PSO are proposed which meet the idea of PSO.更多还原