求解01背包问题的贪婪蛙跳算法

Greedy Frog Leaping Algorithm for 01 Knapsack Problem

01背包问题是经典的组合优化问题,被广泛应用于生活中的多个领域,如货物装载、预算控制、资源分配和资产管理等。因此,长期以来许多科学家在该领域不断钻研,并取得了丰硕的成果。尽管01背包问题已被研究多年,但由于该问题已被证明为NP完全问题,因此找到最优解并不容易。近年来,大量的智能算法不断被提出并被用来求解01背包问题,如化学反应优化算法、遗传算法、粒子群算法、蛙跳算法、人工蜂群算法、爬山算法和模拟退火算法等。通过对智能算法和01背包问题的探索,文中提出了贪婪蛙跳算法(GFLA)来解决01背包问题。不同于传统的蛙跳算法,GFLA总会在每次模因搜索过程中更新全局最优解,以便在接下来的全局搜索过程使用最新的全局最优解进行搜索,从而扩大解的搜索空间。除了蛙跳算法这类传统的局部搜索和全局搜索策略之外,针对01背包问题,在计算适应度值的阶段,本工作提出了贪心策略并分别将其应用于drop和add两个步骤。在drop阶段,若背包超重,则将其中价值密度最小的物品移出并更新解决方案。在add阶段,若背包还有承载物品的能力,则将未放入背包的重量最小的物品放入背包,并对背包信息进行更新。这样,便大大提高了利用蛙跳算法来求解01背包问题的能力。将贪婪蛙跳算法与蜂群算法、化学反应优化算法、遗传算法和量子演化算法进行对比,结果显示,贪婪蛙跳算法取得了最好的结果,从而表明了该算法是求解01背包问题的有效算法。

01 knapsack problem（01 kp）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 01 kp 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 01 kp.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 01 kp,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 01 kp.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.