离散二进制粒子群算法分析  

The analysis of binary particle swarm optimization

作　　者：刘建华[1] 杨荣华[1] 孙水华[1] 

机构地区：[1]福建工程学院计算机与信息科学系,福州350108

出　　处：《南京大学学报（自然科学版）》2011年第5期504-514,共11页Journal of Nanjing University（Natural Science）

基　　金：福建省科技厅K类项目(JK2011035)

摘　　要：粒子群算法(Particle Swarm Optimization,PSO)主要用优化计算实值的连续性问题,而离散二进制粒子群算法(Binary Particle Swarm Optimization,BPSO)则用来优化离散空间问题,它扩展了PSO算法的应用,现已广泛应用到各种离散优化问题计算中,但目前对BPSO算法的理论分析研究还很少,难以指导算法性能.本文从位改变概率和遗传算法的模式定理两方面对BPSO进行分析.分析得出,BPSO算法具有很强全局搜索能力,但不能收敛于粒子的全局最优位置,而且随着算法迭代运行,BPSO的随机性越来越强,缺乏后期的局部搜索能力.本文利用基准的函数,通过仿真实验计算,验证本文的分析结果.基于分析的结果,本文提出BPSO的改进方法,新方法采用新的概率映射函数和混合遗传算法的方法.通过对基准函数的仿真试验,验证了改进方法的有效性.Particle Swarm Optimization（PSO） is an evolutionary computation inspired by swarm intelligence.Compared to other evolutionary computation algorithms,PSO can not only solve a variety of difficult optimization problem,but also is ease to be used.So,PSO have been used across a wide range of applications.But PSO is mainly applied in the area of continuous space and rarely in that of discrete space.In order to be used in discrete space,binary Particle Swarm Optimization（BPSO） was developed to make PSO capable to optimize the combination problem,which extended particle swarm optimization and is used to optimize the discrete binary space problem.Although BPSO has been proposed for over ten years and has been used in many combination optimizing problems and applied in many areas,it was rarely analyzed.In this paper,the binary Particle Swarm Optimization（BPSO） is analyzed with bit change probability and schema theorem of Genetic Algorithm（GA）.On the one hand,the change probability of every bit of BPSO is computed.And It was found that change probability of every bit of BPSO is bigger and bigger with iteration going on.On the other hand,BPSO just uses the mutation of GA in term of theory of Genetic Algorithm,and is lack of the operation and crossover of selection,so it cannot keep the optimal schema increase in BPSO with iteration going on in term of schema theorem of GA.From the two ways,it was found that binary PSO is more and more stochastic,which has the powerful ability of global search,but cannot converges to the optimal particle of swarm.With the iteration going on,the randomness of BPSO is more and more powerful,so the Binary PSO is lack of local exploration which instructs the improvement of BPSO.And then,experiments conducted with Benchmark function have tested the results in this paper.Based on the analysis,an improved Binary PSO is proposed which changes the formula of its probability mapping and the formula of bit obtaining value.The new formulas are favorable of particle＇s convergence to the

关 键 词：二进制粒子群算法 收敛性 位改变概率 模式定理 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]