离散型鸡群优化算法在0-1背包中的应用
|
摘要
为了进一步拓宽鸡群算法的研究领域,设计一种离散型鸡群算法(DCSO)。针对0-1背包问题的特点,在基本鸡群算法的基础上,对更新后的鸡群进行离散化处理,同时,在公鸡的位置更新过程中,引入自适应权重组合变异算子并动态调整变异权重,增强种群的多样性,更好地维持算法的"开采"与"搜索"两个阶段的平衡。最后,采用贪心修复算子对不可行解进行修正。通过4个经典0-1背包问题实例的仿真结果表明,相比离散粒子群算法、遗传算法和蚁群算法,DCSO算法在解的质量、收敛速度以及鲁棒性等方面效果显著提升,验证了该算法的可行性。
In order to further expand the research field of chicken swarm optimization,a discrete chicken swarm optimization( DCSO) algorithm is designed. According to the characteristics of the 0-1 knapsack problems,based on the chicken swarm algorithm,this paper discretes the updated chickens. At the same time,in the process of the rooster location update,this algorithm employs the adaptive weight combined mutation operator and adjusts the weight of mutation dynamically,enhances the diversity of population,better balances the " development" and " exploration" of the algorithm.Finally,greedy repair operator is used to modify the unfeasible solutions. Experiments are conducted on the 4 classical 0-1 knapsack problems,all results showthat compared with discrete particle swarm optimization algorithm, genetic algorithm and ant colony algorithm, DCSO algorithm is improved significantly in the solution accuracy,convergence speed and robustness. The feasibility of this algorithm is verified.
In order to further expand the research field of chicken swarm optimization,a discrete chicken swarm optimization( DCSO) algorithm is designed. According to the characteristics of the 0-1 knapsack problems,based on the chicken swarm algorithm,this paper discretes the updated chickens. At the same time,in the process of the rooster location update,this algorithm employs the adaptive weight combined mutation operator and adjusts the weight of mutation dynamically,enhances the diversity of population,better balances the " development" and " exploration" of the algorithm.Finally,greedy repair operator is used to modify the unfeasible solutions. Experiments are conducted on the 4 classical 0-1 knapsack problems,all results showthat compared with discrete particle swarm optimization algorithm, genetic algorithm and ant colony algorithm, DCSO algorithm is improved significantly in the solution accuracy,convergence speed and robustness. The feasibility of this algorithm is verified.
引文
[1]RAJABIOUN R.Cuckoo optimization algorithm[J]. Applied Soft Computing,2011,11(8):5508-5518.
[2]KENNEDY J,EBERHART R C. A discrete binary version of the particle swarm algorithm[C]//1997 IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation.Orlando,FL,USA:IEEE,1997:4104-4108.
[3]张晶,吴虎胜.改进二进制布谷鸟搜索算法求解多维背包问题[J].计算机应用,2015,35(1):183-188.
[4]宋晓萍,胡常安.离散杂草优化算法在0/1背包问题中的应用[J].计算机工程与应用,2012,48(30):239-242,248.
[5]吴虎胜,张凤鸣,战仁军,等.求解0-1背包问题的二进制狼群算法[J].系统工程与电子技术,2014,36(8):1660-1667.
[6]MENG Xianbing,LIU Yu,GAO Xiaozhi,et al. A new bio-inspired algorithm:Chicken swarm optimization[M]//TAN Y,SHI Y,COELLO C A C. Advances in Swarm Intelligence. ICSI 2014. Lecture Notes in Computer Science. Cham:Springer,2014,8794:86-94.
[7]田烽楠,王于.求解0-1背包问题算法综述[J].软件导刊,2009,8(1):59-61.
[8]杨小健,徐小婷,李荣雨.求解高维优化问题的遗传鸡群优化算法[J].计算机工程与应用,2018,54(11):133-139.
[9] FOURIE P C,GROENWOLD A A. The particle swarm optimization algorithm in size and shape optimization[J].Structural and Multidisciplinary Optimization,2002,23(4):259-267.
[10]贺毅朝,宋建民,张敬敏,等.利用遗传算法求解静态与动态背包问题的研究[J].计算机应用研究,2015,32(4):1011-1015.
[11]马慧民,叶春明,张爽.二进制改进粒子群算法在背包问题中的应用[J].上海理工大学学报,2006,28(1):31-34.
[12]周方俊,王向军,张民.基于t分布变异的进化规划[J].电子学报,2008,36(4):667-671.
[13]刘建芹,贺毅朝,顾茜茜.基于离散微粒群算法求解背包问题研究[J].计算机工程与设计,2007,28(13):3189-3191,3204.
[2]KENNEDY J,EBERHART R C. A discrete binary version of the particle swarm algorithm[C]//1997 IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation.Orlando,FL,USA:IEEE,1997:4104-4108.
[3]张晶,吴虎胜.改进二进制布谷鸟搜索算法求解多维背包问题[J].计算机应用,2015,35(1):183-188.
[4]宋晓萍,胡常安.离散杂草优化算法在0/1背包问题中的应用[J].计算机工程与应用,2012,48(30):239-242,248.
[5]吴虎胜,张凤鸣,战仁军,等.求解0-1背包问题的二进制狼群算法[J].系统工程与电子技术,2014,36(8):1660-1667.
[6]MENG Xianbing,LIU Yu,GAO Xiaozhi,et al. A new bio-inspired algorithm:Chicken swarm optimization[M]//TAN Y,SHI Y,COELLO C A C. Advances in Swarm Intelligence. ICSI 2014. Lecture Notes in Computer Science. Cham:Springer,2014,8794:86-94.
[7]田烽楠,王于.求解0-1背包问题算法综述[J].软件导刊,2009,8(1):59-61.
[8]杨小健,徐小婷,李荣雨.求解高维优化问题的遗传鸡群优化算法[J].计算机工程与应用,2018,54(11):133-139.
[9] FOURIE P C,GROENWOLD A A. The particle swarm optimization algorithm in size and shape optimization[J].Structural and Multidisciplinary Optimization,2002,23(4):259-267.
[10]贺毅朝,宋建民,张敬敏,等.利用遗传算法求解静态与动态背包问题的研究[J].计算机应用研究,2015,32(4):1011-1015.
[11]马慧民,叶春明,张爽.二进制改进粒子群算法在背包问题中的应用[J].上海理工大学学报,2006,28(1):31-34.
[12]周方俊,王向军,张民.基于t分布变异的进化规划[J].电子学报,2008,36(4):667-671.
[13]刘建芹,贺毅朝,顾茜茜.基于离散微粒群算法求解背包问题研究[J].计算机工程与设计,2007,28(13):3189-3191,3204.