改进的遗传蚁群混合算法求解多维0/1背包问题

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

(昆明理工大学 信息工程与自动化学院，云南 昆明 650500)

多维背包问题(Multidimensional Knapsack Problem，MKP)又名多约束背包问题，是著名的整数规划问题之一。在实际应用中，许多问题都可以用多维背包问题来描述，如材料切割、资源分配、货物装载、投资决策等[1]。在近几十年里世界上许多研究机构和个人对它做了大量的研究，已有的求解方法可分为精确方法(如分支定界法、回溯法、动态规划法等[2])，近似算法(如贪婪法、拉格朗日法、蚁群优化算法[3-5]、粒子群算法[6]、遗传算法[7]、布谷鸟算法[8]等)以及混合算法3大类。

遗传算法[7]是受生物进化启发发展起来的一种智能优化算法，它模拟生命进化机制，即模拟自然选择和遗传进化中发生的繁殖、交配和突变现象，从任意一个初始种群出发，通过选择、交叉和变异操作，产生一群新的更适应环境的个体，一代代不断繁殖、进化，最后收敛到最适应环境的个体上，求得问题的最优解。遗传算法具有较强的全局搜索能力，但收敛速度较慢，求解精度不高。蚁群算法[9]求解多维背包问题时，每只蚂蚁主要根据积累在物品上的信息素量的大小来依次选择是否生产该物品，被蚂蚁选择的物品就是要消耗资源所生产的物品。在蚁群算法进行过程中，信息素正反馈的思想使其能较快收敛到局部最优解，但其全局搜索能力较低，易陷入局部最优，产生早熟现象。近年来，遗传蚁群混合算法得以快速发展，涌现出多种混合方式[10-13]。

本文针对原有的遗传蚁群混合算法求解精度低、收敛速度慢等缺陷，设计了一种改进的遗传蚁群混合算法，对传统遗传算法的交叉和变异算子进行了改进，并在蚁群算法的运行过程中引入了概率和为u的轮盘赌方式、禁忌表交换策略以及信息素的混沌更新策略。实验结果表明该算法在搜索能力和收敛速度方面都有明显提高。

1 多维背包问题

具有多类资源限制的背包问题，如投资决策问题中受到资金、人力、原材料等多维约束的限制，即多维背包问题(MKP)[14]。多维背包问题可描述为：给定n个价值为Pj(j=1,2,…,n)的物品，m种有限数量的资源约束ci(i=1,2,…,m),物品j对资源i的消耗为wij(i=1,2,…,m;j=1,2,…,n)；从n个物品中选出一组满足所有资源约束的物品组合使得所选物品价值总和最大。数学模型为

(1)

2 改进遗传蚁群混合算法求解

鉴于遗传算法可通过交叉操作、变异操作产生新的个体增强种群多样性，提高算法的全局搜索能力，蚁群算法可增强寻优精度。在此挑选d只较优蚂蚁进行遗传算法寻优，并利用该寻优结果对蚁群进行全局信息素更新，引导蚂蚁向最优方向寻优。其它蚂蚁进行蚁群算法寻优，并利用其寻优结果对蚁群进行信息素的局部更新，对下一个蚂蚁寻优的方向进行指引。算法可具体描述为：每次进行迭代时，蚂蚁总数目为size，选择d(d=size/4)只较优蚂蚁进行遗传算法寻优，该寻优过程结束后进行信息素的全局更新，其余的蚂蚁进行蚁群算法寻优，此寻优过程结束后进行局部信息素的更新。每一代整体寻优过程结束后，将当代size只蚂蚁寻觅到的解和前一代的d个较优解进行混合降序排列，选取排序后的前d只蚂蚁作为下一次迭代时进行遗传算法的初始种群。

2.1 算法流程

步骤1初始化，设置最大迭代次数Gmax，交叉概率Pc，变异概率Pm，种群大小size；

步骤2随机生成初始种群P(d,n)，并按适应值进行降序排列；

