背包问题(knapsack problem， 简称KP)[1]是筹商机科学中的一类重要的NPC问题， 亦然一类经典的组合优化问题， 在投资方案与资源分派等方面具有重要的应用配景[2黑丝 少妇， 3].0-1背包问题(0-1 knapsack problem， 简称0-1KP)[2]是最典型的KP问题， 其一般刻画为:从n个具有价值与分量的物品中选择些许个装入一个具有载重为止的背包， 如何选择物品使得装入物品的分量之和在不最初背包载重前提下价值之和达到最大.

设第i(1≤i≤n)个物品的价值与分量远隔为vi与wi， 背包载重为C， 其中， vi， wi与C均为正整数; 令Y=(y1， y2， …， yn)∈{0， 1}n暗示0-1KP的一个可行解， 当第i个物品被装入背包时yi=1， 不然yi=0， 则0-1KP的数学模子为:

$ \max f(Y) = \max \sum\nolimits_{i = 1}^n {{v_i}{y_i}} $ (1) $ \begin{array}{*{20}{c}} {{\rm{s}}{\rm{.t}}{\rm{.}}}&{\sum\nolimits_{i = 1}^n {{w_i}{y_i} \le C} } \end{array} $ (2)

动态背包问题(dynamic knapsack problem， 简称DKP)[4， 5]是0-1KP的一种动态延迟形势.在DKP中， 物品的价值、分量或背包载重不再固定不变， 而是跟着时辰的推移可能变大或减轻， 因此DKP是一种比0-1KP更不易求解的动态组合优化问题.

Goldberg等东谈主[4]起头提倡了背包载重在两个固定值之间飘浮变化的DKP:时变背包问题(time-varying knapsack problem， 简称TVKP)， 况且他们诓骗二倍体遗传算法(genetic algorithm， 简称GA)求解TVKP问题.随后， Hadad等东谈主[6]改进了Goldberg等东谈主的重要， 提倡了求解TVKP的多倍体GA， 并指出其关于变化频率较大的TVKP多倍体重要更具有上风.Yang[7]诓骗原对偶遗传算法(primal-dual genetic algorithm， 简称PDGA)求解TVKP问题， 筹商扫尾标明其求解扫尾优于基本GA.Lewis等东谈主[8]相比了几种多倍体重要在求解TVKP时的优劣， 指出当背包载重在k(k≥3)个固定值之间飘浮变化时多倍体重要的上风并不卓绝显着.周传华等东谈主[9]提倡了一种带动态小生境的自组织学习算法(DNSLA)， 并将DNSLA用于求解多个界限为100的TVKP实例.贺毅朝等东谈主[10， 11]诓骗动态筹算(dynamic programming， 简称DP)求解背包载重在给定区间内立地飘浮变化的TVKP问题， 提倡了求解它的两种精准算法.李宁等东谈主[12]则利器用有羼杂编码的和声搜索算法求解背包载重在给定区间内立地飘浮变化的TVKP问题.

He等东谈主[13]将TVKP施四肢立地时变背包问题(randomized time-varying knapsack problem， 简称RTVKP)， 并远隔诓骗DP、贪默算法和GA给出了求解RTVKP问题的精准算法、类似算法和进化算法， 初步盘考了求解动态组合优化问题的类似算法优劣的评价规范.由于0-1KP是RTVKP的特例， 因此RTVKP亦然一个NPC问题.此外， 跟着时辰的推移， RTVKP中物品的价值、分量以及背包载重均可能变大或减小， 故而RTVKP是比TVKP的求解难度更大的DKP.在本文中， 起头诓骗DP提倡一种求解RTVKP的新精准算法， 然后远隔基于差分演化和粒子群优化给出求解RTVKP的两种灵验进化算法.

