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

刘梦佳+向凤红+毛剑琳+郭宁

摘要：

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

关键词：多重二次背包问题；自适应模式替换；贪心算法；遗传算法；最大化修复策略

DOIDOI：10.11907/rjdk.171999

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2018）001004904

Abstract：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 NPhard 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 selfadaptive 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.

Key Words：quadratic multiple knapsack problem； selfadaptive replacement model； greedy algorithm； genetic algorithm； maximize repair strategies

0概述

多重二次背包問题（Quadratic Multiple Knapsack Problem，QMKP）是二次背包问题（Quadratic Knapsack Problem，QKP）与多重背包问题（Multiple Knapsack Problem， MKP）两个经典NP难题融合后的一个新问题，由Hiley和Julstrom[1]于2006年提出。目前，QMKP广泛应用于金融、库存管理、生产计划调度、机场车站布局、密码设计、通讯基站优化、集成电路设计等方面，在最近几年也得到了学者的广泛关注[2]。现有两种求解方法为精确方法和启发式方法。较具代表性的精确算法有2012年Quadri等[3]提出的分支定界精确算法及Wang等[4]提出的具有线性表示的分支定界法，精确算法都只能求解小规模QMKP，难以满足实际需求，所以启发式法通常用于在合理的计算时间内找到多重二次背包的近似解[5]。……