基于蜂群遗传算法的0-1背包问题

The 0-1 Knapsack Problem Based on the Bee-Swarm Genetic Algorithm

针对0-1背包问题,本文提出了基于蜂群遗传算法的优化求解方案。该算法包括两个种群,一个主要用于全局搜索,另一个主要用于局部搜索;每个个体采用二进制编码;采用最优个体交叉策略;对当前解的处理措施是将还未装入背包且性价比最好的物品装进背包,直至不能装为止;不符合约束条件的解采用诱变因子指导变异处理;遗传算子包括单点交叉算子、简单变异算子、主动进化算子和抑制算子。本算法充分发挥了遗传算法的群体搜索和全局收敛的特性,快速地并行搜索,有效地克服了经典遗传算法容易陷入局部最优问题。数值实验表明,该算法在求解0-1背包问题中取得了较好的效果,同样可以应用于其它的组合优化问题。

This paper presents a bee-swarm genetic algorithm for the 0-1 knapsack problem.There are two populations,one for global search,and the other for local search.Each individual adopts the binary code.Only the best one can crossover.The strategy of managing the feasible solution is to enclose the goods which is out of the knapsack and cost-effective,until no goods can be put into.The solution which does not accord with the constraint condition mutates under the instruction of mutagens.The genetic operators include order crossover operator,two-block-exchange mutation operator and restraint operator.The method sufficiently takes the advantage of the genetic algorithm such as group search and global convergence in order to have a quick parallel search,which efficiently overcomes the problem of local optimization.The experimental results show that the bee swarm genetic algorithm is efficient in solving the 0-1 Knapsack problem,and is also suitable for other combinatorial optimization problems.