摘要
针对二进制粒子群算法在求解大规模多维背包问题时存在迭代次数过多、精度不高的不足,提出一种改进的二进制粒子群算法,新算法利用种群个体极值的平均信息和粒子的个体极值决定粒子当前取值的概率,使粒子可以充分利用整个种群的信息,避免算法陷入局部极值,并利用贪婪算法对进化过程中的不可行解进行修复,对背包资源利用不足的可行解进行修正.通过对典型多维背包问题的仿真实验和与其它算法的比较,表明算法有良好的全局优化能力和较好的收敛速度.
Binary particle swarm optimization takes too much time and solves imprecisely for large-scaled multidimensional knapsack problem, a modified binary particle swarm opti- mization is proposed in this paper to overcome this shortcoming. The new algorithm uses the values of the average individual best position and the individual best position depend on the probability of the position vector, makes each particle use the whole swarm information effectively to avoid local optima. During the evolution process, it uses the greedy algorithm repairs the infeasible solution and rectify knapsack resources with insufficient use. Simulated tests of multidimensional knapsack problem and comparisons with other algorithms show the algorithm has strong global optimization ability and a good speed of convergence.
出处
《数学的实践与认识》
CSCD
北大核心
2013年第19期129-137,共9页
Mathematics in Practice and Theory
基金
贵州省教育厅科研项目(黔教科2010093)
泰州市社会发展计划项目(2011044)
江苏省高等学校大学生实践创新训练计划项目(2012JSSPITP3029)
南京师范大学泰州学院资助项目(Q201232)
关键词
粒子群算法
二进制
平均信息
多维背包问题
贪婪算法
particle swarm optimization
binary
average information
.multidimensionalknapsack problem
greedy algorithm
