基于改进的蜂群遗传算法求解多选择背包问题  

Bee-swarm genetic algorithm for multiple-choice knapsack problem

作　　者：吴迪[1] 杨欣宇[1] 王崇[1] 李卫平[2] 

机构地区：[1]齐齐哈尔大学计算机与控制工程学院,黑龙江齐齐哈尔161006 [2]武汉理工大学信息工程学院,武汉430070

出　　处：《计算机应用研究》2014年第6期1632-1634,共3页Application Research of Computers

基　　金：黑龙江省教育厅科学技术研究项目(12531759);国家自然科学基金资助项目(201129493)

摘　　要：多选择背包问题是组合优化中的典型NP难题之一。针对传统蜂群算法存在的收敛速度慢、易陷入局部最优的缺点,提出改进策略。改进的算法通过设置两个自适应变化的种群雄蜂群和雌蜂群,雄蜂群负责与蜂后交叉操作以保持种群的选择压力,雌蜂群负责自适应变异操作以保持种群多样性,蜂后则根据启发式规则主动进化以局部寻优。根据算法实现的核心思想,仿真实验结果表明,提出的改进算法可以有效避免陷入局部最优,同时通过实例也验证了算法的可行性和有效性。Multiple-choice knapsack problem （MCKP） is NP hard as one of combinatorial optimization. This paper proposed a bee-swarm genetic algorithm （BSGA） to solve MCKP. There were two adaptive populations in BSGA, male bee swarm cross- overed with queen to keep pressure of selection, female swarm mutated to keep population diversity, the queen evolved under the instruction of heuristic rules. It presented the main idea of BSGA and implemented by MATLAB. Through a kind of instances, BSGA compared with other algorithms ,it shows the feasibility and effectiveness of the proposed algorithm.

关 键 词：多选择背包问题 蜂群遗传算法 双种群 主动进化 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]