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

摘要：

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

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

所属期刊栏目：45

分类号：TP301(计算技术、计算机技术)

资助基金：国家高技术研究发展计划863 ,国家自然科学基金项目2015AA015305 ,61232003 , 61332003 ,61202121

在线出版日期：2018-08-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：73-77