关键词: 01背包问题, 价值密度, 贪婪策略, 蛙跳算法, 最小分配

Abstract: 01 knapsack problem(01kp) is a classic combinatorial optimization problem and appears in many models of real world problem,such as cargo loading,budget control,resource allocation,financial management,and so forth.Many scientists have studied on this area for several decades and achieved a rich harvest.Even though 01kp has been researched for many years,it has been proved to be an NP complete problem,thus finding the best solution is not easy.In recent years,many original and improved intelligent algorithms was proposed to address 01 knapsack problem,for instance,chemical reaction optimization algorithm,genetic algorithm,particle swarm optimization algorithm,shuffled frog leaping algorithm,artificial bee colony algorithm,hill climbing algorithm and simulated annealing algorithm.This paper studied on many intelligent algorithms and 01 knapsack problems,and proposed greedy frog leaping algorithm (GFLA) to solve 01kp.Different from original shuffled frog leaping algorithm,GFLA always updates global best solution during each memeplex process,such that global exploration would employ the latest global best solution to expand the search space.In addition to traditional global exploration and local exploitation,aiming at 01kp,it proposed a greedy scheme at fitness computing stage,including drop and add two steps.At drop step,if the knapsack is over-weighted,then the item with minimum value density is removed from the knapsack and the solution is updated.At add step,if there is still space for the knapsack to load items,then items with minimum weight which have not been loaded are put into the knapsack and solution is also updated.Drop and add steps adopted in our work greatly improve greedy frog leaping algorithm’s ability to address 01kp.This paper conducted the experiments on benchmarks,and compared the results with chemical reaction optimization algorithm,genetic algorithm,quantum-inspired evolutionary algorithm,chemical reaction optimization with greedy strategy.All experimental results show that greedy frog leaping algorithm obtains the best solutions in all cases,which indicates that GFLA is an efficient algorithm to address 01 knapsack problem.

Key words: 01 knapsack problem, Frog leaping algorithm, Greedy scheme, Min-allocate, Value density