求解多重二次背包问题的改进遗传算法

摘要

多重二次背包问题,旨在将具有单独价值与协作价值的对象分配到一组容量有限的背包中,使总利润最大化,是一种具有广泛应用的NP难组合优化问题。针对该问题提出一种引入自适应模式替换和贪心算法思想的改进遗传算法（IGA）。首先对初始种群进行自适应模式替换,使每代种群中的最好基因个体保存下来形成模式,替换原种群中质量较差的个体,通过设计贪婪算子改进贪心思想对问题进行排序,然后进行扰动交叉操作和双重选择变异操作,最后采用最大化修复策略以保证解的可行性。标准算例仿真结果表明,相比传统算法,IGA具有较强的寻优能力。