步骤3对d只蚂蚁采用遗传算法寻优。

(1)复制P(A=P)；

(2)按个体适应度选择两个解，通过交叉操作对P产生新的解；

(3)每条染色体以概率Pm对P进行变异操作；

(4)对种群进行最大化利率修复策略；

(5)进行信息素的全局更新；

步骤4对size-d只蚂蚁进行蚁群算法寻优。

(1)参数初始化。令时间t=0，候选物品序号集allowed=[1:n]，蚂蚁个体禁忌表tabuk=0,信息素量τj(t)=1,信息挥发素ρ=0.7；

(2)生成B=zeros((size-d),n)，将各蚂蚁的初始出发点设在当前解集中，蚂蚁的禁忌表指针k=1；

(3)对于size-d只蚂蚁。

②每只蚂蚁独立寻得一个解，令临时向量temp(j)=Pj(1≤j≤n)。蚂蚁k按物品被选择的概率以概率之和为u的轮盘赌方法选择下一个物品j+1，然后令u=u-temp(j+1),temp(j+1)=0。若选择物品j未超出所需消耗资源的限制，则xkj=1, 转步骤4-(3)-③；否则xkj=0，j=j+1。若j

③将所选生产物品序号加入到tabuk中，修改禁忌表指针。

(4)采用禁忌表交换策略；

(5)对局部信息素进行更新；

(6)若k

步骤5对蚁群B、P、A按适应值降序排列，选择前d只蚂蚁组成P；

步骤6保留当代最优个体；

步骤7判断g>Gmax是否成立，若成立则循环结束输出最优结果；否则清空禁忌表，令Δτj=0，g=g+1,转步骤3；

步骤8若G

步骤9g=g+1，判断g>Gmax是否成立，若否，重复步骤3～步骤8；若是，输出最优解，结束程序。

2.2 算法具体策略

(1)交叉操作。采用均匀交叉法，父代利用掩码进行交叉，采用“优、优交叉”和“差、差交叉”策略可以有效地保持群体的多样性，使算法具有较强的搜索能力。交叉规则：掩码为1表示父代A为子代提供变量值，掩码为0表示父代B为子代提供变量值；

(2)变异操作。变异个体根据变异概率Pm随机产生，变异基因位个数随机生成，所需变异个体的每个基因位变异的概率由当前种群中所有个体相同基因位上1和0所占比例之差的绝对值(在此定义为Ca)决定，Ca越大该基因位进行变异的概率越小，反之Ca越小该基因位进行变异的概率就越大。例如：1010，1011，1101，1100，1110，0011，各基因位上Ca值分别为Ca1=2/3,Ca2=0,Ca3=1/3,Ca4=0,Ca2=Ca4

(3)最大化利率修复策略。搜索出不满足资源消耗上限的解，对于该选择策略下被放入的物品，按价值密度升序排列的先后次序依次删除物品(即令相应物品对应的xj=0)；对xj=0的物品按价值密度降序排列的先后次序依次选择具有最大剩余的那一维资源，直到所消耗资源达到约束上限为止；

(4)轮盘赌法路径选择策略。为增加蚁群搜索的随机性，本文提出根据概率和为u的轮盘赌方式选择物品。蚁群算法在求解多维背包问题时，每一个物品相当于一个有信息素累积的信息单位，蚂蚁k根据选择概率对下一个物品进行选择，由于选择操作只涉及到概率比较问题，为减少计算量，将选择概率的公式定义为

(2)

此时选择概率之和不为1，在此设为u。其中τj(t)为随时间不断更新的信息素量，α为信息素启发因子，Sk(t)为第k只蚂蚁在t时刻已选择的物品序号集，启发函数ηj表示选择物品j的期望程度，β为期望启发式因子。

信息素量

τj(t+1)=(1-ρ)·τj(t)+Δτj(t)

(3)

