期刊专题

10.11896/j.issn.1002-137X.2018.07.011

求解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

暂无封面信息
查看本期封面目录

计算机科学

1002-137X

50-1075/TP

45

2018,45(7)

专业内容知识聚合服务平台

国家重点研发计划“现代服务业共性关键技术研发及应用示范”重点专项“4.8专业内容知识聚合服务技术研发与创新服务示范”

国家重点研发计划资助 课题编号:2019YFB1406304
National Key R&D Program of China Grant No. 2019YFB1406304

©天津万方数据有限公司 津ICP备20003920号-1

信息网络传播视听节目许可证 许可证号:0108284

网络出版服务许可证:(总)网出证(京)字096号

违法和不良信息举报电话:4000115888    举报邮箱:problem@wanfangdata.com.cn

举报专区:https://www.12377.cn/

客服邮箱:op@wanfangdata.com.cn