刘雪静, 贺毅朝, 吴聪聪. 求解集合联盟背包问题的二次贪心变异乌鸦算法[J]. 微电子学与计算机, 2018, 35(11): 13-19.
引用本文: 刘雪静, 贺毅朝, 吴聪聪. 求解集合联盟背包问题的二次贪心变异乌鸦算法[J]. 微电子学与计算机, 2018, 35(11): 13-19.
LIU Xue-jing, HE Yi-chao, WU Cong-cong. Quadratic Greedy Mutated Crow Search Algorithm for Solving Set-Union Knapsack Problem[J]. Microelectronics & Computer, 2018, 35(11): 13-19.
Citation: LIU Xue-jing, HE Yi-chao, WU Cong-cong. Quadratic Greedy Mutated Crow Search Algorithm for Solving Set-Union Knapsack Problem[J]. Microelectronics & Computer, 2018, 35(11): 13-19.

求解集合联盟背包问题的二次贪心变异乌鸦算法

Quadratic Greedy Mutated Crow Search Algorithm for Solving Set-Union Knapsack Problem

  • 摘要: 针对确定性算法难以求解的集合联盟背包问题(Set-Union Knapsack Problem, SUKP), 提出了二次贪心变异乌鸦算法(quadratic greedy mutated crow search algorithm, QGMCSA).首先结合SUKP问题模型对贪心策略进行改进, 提出了处理其潜在解的二次贪心修复和优化策略; 其次, 为了扩大乌鸦个体的搜索范围, 对乌鸦算法进行变异操作, 在跟踪过程中引入莱维飞行; 最后, 利用三类SUKP实例验证本文算法.仿真结果表明:QGMCSA是比二进制人工蜂群算法求解SUKP的结果更优的一个高效算法.

     

    Abstract: In order to solve the Set-Union Knapsack Problem (SUKP) which is difficult to be solved by the deterministic algorithm, the quadratic greedy mutated crow search algorithm (QGMCSA) is proposed. Firstly, the greedy strategy is inproved by combining the SUKP model, and the quadratic greedy repair and optimization strategy is proposed to deal with its potential solutions. Secondly, in order to enlarge the search scope of the individual, Lévy flight is introduced into the tracking process of crow search algorithm. Finally three kinds of SUKP instances are used to verify the algorithm. Simulation results show that QGMCSA is better than binary artificial bee colony algorithm for solving SUKP, it is a an effective algorithm.

     

/

返回文章
返回