信息素量挥发系数ρ表示信息素量τj(t)随时间的变化而衰减的程度。1-ρ为信息素残留因子。信息素增量Δτj(t)为t时刻蚂蚁选择物品j并留在该物品上的信息素，Δτj(t)∈[0,1]。

(4)

其中

(5)

信息素强度

(6)

fk为本次迭代中第k只蚂蚁所寻解的适应度值，即蚂蚁k所选物品的总价值。上文中的步骤4-(5)是按照式(3)～式(5)进行的信息素局部更新。

(5)禁忌表交换策略。本文采用禁忌启发式局部优化算法，在满足各维资源约束的条件下，将禁忌表中所选物品的序号与非禁忌表的物品序号进行交换。在扩大搜索范围的同时，避免陷入局部最优。步骤4-(4)的禁忌表交换策略具体操作如下：

①计算本次迭代中的最优解fk；

②在禁忌表中任意选出某个物品序号i，再选出一个非禁忌表中的物品序号j；

(6)信息素的混沌更新策略。混沌是非线性确定系统产生的外在复杂表现，具有对初始条件的敏感性、伪随机性、遍历性、混合性、规律性和不可预测性等优点[15]。利用混沌变量进行优化能够跳出局部最优，但在寻优过程中进行盲目搜索的次数较多，耗时长。鉴于此，本文引入混沌更新策略在较大范围内充分发挥混沌更新的全局搜索优势，增强种群多样性。同时利用信息素正反馈思想指导混沌搜索的区域和方向，克服混沌搜索的盲目性。

步骤8的具体步骤为：当判断出种群出现局部收敛时，将所选物品按适应值升序排列，并将物品上的信息素引入混沌更新策略，改变种群的搜索方向。本文将Logistic映射公式定义为

(7)

3 算例及结果分析

为验证算法的有效性，本文采用Matlab编码实现算法程序，并将本文改进的遗传蚁群混合算法与文献[10]和文献[12]中的遗传蚁群混合算法进行了对比。测试算例来源于http://elib.zib.de/pub/Packages/mp-testdata/ip/sac94-suite/index.html中规模为10～28的多维背包问题。其中，蚂蚁数size=200，最大迭代次数Gmax=200，交叉概率取Pc=0.8，变异概率取Pm=0.15，信息素启发因子α=2，期望启发式因子β=1，信息素量挥发系数ρ=0.7。

现将3种算法(算法1是本文的改进算法，算法2采用文献[10]的混合算法，算法3采用文献[12]的混合算法)在此问题上各运行50次的解性能进行比较，结果如表1、表2和图1所示。

表1 3种算法最优解对比结果

表2 3种算法50次达到最优解所运行迭代次数

由表1可知，3种算法均可以在有限的迭代次数中达到最优，其中算法1的平均波动率最小(平均波动率=(最优值-平均最优值)/最优值)，且算法1求得的平均最优值比算法2、算法3更接近最优值，说明算法1在解决多维背包问题时寻优能力有所提高。从表2看，算法1在50次寻优过程中达到最优解时的最短、最长、平均迭代次数均为最小，表明该算法的收敛性能要优于其它两种算法。由图1可看出算法1在40多代时已趋于收敛，而算法2和算法3分别在100多代和60多代时才达到最优，由此可见本文算法的收敛性和搜索能力明显有所提高。

图1 3种算法进化曲线图

4 结束语

本文设计了一种改进的遗传蚁群混合算法，对传统遗传算法的交叉和变异算子进行了改进，以提高寻优性能。并在蚁群算法的运行过程中引入概率和为u的轮盘赌方式降低算法复杂度，采用禁忌表交换策略以及信息素的混沌更新策略避免陷入局部最优，增强了种群多样性。通过对测试用例的仿真，证明本文提出的改进混合算法在求解多维背包问题时，算法的寻优性能、求解精度、收敛性得到了大幅改善。目前，本文只研究了待选物品数较少的情况，今后将对大规模及其他背包问题进行深入研究。