面向离散优化问题的改进二元粒子群算法

An Improved binary particle swarm optimization for discrete optimization problems

二元粒子群算法被广泛用于求解离散组合优化问题。在求解离散优化问题时,二元粒子群算法会出现解空间利用率低,速度和状态趋同以及退化和波动等演化问题。针对这些问题,提出一种改进的二元粒子群算法。算法使用Gray码演化基编码,混沌初始化过程,改进速度和状态调整方法以及子代处理方法用于提高种群利用率和种群多样性。在不同类型的检验函数以及多选择背包问题上,和现有优化算法及其他二元粒子群算法相比,改进算法能够获得较高的收敛精度以及较快的收敛速度,体现出多离散优化问题的实际效用。

Binary particle swarm optimization （BPSO） is wildly used to solve discrete combinational optimization problems. With the low amount of population size and limit iterations, BPSO would have the evolutional problems such as low utilization of solution space, convergence of the speed and status of particles, as well as the degradation and volatility during the iterations. To solve these problems, an improved binary PSO （IBPSO） is designed, which uses the Gray code evolution based coding, chaos initialization process of population, improved modification of the speed and status of particles and the off-spring processing to increase the diversity and utilization of the population. According to the experimental results on the test functions with different types and multiple choice knapsack problems, IBPSO outperforms the existing optimization algorithms and other binary algorithms with higher precision solution and faster convergence speed, which shows the practicality of multiple discrete optimization problems.