改进修复策略遗传算法求解折扣{0-1}背包问题  

Improved repair strategy genetic algorithm solve discount {0-1} knapsack problem

作　　者：杨洋 潘大志[1] 贺毅朝 YANG Yang;PAN Dazhi;HE Yichao(School of Mathematics and Information,China West Normal University,Nanchong,Sichuan 637009,China;College of Information Engineering,Hebei Geological University,Shijiazhuang 050031,China)

机构地区：[1]西华师范大学数学与信息学院,四川南充637009 [2]河北地质大学信息工程学院,石家庄050031

出　　处：《计算机工程与应用》2018年第21期37-42,132,共7页Computer Engineering and Applications

基　　金：国家自然科学基金(No.11371015);四川省教育厅自然科学基金(No.18ZA0469);西华师范大学博士启动基金(No.12B022);西华师范大学校级科研团队(No.CXTD2015-4)

摘　　要：第一遗传算法(FirEGA)在求解折扣{0-1}背包问题(D{0-1}KP)过程中对非正常编码的修复未能较好运用物品折扣关系,影响修复效果,导致求解结果不理想。针对该问题,对FirEGA中的贪心修复与优化算法(GROA)进行修正:传统贪心修复按照价值密度对项进行选取,当出现同一项集中两个项均被选取时,文中不再选取价值密度较大项,而是选择价值较大项,得到处理非正常编码个体的新的贪心修复优化算法(NGROA)。在FirEGA中采用NGROA,构成求解D{0-1}KP新的第一遗传算法(NFirEGA)。最后,利用NFirEGA求解四类大规模D{0-1}KP问题,结果表明,NFirEGA在求解精度上明显优于FirEGA。The First Genetic Algorithm(FirEGA)in the Discount{0-1}Knapsack Problem(D{0-1}KP)on the non-normal coding individual repair failed to better use the discount relationship among items,affecting the repair results and leading to the results of the solution are not ideal.In order to solve this problem,this paper modifies the greedy and Optimization Algorithm(GROA)in FirEGA.Traditional greedy repairs select terms according to the value density.When two items of the same item set are selected,this paper no longer selects the larger value density item,but to choose a larger value item and gets a New Greedy Repair and Optimization Algorithm(NGROA)that deals with non-normal coding individuals.Adopting NGROA in FirEGA propose a New First Genetic Algorithm(NFirEGA)for solving D{0-1}KP.Finally,NFirEGA is used to solve four kinds of large-scale D{0-1}KP problems.The results show that NFirEGA is superior to FirEGA in solving precision.

关 键 词：折扣{0-1}背包问题 非正常编码个体 遗传算法 贪心策略 修复与优化 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]