背包问题(knapsack problem,简称KP)^[1-3]是一类重要的组合优化问题,在工业、经济、金融与计算机领域的资源分配、资金预算、投资决策、装载问题、整数规划、分布式系统以及信息安全领域的公钥密码系统构建中具有重要的理论和应用价值.KP是一类NP难问题,当规模较大时,经典方法(如动态规划)因时间复杂度很高导致实用性较差,因此,利用现代启发式算法求解KP越来越受到重视;演化算法(evolutionary algorithms,简称EAs)作为一种通用启发式算法已被用于KP问题的求解研究,而且对不同KP已给出了许多有效的求解方法.最早的0-1背包问题(0-1 knapsack problem,简称0-1 KP)出现在文献^[4],而Dantzig^[5]对0-1 KP的开创性研究工作对后来KP的推广起到了关键性作用.目前,KP问题包括多种不同形式^{[1, 3]},经典的有0-1 KP、有界背包问题(bounded knapsack problem,简称BKP)、无界背包问题(unbounded knapsack problem,简称UKP)、多维背包问题(multidimensional knapsack problem,简称MDKP)、多背包问题(multiple knapsack problem,简称MKP)、多选择背包问题(multiple-choice knapsack problem,简称MCKP)、二次背包问题(quadratic knapsack problem,简称QKP)、最大最小背包问题(max-min knapsack problem,简称MmKP)、优先约束背包问题(precedence constraint knapsack problem,简称PCKP)、集合联盟背包问题(set-union knapsack problem,简称SUKP)、多目标背包问题(multi-objective knapsack problem,简称MOKP)和在线背包问题(on-line knapsack problem,简称OLKP)等以及它们的变形.近年来,许多新的KP问题,如随机时变背包问题(randomized time-varying knapsack problem,简称RTVKP)^[6-8]、多重二次背包问题(quadratic multiple knapsack problem,简称QMKP)^{[9, 10]}、多选择多维背包问题(multiple-choice multidimensional knapsack problem,简称MMKP)^{[11, 12]}和折扣0-1背包问题(discounted {0-1} knapsack problems,简称D{0-1}KP)^[13-15]等被相继提出,不仅壮大了KP家族,而且大大拓宽了KP的应用领域.

求解KP的算法一般分为两类:一类是精确算法^{[16, 17]},如动态规划、回溯法和分支限界法等;另一类是非精确算法^[18-24],主要有随机算法、近似算法、生物算法和演化算法(EAs)等.由于KP是NP难问题,精确算法的时间复杂度或是伪多项式时间的,或是指数时间的,一般不适用于复杂大规模KP实例的求解,所以在实际应用中非精确算法更受青睐.EAs是一类特殊的随机近似算法,它既不需要计算目标函数的导数和梯度,也不要求目标函数具有连续性,而且具有内在的隐含并行性和全局寻优能力.目前,人们模仿自然界中生物的群体行为,或者受社会实践中某些社会活动的启发,提出了许多有效的EAs,如遗传算法(genetic algorithm,简称GA)^{[25, 26]}、粒子群优化(particle swarm optimization,简称PSO)^[27]、蚁群优化(ant colony optimization,简称ACO)^[28]、差分演化(differential evolution,简称DE)^[29]、人工鱼群算法(artificial fish swarm,简称AFS)^[30]、人工蜂群算法(artificial bee colony,简称ABC)^[31]、和声搜索算法(harmony search algorithm,简称HSA)^[32]、混合蛙跳算法(shuffled frog leaping algorithm,简称SFLA)^[33]和人工免疫算法(artificial immune system,简称AIS)^[34]等,并已被成功用于求解各种组合优化问题(如KP问题、旅行商问题、集合覆盖问题等),取得了许多有益的研究成果.

本文对近10余年来利用EAs求解KP的研究情况作一个较为详细的总结,第1节介绍有效求解0-1 KP的各种EAs,总结处理0-1 KP不可行解的3种常用方法.第2节简述求解MDKP的多种EAs,介绍处理MDKP不可行解的一种有效方法.第3节总结目前已用于求解MKP的EAs,对个体的两种常用编码方法进行简单对比.第4节介绍利用EAs求解QKP与QMKP的有效算法和处理不可行解的常用方法.第5节介绍利用EAs求解RTVKP,D{0-1}KP,MMKP和MOKP等的研究进展情况.最后分析利用EAs求解KP的研究现状与存在的不足,给出今后有待研究的若干问题与研究思路.

1 求解0-1 KP的EAs总结与分析

0-1 KP是最基本的KP问题,也是一个NP难问题^[2].0-1 KP的一般描述为:从若干个具有价值与重量的项中选择一些装入一个具有载重限制的背包中,如何才能使装入背包中各项的重量之和不超过背包载重且价值之和达到最大?

设项j(1≤j≤n)的价值与重量分别为p_j与w_j,C为背包的载重,其中,p_j,w_j与C均为正整数.令Y=[y₁,y₂,…,y_n]∈ {0,1}ⁿ表示0-1 KP的一个可行解,当项j被装入背包时y_j=1,否则,y_j=0.于是,0-1 KP的数学模型为

$\text{Max}f(Y)=\text{Max}\sum\nolimits_{j=1}^{n}{{{p}_{j}}{{y}_{j}}}$

(1)

$\text{s}\text{.t}\text{. }\sum\nolimits_{j=1}^{n}{{{w}_{j}}{{y}_{j}}}\le C$

(2)

任意一个0-1向量只是0-1 KP的一个潜在解,只有当它满足公式(2)的约束时才是一个可行解,否则就是一个不可行解.

