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

南京大学学报(自然科学版) ›› 2011, Vol. 47 ›› Issue (6): 504–514.

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

刘建华**，杨荣华，孙水华

出版日期:2015-05-08 发布日期:2015-05-08
作者简介: (福建工程学院计算机与信息科学系，350108)
基金资助:
福建省科技厅K类项日(JK2o11o35)

The analysis of binary particle swarm optimization

Liu Jian Hua ,Yang Rong Hua，Sun Shui Hua

Online:2015-05-08 Published:2015-05-08
About author: (Department of Computer and Information Science, Fujian University of Technology, Fuzhou，350108，China)

摘要/Abstract

摘要： 粒子群算法(Particle Swarm Optimization, PSO)主要用优化计算实值的连续性问题，而离散二进制粒子群算法(Binary Particle Swarm Optimization, BPSO)则用来优化离散空间问题，它扩展了
PSO算法的应用，现己广泛应用到各种离散优化问题计算中，但目前对BPSO算法的理论分析研究还很少，难以指导算法性能.木文从位改变概率和遗传算法的模式定理两方而对BPSO进行分析.分析得出，
BPSO算法具有很强全局搜索能力，但不能收敛于粒子的全局最优位置，而且随着算法迭代运行，BPSO的随机性越来越强，缺乏后期的局部搜索能力.木文利用基准的函数，通过仿真实验计算，验证木文的分
析结果.基于分析的结果，木文提出BPSO的改进方法，新方法采用新的概率映射函数和混合遗传算法的方法.通过对基准函数的仿真试验，验证了改进方法的有效性.

Abstract: 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 case 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 Ucnetic 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 UA in term of theory of Ucnetic 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 arc favorable of particle’s convergence to the optimal particle and intensify the local exploration of binary PSO. With Benchmark function, the experiment conducted in this paper illustrates that the improved binary

刘建华**，杨荣华，孙水华. 离散二进制粒子群算法分析*
[J]. 南京大学学报(自然科学版), 2011, 47(6): 504–514.

Liu Jian Hua ,Yang Rong Hua，Sun Shui Hua
. The analysis of binary particle swarm optimization
[J]. Journal of Nanjing University(Natural Sciences), 2011, 47(6): 504–514.

参考文献

[1] Eberhart R, Kennedy J. A new optimizer using particle swarm theory. Proceedings of the 6th International Symposium on Micro Machine and Human Science. Nagoya,Japan, 1995,39一43.
[2] Kennedy J，Eberhart R. Particle swarm optimization, IEEE international Conference on Neural Networks. Piscataway, New Jersy;IEEE 8crvicc Ccntcr, 1995，1942一1948.
[3] Shi Y，Eberhart R. A modified particle swarm optimizer, IEEE international Conference on Evolutionary Computation. New Jersy; IEEE Press, 1998，69一73.
[4] Wei J X, Sun Y H, Su X N. A novel particle swarm optimi}ztion based on immune selection. Journal of Nanjing University(Natural Sciences)，2010,46(1);l一9.(魏建香，孙越乱，苏新宁.一种基于免疫选择的粒子群优化算法.南京大学学报(自然科学),2010,46(1) ; l一9).
[5] Liu J H，Liu J W. A new particle swarm optimization algorithm and real-time control of traffic signal in urban intersection. Systems Engineering, 2007, 25(7):83一87.(刘建华，刘建伟.基于粒子群算法的城市单交叉II信号控制.系统工程，2007, 25(7) ; 83一87.
[6] Aler B, Vincent J，Anyakoha C . A review of particle swarm optimization.Natural Computing,2008,7(3):109~124
[7] Liu J H，Fan X P，Qu Z H. A new particle swarm optimization algorithm based on similarity. Control and Deceiosn, 2007，22(10):1155一1159.(刘建华，樊晓平，瞿志华.一种基于相似度的新型粒子群算法.控制与决策，2009, 22(10): 1155一1159).
[8] Liu J H，Fan X P, Qu G H. An improved particle swarm optimization with mutation based on similarity.The 3rd international Conference on Natural Computation. Haikou，China, 2007，9:824一828.
[9] Kennedy J，Eberhart R. A discrete binary version of the particle swarm algorithm. Proceeding of the World Multiconference on Systemics, Cybernetics and informatics. New Jcrsy; Piscataway, 1997，4104一4109.
[10] Salman A，Ahmad I，Al-madani S. Particle swarm optimization for task assignment problem. Microprocessors and Microsystems， 2002，26(8):363一371.
[11] Lian Z, Gu X, Jiao B. A novel particle swarm optimizztion algorithm for permutation flow-shop scheduling to minimize makespan. Chaos Solitons and Fractals, 2008, 35(5):851一861.
[12] Liao C J，Tseng C T，Luarn P. A discrete version of particle swarm optimization for flowshop scheduling problem. Computers and Operations Research, 2007, 34(10):3099一3111.
[13] Correa E S, Frcitas A A, Johnson C G. Particle swarm for attribute selection in Baycsian classification; An application to protein function prediction. Journal of Artificial Evolution and Applications, 2008, 8(2):1一12.
[14] Shen Q, Shi W M, Kong W, et al. A combination of modified particle swarm optimization algorithm and support vector machine for gene selection and tumor classification.Talanta, 2007，71(4):1679一1683.
[15] Yin P Y. A discrete particle swarm algorithm for optimal polygonal approximation of digital curves. Journal of Visual Communication and image Representation, 200，15(2):241一260.
[16] Zhang X M, Sun I. B, Han J Q, et al. An application of swarm intelligence binary particle swarm optimization (BPSO) algorithm to multi-focus image fusion. Optica Applicata, 2010 ,XL(4) : 919一963.
[17] Luh G C, Lin C Y, Lin Y S. A binary particle swarm optimization for continuum structural topology optimization. Applied Stilt Computing, 2010,11(2):2833一2844.
[18] Mohd S M, Sigeru O，Safaai D, et al. Particle swarm optimization with a modified sigmoid function for gene selection from gene expression data. Artificial Lifc and Robotics, 2010, 15(1):21 ~24.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed