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

An Improved Genetic Algorithm for the Quadratic Multiple Knapsack Problem

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

The quadratic multiple knapsack problem （QMKP） consists in assigning objects with both individual and pairwise profits to a set of limited knapsacks in order to maximize the total profit. QMKP is a NP-hard combinatorial optimization problem with a number of applications. To solve the problem, an improved genetic algorithm （IGA） introduced adaptive model of replacement and greedy algorithm is proposed. First, the algorithm used self-adaptive model of replacement to initial population so that made the best gene from each generation population individuals survived and formed model to replace the poor quality individuals of the original population. Then sorted the problem by changing the greedy thought through designing greedy operator. After that performed the disturbance cross operation and double selection mutation operation. Finally, to ensure the feasibility of the solution by using maximized repair strategy. In the numerical computation results on standard quadratic multiple knapsack problem instances,the IGA has stronger optimizing capacity than the traditional algorithms.