Michalewicz^[35]首先研究了利用GA求解0-1 KP时个体编码方法的优劣以及处理0-1 KP不可行解的罚函数法与修复法,指出:GA的个体采用0-1向量编码比自然数编码的效果更佳,而且利用修复法处理0-1 KP不可行解比罚函数法的结果更好.此后,人们在利用EAs求解0-1 KP时一般均采用0-1向量的编码方法.文献^[36]研究了GA的交叉算子与探索子空间的关系,构造出一种启发式交叉算子,由此提出了一个改进的GA,并用于求解0-1 KP.张铃和张钹^[37]利用数论中的佳点集理论与方法,通过对GA的交叉操作进行重新设计,提出了一个新的GA,称为佳点集遗传算法(good point set based genetic algorithm,简称GGA),并利用GGA有效求解0-1 KP等组合优化问题.Lim等人^[38]则利用一夫一妻制(monogamous pairs)改进GA产生子代个体的方法,并基于罚函数法计算个体的适应度,给出了求解0-1 KP的一种新的GA算法:MopGA.

除GA以外,人们还研究了如何利用PSO,ACO,HAS,DE和SFLA等求解0-1 KP问题.文献^[39]通过修改BPSO^[40]中位置更新方程的边界限制,给出了一种改进的二进制粒子群优化算法MBPSO,并利用MBPSO求解0-1 KP问题.文献^[41]基于ACO并采用0-1向量编码方式求解0-1 KP.首先用梯形模糊函数对0-1KP做适当的变形,然后在ACO中引入交叉与变异操作,由此给出了利用ACO求解0-1 KP的一种可行方法.文献^[42]提出了一种具有双重编码的二进制差分演化算法HBDE,并使用修复法处理不可行解,给出了利用DE求解0-1 KP的一种有效方法.文献^{[43, 44]}分别提出了两种不同的HSA算法,并被成功用于求解0-1 KP问题.文献^[45]将量子编码与社会进化算法相结合,提出了一种求解0-1 KP的量子编码社会进化算法.文献^[46]提出了一种具有变异操作的SFLA算法,并用于求解0-1 KP.文献^[47]提出了一种二进制猴群算法,并利用修复法处理不可行解,给出了求解0-1 KP的一种有效方法.

由上述研究可以看出:利用EAs求解0-1 KP的方法是非常成功的,所给出的算法均能求得0-1 KP实例的一个很好的近似解,甚至求得最优解.从求解速度与求解结果来看,它们与0-1 KP的完全多项式时间近似方案(fully polynomial time approximation scheme,简称FPTAS)^{[18, 20, 21]}比较接近;从实现的难易程度来看,它们比FPTAS更容易实现.

按照个体编码的表示方法,求解0-1 KP的EAs分为两类:一类是个体编码表示0-1 KP的一个潜在解的EAs^{[35-39, 45, 47]},在此类EAs中,个体用0-1向量表示,每个个体为0-1 KP的一个潜在解或可行解;另一类是个体编码不为0-1 KP潜在解的EAs^{[42-44, 46]},其特点是个体用一个实向量表示,并利用映射将实向量映射到一个0-1向量以获得0-1 KP的潜在解.

由于0-1 KP是约束优化问题,利用EAs求解时会产生不可行解,如何合理地评价非正常编码个体(即,对应潜在解不为可行解的个体)的优劣,是求解的一个关键问题.当前,处理此问题的方法主要有3种:罚函数法^{[35, 43]}、修复法^[35]和修复与优化法^{[7, 8]}.它们的一般原理概述如下.

· 罚函数法

罚函数法用一个适当的惩罚项对不可行解的目标函数值进行适度“惩罚”,从而给出对应个体的一种相对合理的评价.罚函数法有许多不同的实现方法,下面给出最常见的3种形式^{[35, 43]}.

(1) $Fit(Y)=\sum\nolimits_{j=1}^{n}{{{p}_{j}}{{y}_{j}}}-{{\log }_{2}}(1+\text{Max}\{\alpha (\sum\nolimits_{j=1}^{n}{{{w}_{j}}{{y}_{j}}}-C),0\});$

(2) $Fit(Y)=\sum\nolimits_{j=1}^{n}{{{p}_{j}}{{y}_{j}}}-\text{Max}\{\beta (\sum\nolimits_{j=1}^{n}{{{w}_{j}}{{y}_{j}}-C}),0\};$

(3) $Fit(Y)=\left\{ \begin{array}{*{35}{l}} \sum\nolimits_{j=1}^{n}{{{p}_{j}}{{y}_{j}}-\gamma {{(\sum\nolimits_{j=1}^{n}{{{w}_{j}}{{y}_{j}}-C})}^{2}}},\text{ }如果\sum\nolimits_{j=1}^{n}{{{w}_{j}}{{y}_{j}}>C} \\ \sum\nolimits_{j=1}^{n}{{{p}_{j}}{{y}_{j}}},\text{ }否则 \\ \end{array} \right..$

其中,Y=[y₁,y₂,…,y_n]∈{0,1}ⁿ是0-1 KP的一个潜在解,Fit(Y)为Y所对应个体的适应度;a,b,g为惩罚系数,它们的取值一般为Max{p_j/w_j|j=1,2,…,n}的某个正常数倍.

· 修复法

修复法是通过将不可行解对应的装填方案中价值密度${{{p}_{j}}}/{{{w}_{j}}}\;$小的项从背包中一一去掉,以保证装入背包中所有项的重量之和不超过背包载重,即,将不可行解修复为可行解.根据对背包中项的价值密度${{{p}_{j}}}/{{{w}_{j}}}\;$大小的考虑次序,修复法有两种实现方法^[35],我们按照价值密度${{{p}_{j}}}/{{{w}_{j}}}\;$由小到大进行的修复法称为第一修复法(记为fGRA),按相反次序进行的修复法称为第二修复法(记为sGRA),它们的伪代码描述见下.

将0-1 KP的n个项按照${{{p}_{j}}}/{{{w}_{j}}}\;$由大到小的次序排序,并根据这一顺序将各项原来的序号存入数组H[1,…,n]中.设Y=[y₁,y₂,…,y_n]∈{0,1}ⁿ为0-1 KP的一个潜在解,于是有下面的算法1和算法2.

算法1. fGRA^[35].

(1) $R\leftarrow \sum\nolimits_{j=1}^{n}{{{w}_{j}}{{y}_{j}}}$and j←n;

(2) while (R>C) do

(3) if (y_H[j]=1) then y_H[j]←0 and R←R-w_H[j];

(4) j←j-1;

(5) end while

算法2. sGRA^[7].

(1) if $\sum\nolimits_{j=1}^{n}{{{w}_{j}}{{y}_{j}}}\le C$ then return

(2) R←0;

(3) for j←1 to n do

(4) if (y_H[j]=1) and (R+w_H[j]>C) then y_H[j]←0 else R←R+w_H[j];

(5) end for

· 修复与优化法

修复与优化法是针对于所有潜在解的一种处理方法,它首先将其中的不可行解修复为可行解,然后对所有的可行解进行优化处理.在优化处理时,所采用的方法是将未被装入背包且将之装入不会导致超载的、具有最大价值密度的项尽可能地装入背包中,以此提高可行解的质量(目标函数值).以下记修复与优化法为GROA^[7],则其算法伪代码描述如下所示.

算法3. GROA.

(1) if $\sum\nolimits_{j=1}^{n}{{{w}_{j}}{{y}_{j}}}>C$ then Y←fGRA(Y) or Y←sGRA(Y);

(2) $R\leftarrow \sum\nolimits_{j=1}^{n}{{{w}_{j}}{{y}_{j}}};$

(3) for j←1 to n do

(4) if (y_H[j]=0) and (R+w_H[j]≤C) then y_H[j]←1 and R←R+w_H[j];

(5) end for

在利用修复法或修复与优化法处理不可行解时,由于所有不可行解Y均被修复为可行解,个体的适应度定义为f(Y)是一种显而易见的简单方法.需要注意的是:在EAs生成初始种群之前,只需对0-1 KP实例中所有的项按价值密度${{{p}_{j}}}/{{{w}_{j}}}\;$由大到小的次序进行一次排序并存储排序后各项的下标即可.事实上,下面对于其他KP不可行解的处理与0-1 KP是相类似的.

2 利用EAs求解MDKP的研究综述

MDKP^{[1, 3]}是0-1 KP的一个扩展形式,也是一个NP难问题,在预算规划、项目日程安排、计算机中处理器的分配和分布式计算机系统中的数据库等方面具有重要的应用.MDKP的数学模型为

$\text{Max}f(Y)=\text{Max}\sum\nolimits_{j=1}^{n}{{{p}_{j}}{{y}_{j}}}$

(3)

$\text{s}\text{.t}\text{. }\sum\nolimits_{j=1}^{n}{{{w}_{ij}}{{y}_{j}}}\le {{C}_{i}},i=1,2,...,d$

(4)

${{y}_{j}}\hat{I}\left\{ 0,1 \right\},j=1,2,\ldots ,n$

(5)

其中,p_j是项j的价值,w_ij(i=1,2,…,d)是项j的d个重量限制;p_j,w_ij和C_i均为正整数,并且满足w_ij≤C_i,$\sum\nolimits_{j=1}^{n}{{{w}_{ij}}}>{{C}_{i}}$,i=1,2,…,d,j=1,2,…,n;y_i=1当且仅当项j被装入背包.显然,0-1 KP是d=1时MDKP的特例,因此,MDKP的求解难度比0-1 KP更大.MDKP的Benchmark请参考文献^[48].

作为经典EAs,GA最早被用于求解MDKP问题的研究.Chu和Beasley^[48]研究了如何利用GA有效求解MDKP,他们提出的修复与优化法已成为利用EAs求解MDKP时处理不可行解的一种最常用的方法.文献^[49]在利用GA求解MDKP时,个体采用自然数编码方式,并通过一种有效的解码方法来避免不可行解的产生.文献^[50]基于Tchebycheff标量化函数提出了一种多目标遗传算法MOTGA,并使用文献^[48]中的方法处理不可行解,给出了求解MDKP的一种有效方法.文献^[51]提出了一种混合GA求解MDKP,并使用罚函数法处理不可行解.文献^{[52, 53]}采用与文献^[48]类似的方法处理不可行解,分别基于改进的GA给出了求解MDKP的两种有效方法.

除了利用GA求解MDKP以外,人们还利用其他EAs提出了求解MDKP的许多有效方法.如:文献^[54-57]分别基于不同策略提出了多个改进的二进制PSO,并利用它们求解MDKP;文献^[58]提出了一种二进制DE算法,用于求解MDKP问题;文献^[59]给出了求解MDKP的一种二进制差分搜索算法(binary differential search algorithm,简称BDS);文献^[60-62]分别提出了改进的HSA算法,给出了利用HSA求解MDKP的3种不同的方法;文献^[63]提出了一种求解MDKP的人类学习优化(human learning optimization,简称HLO)算法;文献^[64]基于引导素更新和扩散机制提出了一种改进的ABC算法,给出了求解MDKP的一种有效方法;文献^[65]基于萤火虫算法(firefly algorithm,简称FFA),提出了求解MDKP的一种可行方法;最近,文献^[66]提出了一种二进制人工藻算法(binary artificial algae algorithm,简称BAAA),并被成功用于求解MDKP问题.

上述求解MDKP的EAs几乎均采用0-1向量的编码形式,求解的关键是如何处理算法产生的不可行解.显然,除文献^[51]外都是用修复与优化方法处理不可行解的,这表明,在利用EAs求解MDKP时,修复与优化方法比罚函数法的处理效果更佳.为此,下面主要讨论修复与优化法,限于篇幅,仅给出文献^[48]中的经典方法(记为dGROA)的算法伪代码描述,其他请参考相关文献.

设MDKP的代理松弛问题^[48]为

$\text{Max}\sum\nolimits_{j=1}^{n}{{{p}_{j}}{{y}_{j}}}$

(6)

$\text{s}\text{.t}\text{. }\sum\nolimits_{j=1}^{n}{(\sum\nolimits_{i=1}^{d}{{{r}_{i}}{{w}_{ij}}}){{y}_{j}}}\le \sum\nolimits_{i=1}^{d}{{{r}_{i}}{{C}_{i}}}$

(7)

${{y}_{j}}\in \left\{ 0,1 \right\},j=1,2,\ldots ,n$

(8)

其中,r={r₁,r₂,...,r_d},r_i是正实数,称为代理乘子(surrogate multiplier),i=1,2,…,d.

设Y=[y₁,y₂,…,y_n]∈{0,1}ⁿ为MDKP实例的一个潜在解,将实例中的n个项按${{{p}_{j}}}/{\sum\nolimits_{i=1}^{d}{{{r}_{i}}{{w}_{ij}}}}\;$由大到小的顺序排序,并根据这一次序将各项序号依次存入数组H[1,…,n]中.令I={1,2,…,d},则算法dGROA的伪代码描述如下.

算法4. dGROA^[48].

(1) ${{R}_{i}}\leftarrow \sum\nolimits_{j=1}^{n}{{{w}_{ij}}{{y}_{j}}},\forall i\in I;$

(2) for j←n downto 1 do

(3) if (y_H[j]=1) and (R_i>C_i,∃i∈I) then

(4) y_H[j]←0; R_i←R_i-w_i,H[j],∀i∈I;

(5) end if

(6) end for

(7) for j←1 to n do

(8) if (y_H[j]=0) and (R_i+w_i,H[j]≤C_i,∀i∈I) then

(9) y_H[j]←1; R_i←R_i+w_i,H[j],∀i∈I;

(10) end if

(11) end for

研究表明:ACO是一种高效的仿生智能算法,非常适于求解组合优化问题.因此,许多学者对如何利用ACO求解MDKP进行了研究,给出了多种有效方法:文献^[67]定义了新的选择概率规则和基于背包项的一种序的启发式信息,提出了一种求解MDKP的改进ACO算法;文献^[68]则利用改进的超立方体结构提出了一种新的二进制ACO算法,并用于求解MDKP;文献^[69]基于变异和信息素扩散的融合机制提出了一种改进的ACO算法,可有效求解MDKP;文献^[70]将拉格朗日启发式策略与ACO相结合,给出了求解MDKP的一种有效方法.

由以上研究可以看出:利用ACO求解MDKP的关键问题是如何将其表示为一个有向图或无图,并通过蚂蚁的随机行走来获得问题的可行解.显然,有效的信息素更新与扩散机制以及顶点的合理选择方法,对利用ACO高效求解MDKP是非常重要的.

3 利用EAs求解MKP的研究现状

MKP^{[1, 71]}在投资决策和多装载问题中具有典型的应用,它的一般描述为:给定n个项和m个背包,其中,项j的价值为p_j,重量为w_j,第i个背包的载重为C_i;p_j,w_j和C_i均为正整数,i=1,2,…,m,j=1,2,…,n,每个项最多只能装入一个背包中.如何选择项装入背包,使得每个背包中装入项的重量之和在不超过背包载重的前提下所有背包中装入项的价值之和最大?MKP的数学模型表示如下:

$\text{Max}f(Y)=\text{Max}\sum\nolimits_{i=1}^{m}{\sum\nolimits_{j=1}^{n}{{{p}_{j}}{{y}_{ij}}}}$

(9)

$\text{s}\text{.t}\text{. }\sum\nolimits_{j=1}^{n}{{{w}_{j}}{{y}_{ij}}}\le {{C}_{i}},i=1,2,...,m$

(10)

$\sum\nolimits_{i=1}^{m}{{{y}_{ij}}}\le 1,j=1,2,...,n$

(11)

${{y}_{i}}_{j}\in \left\{ 0,1 \right\},i=1,2,\ldots ,m,j=1,2,\ldots ,n$

(12)

其中,y_ij=1表示项j被装入了背包i中,y_ij=0表示项j不装入背包i中.显然,m=1时,MKP退化为0-1 KP.不失一般性,以下总是假设m≥2,w_j≤Max_1≤i≤m{C_i},j=1,2,…,n;C_i≥Min_1≤j≤n{w_j},i=1,2,…,m;$\sum\nolimits_{j=1}^{n}{{{w}_{j}}}>\text{Mi}{{\text{n}}_{1\le i\le m}}\{{{C}_{i}}\}.$

由于MKP是一个强NP难问题,不存在FPTAS.为了获得求解MKP的有效近似算法,人们探讨利用EAs求解MKP的可行方法,初步取得了一些研究成果.文献^[72]提出了利用群遗传算法(grouping genetic algorithm,简称GGA)求解MKP的方法,计算结果表明:对项的价值与重量高度相关的难MKP实例,GGA比已有某些启发式方法的求解效果更佳.为了实现粒子位置的整数向量编码表示,文献^[73]重新设计了PSO的速度与位置更新方程,提出了一种新的离散PSO算法——DPSO,并利用DPSO给出了一种求解MKP的可行方法.文献^{[74, 75]}分别基于整数编码方法,利用AFS求解MKP问题,探讨了利用AFS求解MKP的可行性与有效性.文献^[76]则利用GA求解MKP,其中,个体采用0-1矩阵的表示方法,并基于罚函数法定义个体适应度,给出了一种求解MKP的可行方法.可以看出:目前,用于求解MKP的EAs仅限于GA,PSO和AFS,而且个体编码主要是0-1矩阵和整数向量两种基本方法.虽然利用0-1矩阵方法与MKP的数学模型(即公式(9)~公式(12))中可行解的表示是一致的,但由约束条件(11)不难看出:这样的0-1矩阵必然是一个稀疏矩阵,这个苛刻的限制条件必然会降低算法的求解效率.另一方面,利用整数向量的编码方法虽然简单且容易转化为0-1矩阵形式,但是此编码方法不利于EAs的进化操作,即,不容易设计出针对此编码的高效进化算子.文献^[72]中给出的个体编码方法本质上是一种集值编码方法,虽然略显繁琐,但值得借鉴.此外,对于整数向量编码方法,可以尝试利用量子编码设计进化算子.

由于MKP是一个约束优化问题,在利用EAs求解MKP时也会产生不可行解,除非采用特殊的编码方法,但这样会导致算法获得的潜在解的质量不高,影响到算法的求解效果.此外,对于MKP问题中的每一个背包而言,可类似0-1 KP的方法给出处理不可行解的修复与优化法.

4 求解QKP与QMKP的EAs 4.1 QKP问题

QKP是Gallo等人^{[1, 77]}提出的一个KP问题,在金融业、集成电路设计、电信业、柔性制造系统以及机场、火车站和货运站的选址中具有重要的应用.QKP是一个强NP难问题,不存在近似比为常数的近似算法.QKP的一般描述为:给定n个项和一个载重为C的背包,项j具有价值p_j和重量w_j,且任意两个项i和j(1≤i≠j≤n)被同时装入背包时产生一个联合价值p_ij,其中,C,p_j,w_j和p_ij均为正整数.如何选择项装入背包,使它们的重量之和在不超过背包载重的前提下价值与联合价值之和最大?QKP的数学模型表示如下:

$\text{Max}f(Y)=\text{Max}\sum\nolimits_{j=1}^{n}{{{p}_{j}}{{y}_{j}}}+\sum\nolimits_{i=1}^{n-1}{\sum\nolimits_{j=i+1}^{n}{({{p}_{ij}}{{y}_{i}}{{y}_{j}})}}$

(13)

$\text{s}\text{.t}\text{. }\sum\nolimits_{j=1}^{n}{{{w}_{j}}{{y}_{j}}}\le C$

(14)

${{y}_{j}}\in \left\{ 0,1 \right\},j=1,2,\ldots ,n$

(15)

其中,y_j=1当且仅当项j被装入了背包中.不失一般性,设$\text{Max}\{{{w}_{j}}|j=1,2,...,n\}\le C<\sum\nolimits_{j=1}^{n}{{{w}_{j}}}.$

有关QKP的Benchmark请参考文献^[78].

目前,人们利用EAs提出了许多求解QKP的有效方法:Julstrom^[78]将贪心算法融入GA,提出了求解QKP的一种贪心遗传算法,他所提出的修复与优化法是利用EAs求解QKP时处理不可行解的一种非常有效的方法;文献^[79]提出了一种二进制AFS算法,并利用文献^[78]中的方法处理不可行解,给出了一种求解QKP的可行方法;Patvardhan等人^[80]提出了一种量子进化算法(quantum inspired evolutionary algorithm,简称QIEA),并采用文献^[78]中的方法处理不可行解,给出了求解QKP的一种有效方法.此外,他们还在文献^[81]中进一步讨论了QIEA的并行实现方法.

上述求解QKP的EAs均采用0-1向量表示问题的潜在解,使用修复与优化法而非罚函数法处理不可行解,取得了很好的效果,由此说明:在利用EAs求解QKP时,修复与优化法是处理不可行解的最佳选择.下面基于绝对价值密度(absolute value density,简称AVD)^[78]的贪心策略,给出修复与优化法的一种有效实现方法(记为qGROA).当然,也可以基于相对价值密度(relative value density,简称RVD)^[78]的贪心策略,类似于qGROA,给出另一种修复与优化法的实现方法.限于篇幅,在此略之.

记${{\delta }_{j}}={({{p}_{j}}+\sum\nolimits_{k\in {{A}_{Y}}}{{{p}_{jk}}})}/{{{w}_{j}}}\;$为项j的AVD,j=1,2,…,n,Y=[y₁,y₂,…,y_n]∈{0,1}ⁿ为QKP的一个潜在解,A_Y={k|y_k∈Y且y_k=1,k=1,2,…,n}.对QKP实例中的所有项按d_j由大到小的次序排序,并按照排序后的顺序将各项下标依次存于数组H[1,…,n]中.于是,qGROA的算法伪代码描述如下.

算法 5. qGROA.

(1)$R\leftarrow \sum\nolimits_{j=1}^{n}{{{w}_{j}}{{y}_{j}}};$

(2) if (R≤C) then goto 步骤(9) else j←n;

(3) while (R>C) do //对不可行解Y进行修复

(4) if (y_H[j]=1) then

(5) y_H[j]←0; R←R-w_H[j];

(6) end if

(7) j←j-1;

(8) end while

(9) for j←1 to n do //对已是可行解的Y进行优化

(10) if (y_H[j]=0) and (R+w_H[j]≤C) then

(11) y_H[j]←1; R←R+w_H[j];

(12) end if

(13) end for

不难看出:算法5与算法3调用子算法fGRA时的实现原理是完全一样的,只不过两种算法所使用的数组H[1,…,n]的确定方式不同罢了.此外,很容易像算法3调用子算法sGRA那样,给出算法5的另一种实现方法.

需要说明的是:在利用EAs求解QKP的研究成果中,仅涉及到GA,ABC和AFS等少数算法,诸如PSO,ACO,DE,HSA和SFLA等具有良好性能的EAs均未出现.由此容易看出:探讨基于还未被利用的EAs求解QKP的研究,将是一个值得关注的问题.此外,提出新的更高效的贪心策略,并由此给出一种更高效的修复与优化法,也是非常值得探讨的问题.

4.2 QMKP问题

QMKP是一个组合了QKP与MKP的KP问题,由Hiley和Julstrom^[9]于2006年在国际会议GECCO 2006上提出.QMKP的一般描述为:设项的集合N={1,2,...,n},背包的集合M={1,2,...,m},每个项j∈N具有价值p_j和重量w_j,当任意两个项i和j(1≤i≠j≤n)被装入同一个背包时产生一个联合价值p_ij,每个背包k∈M具有一个载重C_k,并且C_k,p_j,w_j和p_ij均为正整数.如何选择项装入背包,使得在满足下述两个前提条件下装入所有背包中项的价值之和最大.

(1) 每个项j∈N最多只能被装入一个背包中;

(2) 装入背包k∈M中所有项的重量之和不能超过C_k.

设y_ik∈{0,1},y_ik=1表示项i被装入了背包k中,y_ik=0表示项i不装入背包k中,则QMKP的数学模型为

$\text{Max}f(Y)=\text{Max}\sum\limits_{i=1}^{n}{\sum\limits_{k=1}^{m}{{{y}_{ik}}{{p}_{i}}+\sum\limits_{i=1}^{n-1}{\sum\limits_{j=i+1}^{n}{\sum\limits_{k=1}^{m}{{{y}_{ik}}{{y}_{jk}}{{p}_{ij}}}}}}}$

(16)

$\text{s}\text{.t}\text{. }\sum\nolimits_{i=1}^{n}{{{w}_{i}}{{y}_{ik}}}\le {{C}_{k}},\forall k\in M$

(17)

$\sum\nolimits_{k=1}^{m}{{{y}_{ik}}}\le 1,\text{ }\forall i\in N$

(18)

自从QMKP被提出之后,人们即开始了利用EAs对其求解的研究,获得了较好的研究成果.Saraç和Sipahioglu^[10]采用自然数编码方法提出了具有改进变异算子的遗传算法(SSGA),他们的改进不仅提高了解的质量,而且能够有效地避免变异后产生不可行解.因此,SSGA是求解QMKP的一种有效方法.文献^[82]基于反复选择两个父代个体交叉产生子代个体来替换种群中较差个体的方法,提出了一种改进的GA,可以快速获得一个较好的结果.文献^[83]在自适应链路调整进化算法(adaptive link adjustment evolutionary algorithm,简称ALA-EA)中使用有效初始化方法和启发式适应度改进方案(heuristic fitness improvement schemes)提出了一种新的Memetic算法,对QMKP的求解效果较好.Saraç和Sipahioglu^[84]进一步完善了SSGA,并将其用于求解更一般的QMKP.文献^[85]提出了一种量子进化求解算法,可有效求解QMKP.文献^[86]将路径重连(path relinking)方法和响应阈值搜索算法(responsive threshold search algorithm)相结合,提出了一种求解QMKP的首进化路径重链接算法(first evolutionary path relinking approach,简称EPR),可用于求解大规模QMKP实例.

从上面的总结不难看出:目前,用于求解QMKP的EAs也仅限于GA,ABC,ALA-EA和EPR等少数算法,许多经典的EAs(如PSO,DE和HSA等)还未被用于QMKP的求解研究,因此可以断言:探讨如何利用这些经典EAs有效地求解QMKP,将是今后研究的一个趋势.此外,由于QMKP是由QKP与MKP组合而成,在利用EAs求解QKP与MKP时存在的问题,对于QMKP也同样存在,所获得的宝贵经验对于QMKP也具有借鉴意义.

5 利用EAs求解其他KP的研究进展 5.1 RTVKP问题

时变背包问题(time-varying knapsack problem,简称TVKP)^[6]是Goldberg和Smith在0-1 KP中引入动态变化因素提出的一个KP问题,它也是一个动态组合优化问题.在TVKP中,背包载重不再固定不变,而是随着时间的推移在给定的若干个固定值之间震荡变化.贺毅朝等人^[7]将TVKP推广为随机时变背包问题(randomized time-varying knapsack problem,简称RTVKP),即:背包载重在一个给定范围内随机震荡变化,并且某些项的价值和重量也随着时间的推移进行震荡变化.显然,由于RTVKP中动态变化因素的增多,求解难度比TVKP大为增加.

设RTVKP中,n个项的初始价值集与重量集分别为P₀={p₀₁,p₀₂,…,p_0n}和W₀={w₀₁,w₀₂,…,w_0n},p_0j∈[A_v,B_v],w_0j∈[A_w,B_w](1≤j≤n),背包初始载重为C₀∈[A_c,B_c],A_v,B_v,A_w,B_w,A_c和B_c均为正整数,且A_v<B_v,A_w<B_w,B_w<A_c<B_c< nA_w.令T_i(i≥1)表示项的价值、重量或背包载重的第i-1次随机变化与第i次随机变化之间的时间间隔,称为第i次随机振荡变化周期.第i(i≥1)次随机变化后,n个项的价值集与重量集分别记为P_i={p_i1,p_i2,…,p_in}和W_i={w_i1,w_i2,…,w_in},背包载重记为C_i∈[A_c,B_c],其中,p_ij∈[A_v,B_v],w_ij∈[A_w,B_w](1≤j≤n),满足|(V_i∪W_i)-(V_i-1∪W_i-1)|≤Threshold,并且|(V_i∪W_i)-(V_i-1∪W_i-1)|+|C_i-C_i-1|>0,$Threshold\le 3\sqrt{n}$.记RTVKP_i-1(n,C_i-1,V_i-1,W_i-1)(i≥1)表示在周期T_i中以V_i-1为价值集、W_i-1为重量集、C_i-1为背包载重的0-1 KP子问题(记为RTVKP_i-1),则RTVKP问题即为依次求解时间间隔序列{T_i}_i≥1上的一系列RTVKP_i-1(i≥1)子问题的最优值与最优解.

令Y_i=[y_i1,y_i2,...,y_in]∈{0,1}ⁿ表示RTVKP_i(i≥0)的可行解,在第i次随机振荡变化周期中,项j(1≤j≤n)装入载重为C_i的背包时,y_ij=1,否则,y_ij=0.于是,RTVKP的数学模型描述为

$\text{Max}f({{Y}_{i}})=\text{Max}\sum\nolimits_{j=1}^{n}{{{y}_{ij}}{{p}_{ij}}}$

(19)

$\text{s}\text{.t}\text{. }\sum\nolimits_{j=1}^{n}{{{y}_{ij}}{{w}_{ij}}}\le {{C}_{i}}$

(20)

其中,i≥0且1≤j≤n,随机振荡变化周期为T_i+1.

显然,当(V_i∪W_i)-(V_i-1∪W_i-1)=∅时,RTVKP退化为TVKP.令MinT=min{T_i|T_i为RTVKP的第i次随机振荡变化周期,i≥1},则RTVKP实例的MinT值越小,其振荡变化频率越大,越不容易求解.有关RTVKP的Benchmark请参考文献^{[7, 8]}.

文献^[6]首先利用GA求解TVKP,提出了一种基于二倍体形式的遗传算法.文献^[87]利用具有多倍体形式的GA求解TVKP,指出:对于振荡变化频率较大的TVKP,多倍体方法更有优势.Yang^[88]提出原对偶遗传算法(primal-dual genetic algorithm,简称PDGA)以求解TVKP,计算结果表明,PDGA的求解效果优于标准GA.文献^[89]提出了一种带动态小生境的自组织学习算法(DNSLA),并利用DNSLA求解多个大规模TVKP实例,计算结果极佳.贺毅朝等人^{[7, 8]}研究了如何利用GA,DE和PSO等EAs求解RTVKP,给出了求解该问题的多种非常有效的近似算法.

RTVKP可以看成是由多个具有共性的0-1 KP构成,在利用EAs求解时,可以借鉴求解0-1 KP的经验,对不可行解采用修复与优化法(见算法3)比罚函数法更适宜.此外,当RTVKP的随机震荡变化周期较小时,对于算法的运算速度要求较高,因此,算法中应避免使用过于复杂的进化算子.

5.2 D{0-1}KP问题

D{0-1}KP^[13-15]是Guldan于2007年将“折扣”思想引入0-1 KP而提出的一个KP问题,在商贸经营、投资决策、项目筛选和预算控制等方面具有较高的应用价值.D{0-1}KP的一般描述为:给定n个均含有3个项的项集,项集i(0≤i≤n-1)中含有的3个项分别记为3i,3i+1,3i+2,其中,前两个项3i和3i+1具有的价值系数分别为p_3i和p_3i+1,具有的重量系数分别为w_3i和w_3i+1;前两个项合并在一起构成第3个项3i+2,它具有的价值系数为p_3i+2=p_3i+p_3i+1,具有的折扣重量系数为w_3i+2,满足w_3i+2<w_3i+w_3i+1并且w_3i<w_3i+2,w_3i+1<w_3i+2.在项集i(0≤i≤n-1)中,项3i,3i+1,3i+2中至多有一个可以被选择装入载重为C的背包中.如何选择各项装入背包,使得它们的重量系数之和在不超过背包载重的前提下价值系数之和达到最大?

不失一般性,设p_j,w_j(0≤j≤3n-1)和C均为正整数,并且w_3i+2≤C(0≤i≤n-1),$\sum\nolimits_{i=0}^{n-1}{{{w}_{3i+2}}}>C.$令D{0-1}KP的价值系数集为P={{p_3i,p_3i+1,p_3i+2}|0≤i≤n-1},重量系数集为W={{w_3i,w_3i+1,w_3i+2}|0≤i≤n-1},背包载重为C,则D{0-1}KP的数学模型为

$\text{Max}f(Y)=\text{Max}\sum\limits_{i=0}^{n-1}{({{y}_{3i}}{{p}_{3i}}+{{y}_{3i+1}}{{p}_{3i+1}}+{{y}_{3i+2}}{{p}_{3i+2}})}$

(21)

$s.t.~{{y}_{3i}}+{{y}_{3i+1}}+{{y}_{3i+2}}\le 1,i=0,1,\ldots ,n-1$

(22)

$\sum\nolimits_{i=0}^{n-1}{({{y}_{3i}}{{w}_{3i}}+{{y}_{3i+1}}{{w}_{3i+1}}+{{y}_{3i+2}}{{w}_{3i+2}})}\le C$

(23)

${{y}_{3i}},{{y}_{3i+1}},{{y}_{3i+2}}\hat{I}\left\{ 0,1 \right\},i=0,1,\ldots ,n-1$

(24)

其中,y_j=1表示项j被装入了背包中,y_j=0表示项j未被装入背包中.D{0-1}KP的Benchmark见文献^{[15, 16]}.

贺毅朝等人^[15]建立了D{0-1}KP的一个新的数学模型,利用GA并基于不同编码方法提出了求解它的两种有效算法,其中,所给出的两种修复与优化法是利用EAs求解D{0-1}KP时处理不可行解的通用方法.最近,他们又在文献^[90]中给出了处理D{0-1}KP不可行解的一种新方法,并利用BPSO^[40]提出了一种求解D{0-1}KP的更高效的方法.

由于D{0-1}KP的提出时间较晚,利用EAs对其求解研究相对较少,因此,如何利用DE,ABC,ACO和HSA等算法有效求解D{0-1}KP问题,将会成为今后的一个研究热点.

5.3 MMKP问题

MMKP^{[11, 12]}是由MCKP与MDKP组合而成的一个KP问题,它的一般描述为:给定n个项集的集合J={J₁,J₂,…,J_n}和m个载重分别为C₁,C₂,…,C_m的背包,其中,J_p∩J_q=∅,1≤p≠q≤n,每个项j∈J_i具有一个价值p_ij和m个重量w_ij1,w_ij2,…,w_ijm,其中,w_ijk是项j∈J_i被装入载重为C_k的背包时的重量,并且p_ij,w_ijk和C_k均为正整数,1≤i≤n,j∈J_i且1≤|J_i|=r_i,1≤k≤m.如何从每个项集中恰好选择一个项装入所有的背包中,在使得装入每个背包中项的重量之和均不超重的前提下,所有背包中项的价值之和达到最大?MMKP的数学模型为

$\text{Max}f(Y)=\text{Max}\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{{{r}_{i}}}{{{y}_{ij}}{{p}_{ij}}}}$

(25)

$\text{s}\text{.t}\text{. }\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{{{r}_{i}}}{{{w}_{ijk}}{{y}_{ij}}}}\le {{C}_{k}},\text{ }k=1,2,...,m$

(26)

$\sum\nolimits_{j=1}^{{{r}_{i}}}{{{y}_{ij}}}=1,\text{ }i=1,2,...,n$

(27)

${{y}_{ij}}\hat{I}\left\{ 0,1 \right\},i=1,2,\ldots ,n,j=1,2,\ldots ,{{r}_{i}}$

(28)

其中,y_ij=0表示项j∈J_i未装入任何背包中,y_ij=1表示项j∈J_i被装入了所有背包中.MMKP的Benchmark请参考文献^[12].

为了利用ACO求解MMKP,文献^[12]将最大-最小蚁群系统(max-min ant system)与拉格朗日松弛法(Lagrangian relaxation,简称LR)相结合,利用LR获得各项的值作为ACO的启发式因子,利用修复法处理不可行解,给出了求解MMKP的一种有效方法.计算结果表明,它比已有算法HMMKP,CCFT,RLS和MRLS的求解效果更优.文献^[91]提出了一种求解MMKP的多群体遗传算法(multi-population genetic algorithm,简称MPGA),MPGA用两个种群执行进化搜索,用一个种群进行归档以平衡算法在可行空间和不可行空间之间的搜索偏差,具有较好的求解效果.

