【作者】 陈自郁；

【导师】 何中市；

【作者基本信息】 重庆大学 ， 计算机系统结构， 2009， 博士

【摘要】 粒子群优化(Particle Swarm Optimization, PSO)是由Kennedy和Eberhart于1995年提出的一种进化计算技术,其源于对鸟群捕食行为的研究。作为一种基于群体的随机算法,PSO采用速度——位置模型,避免了复杂的遗传操作,利用群体内个体间的合作与竞争实现寻优。由于思想简单、操作方便,该算法受到了人们广泛关注并成功应用于很多领域。然而,粒子群优化的研究还很不成熟,其理论研究较薄弱,易出现早熟收敛,且搜索精度有限,应用还存在局限性。本文从邻居拓扑结构、算法改进以及在离散优化问题中的应用三个方面对粒子群优化进行了深入研究。论文取得的主要成果与创新工作概括如下:①深入研究了邻居拓扑结构的图属性特征及其对PSO算法性能的影响。引入图属性(直径、平均路径长度、聚类系数和平均度)研究了典型的静态邻居拓扑结构(全互连、环形和冯诺依曼结构),给出了它们的图属性特征;分析了图属性特征对算法性能的影响以及图属性特征之间的关系;首次讨论了粒子的邻居分布对算法性能的影响以及聚类系数与邻居分布的关系。分析指出在平均度相同的情况下,聚类系数低的邻居拓扑结构通常具有较均衡的邻居分布和较短的直径与平均路径长度。②设计了一种新的静态邻居拓扑结构——无团邻居拓扑结构。无团邻居拓扑结构在给定的平均度下保持最小的聚类系数,具有较均衡的邻居分布。通过对具有相同平均度、不同聚类系数邻居结构的PSO算法的实验测试验证了聚类系数的作用和无团邻居拓扑结构的优越性,并且分析了无团邻居拓扑结构的平均度与群规模的关系。③研究提出了静态邻居结构上的一种新的信息共享机制——局部精英信息共享策略。首先分析了静态邻居结构上的信息共享机制,探讨了邻居结构间的关联性对算法的影响,提出粒子群中的“富人节点”和“富人俱乐部”现象,并指出粒子群中的“富人俱乐部”现象可能导致算法陷入局部最优;在此思想基础上,定义了局部影响因子和局部精英粒子,提出了局部精英信息共享策略。通过测试函数和群体多样性测量的实验说明,与其它不同共享机制的PSO算法比较,局部精英共享策略在邻居结构变化下性能表现出较好的稳定性,能较好地保持粒子多样性,但寻优速度较慢。④设计了两类基于编号的自适应邻居扩充PSO算法——基于自适应动态邻居结构的PSO算法(PSOSADN)和受约束的动态邻居扩充PSO算法(PSODNE)。两类算法利用粒子的自身特性和邻居状态,在环形结构的基础上通过不断扩充邻居来提高性能。在PSOSADN算法中根据粒子和邻居最优位置的关系,定义了粒子的扩充概率来自适应地调整粒子的扩充速度;同时,利用无团邻居拓扑结构的性质提出了三种邻居扩充策略,由此得到三个不同的PSO算法(PSOSADN1、PSOSADN2和PSOSADN3)。PSODNE算法则基于控制“富人节点”影响力的思想,通过定义粒子邻居扩充因子和邻居扩充与约束策略来调整粒子的邻居扩充行为和扩充速度。与基于不同邻居结构的PSO算法的比较实验,结果表明:PSOSADN1算法具有较快的收敛速度,PSOSADN2算法具有较好的平衡性能,而PSOSADN3和PSODNE算法在全局寻优能力方面表现较好。实验还分析了扩充行为对算法性能的影响。⑤设计了一种基于动态子群的混合粒子群优化算法(HPSODS)。HPSODS算法依据粒子的适应值特性,采用层次聚类将粒子动态地分为多个子群;并按照各子群的性能,将它们归为四类;每类采用不同作用的进化策略,合作实现优化任务。算法引入种群熵控制聚类频率,引入高斯变异和分段线性混沌映射设计出四种不同的进化策略,实现了不同区域、不同目的的寻优。通过实验分析了子群数和四种进化策略对算法的影响,给出了子群数的选择范围。与其它著名的PSO算法对比实验,结果表明:HPSODS算法在典型的单模和多模测试函数中均显示出更强的全局搜索能力、更高的求解精度、更快的收敛速度以及更好的稳定性。⑥建立了一种新的解决集合组合优化问题的离散粒子群优化模型(SDPSO),并由此设计出背包问题的集合解决方法。SDPSO模型将集合概念和运算引入到粒子群优化中,定义了一个可变集合搜索空间,重新定义了粒子的位置、速度及作用于此空间的运算规则。采用四个不同规模的背包实例进行测试,实验结果显示基于该模型的算法具有较强的寻优能力和较快的收敛速度明显优于传统的二进制PSO算法,说明所提离散模型的可行性和有效性。更多还原

