平均计算时间复杂度优化的动态粒子群优化算法  

Average Computational Time Complexity Optimized Dynamic Particle Swarm Optimization Algorithm

作　　者：王沁[1] 李磊[1] 陆成勇[1] 孙富明[1] 

机构地区：[1]北京科技大学信息工程学院,北京100083

出　　处：《计算机科学》2010年第3期191-194,288,共5页Computer Science

基　　金：863国家重点基金项目"负载自适应的低功耗异构多核网络处理器研究"(2008AA01Z134)资助

摘　　要：粒子群优化(PSO:Particle Swarm Optimization)算法已经被广泛地应用,其中包括大量实时性要求很高的领域,如宽带数字信号处理。传统PSO算法需要对大量粒子分别进行若干次迭代运算,这将导致该算法的平均计算时间复杂度较高,运算延时大,不能满足这种高实时性要求。因此,需要在不影响性能的前提下降低PSO算法的平均计算时间复杂度。提出了一种粒子数量可变的动态粒子群优化(DPSO:Dynamic PSO)算法,其核心是丢弃粒子判定条件,在迭代过程中,根据该条件动态地抛弃一些粒子,从而降低算法的平均计算时间复杂度。此外,在算法迭代过程中对粒子的个体极值进行变异,从而避免陷入局部最优解。实验和理论分析结果表明,在算法的平均计算时间复杂度方面,对于相同的优化结果,DPSO算法的平均计算时间复杂度比传统PSO算法降低了30%左右;在算法的性能方面,对于单峰值目标函数,DPSO算法与传统PSO算法的优化性能相当,而对于多峰值目标函数,DPSO算法的优化性能要优于传统PSO算法。Particle Swarm Optimization algorithm is widely used in many fields including lots of situations with high real time requirements such as wide-band digital signal processing. A great number of particles should be updated in iteralion in traditional PSO algorithm. So the average computational time complexity is high. This property of traditional PSO algorithm leads to serious delay which makes it could not be used in system with high real-time requirements. So,the average computational time complexity of traditional PSO algorithm should be reduced with negligible performance penalty. We proposed a Dynamic PSO （DPSO） with adjustable particle quantity algorithm. The core of this algorithm is the criteria of discarding particles. During iterations, some of particles will be discarded dynamically to reduce the average computational time complexity. Furthermore, the mutation was used on local best position in iterations to avoid involving in local optimum solution. Simulation results and theoretical analysis show the average computational time complexity of DPSO algorithm is reduced by about 30 0 o under the condition of similar optimum solution compared with traditional PSO algorithm. In terms of algorithm performance, the performance of DPSO algorithm is same as that of traditional PSO algorithm for the single-modal optimization. On the other side,the performance of DPSO will be better than traditional PSO for multimodal optimization.

关 键 词：平均计算时间复杂度 粒子群优化 动态 变异 多峰值函数优化 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]