MCKP与MDKP的难解性决定了MMKP的求解困难性,因此,基于EAs的已有求解方法对于复杂的大规模MMKP实例的求解性能有待进一步提高.显然,如何利用EAs高效求解MMKP,是一个有待于今后进一步深入研究的问题.

5.4 MOKP问题

MOKP^{[1, 92]}是KP问题中的一个多目标优化问题,其一般描述为:给定n个项和m个载重分别为C₁,C₂,…,C_m的背包,项j相对于背包i的价值为p_ij,重量为w_ij,1≤j≤n且1≤i≤m.求0-1向量Y=[y₁,y₂,...,y_n]∈{0,1}ⁿ,在满足m个约束不等式:

$\sum\nolimits_{j=1}^{n}{{{w}_{ij}}{{y}_{j}}}\le {{C}_{i}},\text{ }i=1,2,...,m$

(29)

的前提下,使得f(Y)=[g₁(Y),g₂(Y),…,g_m(Y)]最大.其中,

${{g}_{i}}(Y)=\sum\nolimits_{j=1}^{n}{{{p}_{ij}}{{y}_{j}}},\text{ }i=1,2,...,m$

(30)

文献^[92]提出了求解MOKP的一种混合评估分布算法(hybrid estimation of distribution algorithm,简称MOHEDA),给出了一种基于加权和的局部搜索方法,并利用随机修复法处理不可行解.Lu和Yu^[93]提出了一种自适应种群多目标量子演化算法(adaptive population multi-objective quantum-inspired evolutionary algorithm,简称APMQEA)以求解MOKP,其个体表示为量子比特,并分成若干个子群求解不同的目标函数.计算表明:APMQEA求得的结果非常接近Pareto最优前沿,而且非支配集有一个良好的分布.文献^[94]基于量子人工免疫算法(QAIS)和人工免疫系统(BAIS)提出了一个新的量子人工免疫系统(MOQAIS),可有效求解MOKP问题.文献^[95]提出了求解MOKP的一种基于指标的蚁群算法(indicator-based ant colony optimization,简称IBACO),在IBACO中,使用二元质量指标(binary quality indicator)指导蚂蚁进行搜索来提高算法的求解性能.

