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

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

第一遗传算法(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.