本文第1节给出RTVKP的界说与数学模子， 并简要分析其特质.第2节先容诓骗第二动态筹算法求解0-1KP的基本算法， 诓骗它们提倡一种求解RTVKP的精准算法， 并相比其与已有精准算法的时辰复杂度.第3节起头给出基于进化算法求解RTVKP时科罚不成行解的灵验算法GOA[13]， 然后远隔诓骗差分演化和粒子群优化与GOA相合并， 提倡求解RTVKP问题的两种进化算法.第4节通过对5个较大界限RTVKP实例的仿真筹商， 考证进化算法求解RTVKP问题的高效性与实用性.临了， 回归全文， 并提倡今后进一步的计划想路.

1 RTVKP问题过甚数学模子

所谓立地时变背包问题(RTVKP)[13]， 即给定n个物品和一个背包， 每个物品均具有价值与分量两种属性， 背包具有载重为止， 况且物品的价值和分量以及背包载重均不错跟着时辰的推移而动态立地飘浮变化.如安在每一变化拒绝周期内选择物品装入背包， 使得在不最初背包现时载重的前提下装入物品的价值之和达到最大.

设RTVKP中n个物品的运行价值集与运行分量集远隔为V0={v01， v02， …， v0n}和W0={w01， w02， …， w0n}， v0j∈[Av， Bv]， w0j∈[Aw， Bw](1≤j≤n)， 背包运行载重为C0∈[Ac， Bc]， 其中Av， Bv， Aw， Bw， Ac和Bc均为正整数， 且Av < Bv， Aw < Bw， Bw < Ac < Bc < nAw.令Ti(i≥1)暗示物品的价值、分量或背包载重的第i-1次立地飘浮变化与第i次立地飘浮变化之间的时辰拒绝(即在此拒绝内物品的价值、分量和背包载重齐是固定不变的)， 称为第i次立地变化周期(单元为s).记第i(i≥1)次立地变化后n个物品的价值集与分量集远隔为Vi={vi1， vi2， …， vin}和Wi={wi1， wi2， …， win}， 背包载重为Ci∈[Ac， Bc]， 其中vij∈[Av， Bv]， wij∈[Aw， Bw](1≤j≤n)， 况且鼎沸|(Vi∪Wi)-(Vi-1∪Wi-1)|≤Threshold(一般取$Thrshold \le 3\sqrt n $)， |(Vi∪Wi)-(Vi-1∪Wi-1)|+|Ci-Ci-1| > 0.记RTVKPi-1(n， Ci-1， Vi-1， Wi-1)(i≥1)暗示在立地变化周期Ti中以Vi-1为价值集， Wi-1为分量集， Ci-1为背包载重所对应的0-1KP子问题(进一步简记为RTVKPi-1)， 则RTVKP即为挨次求解时辰拒绝序列{Ti}i≥1上的一系列RTVKPi-1(i≥1)子问题的最优值与最优解.

令Yi=(yi1， yi2， …， yin)∈{0， 1}n暗示RTVKPi(i≥0)的可行解， 则此时第j(1≤j≤n)个物品装入载重为Ci的背包时yij=1， 不然yij=0.于是， 在Ti+1的时辰为止下， RTVKP的数学模子刻画如下:

$ \max f({Y_i}) = \max \sum\nolimits_{j = 1}^n {{y_{ij}}{v_{ij}}} $ (3) $ \begin{array}{*{20}{c}} {{\rm{s}}{\rm{.t}}{\rm{.}}}&{\sum\nolimits_{j = 1}^n {{y_{ij}}{w_{ij}} \le {C_i}} } \end{array} $ (4)

其中， i≥0， 1≤j≤n; Vi={vi1， vi2， …， vin}和Wi={wi1， wi2， …， win}远隔为RTVKPi对应的价值集和分量集， Ci为背包载重.

当RTVKP的物品价值集和分量集均不发生变化时， 即(Vi∪Wi)-(Vi-1∪Wi-1)=∅时， RTVKP退化为TVKP.赫然， RTVKP是由一系列具有部分共同数据的0-1KP子问题组成的， 即子问题RTVKPi与RTVKPi+1(i≥0)的大部分物品的价值与分量是疏导的， 唯有少部分物品的价值、分量或背包载重是相异的.恰是由于RTVKP的子问题之间的这种共罕有据特征， 使得大略诓骗DP对其进行求解.

令MinT=min{Ti|Ti为RTVKP的第i次立地变化周期， i≥1}， 则RTVKP实例的MinT值越小， 要求算法妥当其飘浮变化的才智就越高， 实例就越莽撞易被收效求解.此外， 当RTVKP问题的立地变化周期Ti恒为常数时， 称其为具有固定变化周期的RTVKP， 并简记为fixRTVKP.

2 基于动态筹算法求解RTVKP问题

动态筹算(DP)[11， 14-16]是一种重要的算法遐想重要， 适于求解具有最优子结构性质的最优化问题.在诓骗DP求解问题时， 刻画子问题的最优解的结构特征， 并依此开辟问题与子问题最优值之间的递推公式是算法遐想的重要场所; 一朝开辟了递推公式， 就不错左证它按照自底进取的样式逐个求解各子问题的最优值， 最终求得原问题的最优值(这还是过经常诓骗填表已矣); 然后， 左证求得的最优值和递推公式， 按照自顶向下的样式渐渐细目问题的一个最优解(这还是过经常是按照与填表相悖的规定查表已矣).

底下起头给出求解0-1KP的第二动态筹算法[11， 16]， 然后诓骗它提倡一种求解RTVKP问题的具有伪多项式时辰的新精准算法.

设0-1KP问题的价值集与分量集远隔为V={v1， v2， …， vn}和W={w1， w2， …， wn}， 背包载重为C.为了开辟0-1KP最优值的递推公式， 令Uik暗示从前i个物品中选择物品装入背包， 当所选择物品的价值之和就是k时分量之和所能达到的最小值， 其中， 1≤i≤n， 0≤k≤P且$P = \sum\nolimits_{j = 1}^n {{v_j}}$; 若是前i个物品中不存在的价值之和就是k的物品子集， 则令Uik=∞， 于是有递推公式