由于MOKP的多目标和多约束条件限制,导致它的求解难度较大.目前,用于求解MOKP的EAs仅限于以上几种算法,今后还有待进一步探讨利用更多EAs有效求解MOKP的方法.

6 总结与展望

EAs以其极强的全局寻优能力和极好的通用性,在求解KP问题的研究中越来越受到人们的重视.从已有的研究结果来看,利用EAs求解0-1 KP,MDKP和QKP的研究相对比较成熟,人们基于不同的EAs提出了求解这3个问题的许多高效方法.但是,利用EAs求解其他KP问题还存在许多不足:一方面,利用EAs求解这些问题的研究较少,很多性能优越的EAs还未被用于求解这些问题,如求解MKP,RTVKP,MOKP,MMKP,QMKP和D{0-1}KP等问题的EAs还仅限于少数几个,而PCKP,SUKP,MmKP和OLKP等问题甚至还未见利用EAs的求解研究报道;另一方面,在利用EAs求解KP时,表示问题潜在解或可行解的方法还仅限于0-1向量编码和自然数编码等经典方法,新的更适宜的编码方法还有待研究.此外,处理不可行解的方法与技术相对比较单调,缺乏与已有先进技术相结合的新的研究成果.

综合以上分析,下面给出利用EAs求解KP时有待解决的若干问题与研究思路.

(1) 利用EAs求解PCKP,SUKP,MmKP和OLKP等典型KP的有效算法的设计问题;

(2) 由于EAs是一类随机近似算法,在利用它们求解KP时,算法近似性能的估算问题有待解决.对此,是利用经典近似算法中的近似性能(即近似比)进行估算?还是给出一种新的度量方法?值得深入研究;

(3) 利用EAs求解KP时,潜在解或可行解的表示方法问题.例如,利用二进制数、自然数以及其他符号进行混合编码是否可行?利用量子比特矩阵编码是否可行?

(4) 能否基于机器学习、复杂网络、量子纠缠以及并行计算等方法设计比现有EAs更适于求解KP的高效进化算子?这既是关乎KP高效求解的一个关键问题,更是EAs算法设计中的一个核心问题;

(5) 能否利用松弛技术、原对偶技术、代理技术、次梯度方法和Bundle方法等给出处理KP不可行解的更为高效的方法?

(6) 对于还未利用EAs求解的KP,构造具有一定难度的大规模实例,为比较求解它的各EAs优劣提供通用的Benchmark实例;

(7) 利用新提出的EAs(例如果蝇优化(fruit fly optimization)^[96]、头脑风暴优化(brain storm optimization)^[97]等)求解KP问题的研究.