【Abstract】 Inspired by the emergent motion of a flock of birds searching for food, Kennedy and Eberhart introduced a new evolutionary computation technique, Particle Swarm Optimization (PSO), in 1995. As a population-based stochastic algorithm, PSO adopts simple velocity-position model, avoids complex genetic operators and takes advantage of cooperation and competition among individuals in the swarm to attain the solution. Due to the simple concept and easy implementation, PSO has gained much attention and wide applications in different fields.However, the research on PSO is still far from maturity. PSO also suffers from unsubstantial theoretical analysis, premature convergence, unsatisfactory solution precision and limitation of applications. In our work, several aspects of PSO such as neighborhood topologies, algorithm modification and application in discrete optimization problems are studied intensively. The main contributions and innovations of this dissertation are summarized as follows:①Delve into the graph properties of neighborhood topologies and their influences on PSO’s performance. By introducing the graph properties (diameter, average path length, clustering coefficient and average degree),the typical static neighborhood topologies such as complete, ring and von Neumann structure are investigated and their graph properties are given. Also, the influences of these graph properties on PSO’s performance as well as the correlations between them are analyzed. It is, for the first time, discussed about the neighbor distribution’s effects on the performance of PSO and its connection with clustering coefficient. It is concluded that among topologies having same average degree, those with smaller clustering coefficient have more uniform neighbor distribution, smaller diameter and shorter average path length.②A new static neighborhood topology, the non-clique neighborhood topology, is designed. With a given average degree, the non-clique neighborhood topology possesses the lowest clustering coefficient and more uniform neighbor distribution. The performances of the PSO algorithms with different neighborhood topologies which have the same population size and average degree but different clustering coefficient are compared. The experimental results verify the effect of clustering coefficient and the superiority of the non-clique neighborhood topology. Additionally, a further experiment is made to analyze the relationship between average degree and population size in the non-clique neighborhood topology.③A new information-sharing mechanism, the local elitist information-sharing strategy, is proposed. Firstly, the existing information-sharing mechanisms on static neighborhood topologies are analyzed. Then, the influence of neighborhood correlation on the performance of PSO is discussed. The‘rich nodes’and the‘rich-club’phenomenon in the particle swarm are revealed. It is indicated that the‘rich -club’phenomenon may lead PSO to be trapped in local optimum. Based on this idea, local impact factor and local elitist particle are defined, and the local elitist information-sharing strategy is proposed. The experimental results on the benchmark functions and measurement of population diversity show that the PSO with the local elitist information-sharing strategy has better stability and larger diversity but slower searching speed than the PSOs with other information-sharing mechanisms on the different static neighborhood topologies.④Two types of the PSOs with number-based self-adaptive neighborhood extension, the PSO with self-adaptive dynamic neighborhoods (PSOSADN) and the PSO with restricted dynamic neighborhood extension (PSODNE), are developed. The proposed PSOs begin the search with ring topology and then employ neighborhood extension to improve the performance of the original PSO according to particle’s evolutionary state and neighborhood relation. In PSOSADN, an expanding probability, derived from the relation between particle and its neighbor best position, is introduced to adaptively adjust the expanding speed,and three expanding strategies are proposed on the basis of the quality of the non-clique neighborhood topology. Three different PSO algorithms, PSOSADN1, PSOSADN2 and PSOSAND3, are presented based on the three expanding strategies. Different from PSOSADN, PSODNE follows the idea of controlling the influence of‘rich nodes’. In PSODNE, neighborhood extension factor is defined and novel neighborhood extension & restriction strategies are proposed to adjust the expanding movement and speed. The proposed PSOs are compared with other PSOs using different neighborhood schemes on a suite of benchmark functions. The experimental results show that PSOSADN1 has great superiority on convergence speed, PSOSADN2 has better balanced performance, and PSOSADN2 & PSODNE outperform other PSOs on global searching ability. Also, an experimental analysis is presented about the influences of different extension movements on PSO’s performance. ⑤A hybrid particle swarm optimizer with dynamic subswarms (HPSODS) is proposed. On the basis of particle’s fitness value, hierarchical clustering method is adopted to dynamically divide the swarm into several subswarms in HPSODS. And these subswarms are classified into four categories according to their performance. Four different functional evolutionary strategies are used in each category and different functional categories cooperate to achieve good optimization performance. Moreover, population entropy is introduced to control clustering frequency. Gaussian mutation and piecewise linear chaotic map are used and four evolutionary strategies are developed to realize searching for different areas and purposes. The experiments are conducted to analyze the effects of the subswarm number and the proposed strategies on the performance of PSO. And the range of the subswarm number is suggested. The experimental results on the classic unimodal and multimodal benchmark functions demonstrate the superiority of the proposed HPSODS over some famous PSOs in terms of global searching ability, solution precision, convergence speed and stability.⑥A new discrete PSO model (SDPSO) for set-based combinatorial optimization problems is constructed and a set-based method for knapsack problems based on this model is designed. In SDPSO, set concepts and operations are introduced into particle swarm optimization. A search space of variable set is defined, particle’velocity and location are re-stated, and new operation rules are designed on the search space. Four knapsack examples with different scales are employed to test the model. The experimental results demonstrate the superiority of the algorithm based on SDPSO over the traditional binary PSO in terms of searching ability and convergence speed, which validates the feasibility and effectiveness of the proposed model.更多还原