$ {U_{ik}} = \left\{ {\begin{array}{*{20}{l}} {\min \{ {U_{i - 1，k}}，{U_{i - 1，k - {v_i}}} + {w_i}\} ，}&{{\rm{if }}{v_i} \le k，{\rm{ }}i \ge 2}\\ {{U_{i - 1，k}}，}&{{\rm{if }}{v_i} > k，{\rm{ }}i \ge 2} \end{array}} \right. $ (5)

运行条目为Ui0=0(1≤i≤n)， U1k=∞(1≤k≤P， k≠v1)且${U_{1{v_1}}} = {w_1}$.由式(5)可知， Uik的筹商与背包载重无关， 但与通盘物品的价值之和是洽商的.筹商出通盘Unk(1≤k≤P)之后， 即可由$OPT = \mathop {\max }\limits_{1 \le k \le P} \{ k|{U_{nk}} \le C\} $求得0-1KP的最优值.

设Uik(1≤i≤n， 0≤k≤P)存于二维数组U[1…n， 0…P]中， 其中$P = \sum\nolimits_{j = 1}^n {{v_j}}$; 令P0， low和high均为整型变量， 况且1≤low≤high≤n， P0≤P; 记T为给定的求解周期， 函数SystemTime()用于得到系统现时时辰， 于是在周期T内求Uik(1≤i≤n， 0≤k≤P)的算法OPTfor0-1KP刻画如下.

算法1. OPTfor0-1KP.

输入:聚拢V和W; 参数C， T， n， low， high， P0和P.

输出:二维数组U[low...high， P0…P].

1.  time←SystemTime();

2.  if P0=0 then

3.    fori=low to high do U[i， 0]←0;

4.  end if

5.  if low=1 then

6.    for k=1 to P do U[1， k]←∞;

7.    U[1， v1]←w1;

8.  end if

9.  for i=low to high do

10.    for k=P0 to P do

11.      U[i， k]←U[i-1， k];

12.      if vi≤k then $U[i，k] \leftarrow \min \{ U[i - 1，k]，U[i - 1，k - {v_i}] + {w_i}\}$;

13.      if SystemTime()-time≥T and (k < P or i < high) then return (“Solving failure”);

14.    end for

15.  end for

16.  return (U[low...high， P0…P]).

算法1的时辰复杂度为O((high-low+1)(P-P0+1)).隆重到， 当P > > P0时， P-P0+1是一个大整数， log2(P-P0+1)为其输入界限， 因此算法1是一种伪多项式时辰精准算法.在求0-1KP时， 起头诓骗算法1筹商U[1…n， 0…P]， 其调用样式为OPTfor0-1KP(n， V， W， C， 1， n， 0， P， T)， 然后由$OPT = \mathop {\max }\limits_{1 \le k \le P} \{ k|U[n，k] \le C\} $即可求得最优值.

在算法1的基础上， 求解0-1KP最优解的算法SOLfor0-1KP刻画如下.

算法2. SOLfor0-1KP.

输入:聚拢V和W; 参数n， C， OPT; 二维数组U[1…n， 0…P].

输出:0-1KP问题的最优解Y=(y1， y2， …， yn)∈{0， 1}n.

1.  i←n; k←OPT;

2.  for i=1 to n do yi←0;

欧美在线成人

3.  while (i > 1 and k > 0) do

4.    if U[i， k]=U[i-1， k-vi]+wi then yi←1 and k←k-vi;

5.    i←i-1;

6.  end while

7.  if (i=1 and U[1， k]=w1) then y1←1;

8.  return (Y).

算法2输出0-1KP的一个最优解Y， 其算法时辰复杂度为Θ(n); 在算法2的输入参数中， OPT是最优解Y对应的最优值.关于0-1KP， 诓骗算法2求其最优解的调用样式为SOLfor0-1KP(n， V， W， C， OPT， U[1…n， 0…P]).

底下起头诓骗算法1和算法2基于动态筹算法请问求解RTVKP问题的算法(记为DPfRTVKP)遐想想想， 然后给出其算法伪代码刻画.

运行时， 调用算法1和算法2在立地变化周期T1内径直求解子问题RTVKP0(n， C0， V0， W0).

假定子问题RTVKPi(n， Ci， Vi， Wi)(i≥0)已经求解已矣， 况且其某些物品的价值和分量或背包载重发生变化得到后继子问题RTVKPi+1(n， Ci+1， Vi+1， Wi+1)， 则按照如下的两种情形对RTVKPi+1进行求解.

(1) 当(Vi+1∪Wi+1)-(Vi∪Wi)=∅时， 讲明RTVKPi立地变化为RTVKPi+1时仅有背包载重发生了篡改， 物品的价值与分量均未篡改， 此时径直诓骗$OPT = \mathop {\max }\limits_{1 \le k \le P} \{ k|{U_{nk}} \le {C_{i + 1}}\} $和算法2求解即可.

(2) 当(Vi+1∪Wi+1)-(Vi∪Wi)≠∅时， 讲明RTVKPi立地变化为RTVKPi+1时至少有1个物品的价值或分量发生了篡改， 于是令${P_i} = \sum\nolimits_{j = 1}^n {{v_{ij}}} $， ${P_{i + 1}} = \sum\nolimits_{j = 1}^n {{v_{i + 1，j}}}$， 并设low为聚拢(Vi+1∪Wi+1)-(Vi∪Wi)中物品的最小下标， 则左证Pi与Pi+1的大小情况诓骗算法1远隔筹商如下:

(2.1) 若是Pi≥Pi+1， 则求解RTVKPi时已经筹商的Uik(1≤i≤low-1， 0≤k≤Pi+1)关于RTVKPi+1仍适用， 此时只需诓骗算法1再行筹商Uik(low≤i≤n， 0≤k≤Pi+1)即可;

(2.2) 若是Pi < Pi+1， 则求解RTVKPi时已经筹商的Uik(1≤i≤low-1， 0≤k≤Pi)关于RTVKPi+1仍适用， 此时只需诓骗算法1远隔筹商Uik(1≤i≤low-1， Pi+1≤k≤Pi+1)和Uik(low≤i≤n， 1≤k≤Pi+1)即可.

在按照上述重要筹商出Uik(1≤i≤n， 0≤k≤Pi+1)之后， 诓骗$OPT = \mathop {\max }\limits_{1 \le k \le P} \{ k|{U_{nk}} \le {C_{i + 1}}\} $求得RTVKPi+1的最优值， 然后再调用算法2求得其最优解.

令m为RTVKP的立地飘浮变化次数， 则RTVKP可视为由m个0-1KP子问题组成.令V={v1， v2， …， vn}与W={w1， w2， …， wn}远隔暗示子问题的价值集和分量集， C暗示背包载重.设函数CheckVary(V0， W0， C0)的作用是在V0， W0和C0的基础上， 在区间[Av， Bv]， [Aw， Bw]和[Ac， Bc]上立地产生新的价值集V、分量集W和背包载重C， 函数GetPeriod()用于产生新的立地变化周期T， 函数FindIndex((V∪W)-(V0∪W0))用于细目聚拢(V∪W)-(V0∪W0)中物品的最小下标， 于是DPfRTVKP的算法伪代码刻画如下.

算法3. DPfRTVKP.

输入:运行价值集V0={v01， v02， …， v0n}; 运行分量集W0={w01， w02， …， w0n}; 运行背包载重C0; 参数n， m， Threshold， Av， Bv， Aw， Bw， Ac和Bc.

输出:RTVKP的m个子问题的最优值与最优解.

1.  V←V0; W←W0; C←C0;

2.  P0←0;$P \leftarrow \sum\nolimits_{j = 1}^n {{v_j}}$; low←1; high←n; k←0;

3.  T←GetPeriod(); time←SystemTime();

4.  (U[low...high， P0…P])←OPTfor0-1KP(n， V， W， C， low， high， P0， P， T);

5.  while (k < m) do

6.    if (V∪W)-(V0∪W0)≠∅ then

7.      if P0 < P then

8.        (U[1...low-1， P0+1…P])←OPTfor0-1KP(n， V， W， C， 1， low-1， P0+1， P， T);

9.        T←T-SystemTime()+time;

10.      end if

11.      (U[low...n， 0…P])←OPTfor0-1KP(n， V， W， C， low， n， 0， P， T);

12.    endif

13.    $OPT \leftarrow \mathop {\max }\limits_{1 \le j \le P} \{ j|U[n，j] \le C\}$;

14.    Y←SOLfor0-1KP(n， V， W， C， OPT， U[1…n， 0， …P]);

15.    return (OPT， Y);

16.    while (SystemTime()-time < T) do SystemTime();

17.    if (k < m-1) then

18.      V0←V; W0←W; C0←C; P0←P; T←GetPeriod();

19.      (V， W， C)←CheckVary(V0， W0， C0); $P \leftarrow \sum\nolimits_{j = 1}^n {{v_j}}$;

20.      low←FindIndex((V∪W)-(V0∪W0)); time←SystemTime();

21.    end if

22.    k←k+1;

23.  end while

24.  return (“Success to solve”).

隆重到RTVKP的界限由物品个数n和子问题数m细目黑丝 少妇， 记Pmax=max ({|Pi-Pi-1

• 黑丝 少妇
• 算法
• 求解
• 立地
• 事变