关键词: 背包问题, 蜂群遗传算法, 主动进化算子, 最优交叉, 抑制算子

Abstract:

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-1Knapsack  problem, and is also suitable for other combinatorial optimization problems.

Key words: knapsack problem;bee swarm genetic algorithm;active evolution operator;best one crossover;restraint operator