求解0-1背包问题的贪心优化粒子群算法
|
摘要
为进一步加快粒子群算法求解0-1背包问题的收敛速度,通过对现有背包问题中非正常编码个体处理方法存在的不足进行分析,本文在传统粒子群算法中加入了贪心修复算子和贪心优化算子,提出了一种求解0-1背包问题的改进粒子群算法。仿真实验结果表明:在求解0-1背包问题时,与遗传算法、离散粒子群算法、蚁群算法等相比,该算法不仅显著提高了收敛速度,而且具有较强的寻优能力和鲁棒性。
To further accelerate the convergence speed of the 0-1 knapsack problem solved by particle swarm optimization,an improved particle swarm optimization algorithm for 0-1 knapsack problem is proposed by adding the greedy repair operator and greedy optimize operator to the traditional particle swarm optimization algorithm. It is based on the analysis of deficiencies in the processing methods of non-normal coding individuals in the existing knapsack problem. The results of simulation experiments show that compared with genetic algorithm,discrete particle swarm optimization and ant colony algorithm,this algorithm not only improves the convergence speed significantly but also performs better in searching ability and robustness when solving 0-1 knapsack problem.
To further accelerate the convergence speed of the 0-1 knapsack problem solved by particle swarm optimization,an improved particle swarm optimization algorithm for 0-1 knapsack problem is proposed by adding the greedy repair operator and greedy optimize operator to the traditional particle swarm optimization algorithm. It is based on the analysis of deficiencies in the processing methods of non-normal coding individuals in the existing knapsack problem. The results of simulation experiments show that compared with genetic algorithm,discrete particle swarm optimization and ant colony algorithm,this algorithm not only improves the convergence speed significantly but also performs better in searching ability and robustness when solving 0-1 knapsack problem.
引文
[1]刘逸.粒子群优化算法的改进及应用研究[D].西安:西安电子科技大学,2013.
[2]陶新民,付丹丹,刘玉,等.双尺度变异离散粒子群算法求解背包问题[J].系统仿真学报,2013,25(01):12-17.
[3]张其亮,陈永生.基于模拟退火思想改进的粒子群算法求解背包问题[J].现代电子技术,2010,33(12):85-86+89.
[4]贺毅朝,宋建民,张敬敏,等.利用遗传算法求解静态与动态背包问题的研究[J].计算机应用研究,2015,32(04):1011-1015.
[5]田烽楠,王于.求解0-1背包问题算法综述[J].软件导刊,2009,8(01):59-61.
[6]刘建芹,贺毅朝,顾茜茜.基于离散微粒群算法求解背包问题研究[J].计算机工程与设计,2007,28(13):3189-3191+3204.
[7]徐俊杰,忻展红.粒子群优化在0/1背包问题中的应用[C]//中国运筹学会.中国运筹学会第七届学术交流会论文集(上卷).中国香港:Global-Link出版社,2004:131-135.
[8]KENNEDY J,EBERHART R C.A Discrete Binary Version of the Particle Swarm Optimization Algorithm[C]//IEEE Service Center.Proceedings of 1997 IEEE International Conference on Systems,Man and Cybernetics.Piscataway:IEEE,1997:4104-4108.
[9]马慧民,叶春明,张爽.二进制改进粒子群算法在背包问题中的应用[J].上海理工大学学报,2006,28(01):31-34.
[10]莫愿斌,马彦追,郑巧燕.求解0-1背包问题的萤火虫算法[J].计算机工程与设计,2014,35(08):2778-2784.
[11]姜长元.改进蚁群算法求解0/1背包问题[J].软件导刊,2009,8(12):52-54.
[2]陶新民,付丹丹,刘玉,等.双尺度变异离散粒子群算法求解背包问题[J].系统仿真学报,2013,25(01):12-17.
[3]张其亮,陈永生.基于模拟退火思想改进的粒子群算法求解背包问题[J].现代电子技术,2010,33(12):85-86+89.
[4]贺毅朝,宋建民,张敬敏,等.利用遗传算法求解静态与动态背包问题的研究[J].计算机应用研究,2015,32(04):1011-1015.
[5]田烽楠,王于.求解0-1背包问题算法综述[J].软件导刊,2009,8(01):59-61.
[6]刘建芹,贺毅朝,顾茜茜.基于离散微粒群算法求解背包问题研究[J].计算机工程与设计,2007,28(13):3189-3191+3204.
[7]徐俊杰,忻展红.粒子群优化在0/1背包问题中的应用[C]//中国运筹学会.中国运筹学会第七届学术交流会论文集(上卷).中国香港:Global-Link出版社,2004:131-135.
[8]KENNEDY J,EBERHART R C.A Discrete Binary Version of the Particle Swarm Optimization Algorithm[C]//IEEE Service Center.Proceedings of 1997 IEEE International Conference on Systems,Man and Cybernetics.Piscataway:IEEE,1997:4104-4108.
[9]马慧民,叶春明,张爽.二进制改进粒子群算法在背包问题中的应用[J].上海理工大学学报,2006,28(01):31-34.
[10]莫愿斌,马彦追,郑巧燕.求解0-1背包问题的萤火虫算法[J].计算机工程与设计,2014,35(08):2778-2784.
[11]姜长元.改进蚁群算法求解0/1背包问题[J].软件导刊,2009,8(12):52-54.