使用修补算子求解MKP问题的文献总结

按顺序进行丢弃--增加操作

决策变量根据规则排序（一般是根据效用排序），直接进行丢弃--增加操作。5，6，7是同一作者，5和6使用的效用和Chu是一样的，7则改进了效用的计算方式。8和9是清华大学王凌实验室的文章，与其他文章思路不一样，是按照约束进行丢项操作。
1）求解多维背包问题的改进二进制粒子群算法
2）改进二进制人工蜂群算法求解多维背包问题
3）无参数变异的二进制差分进化算法
4）利用改进的二进制狼群算法求解多维背包问题
5）A new ant colony optimization algorithm for the multidimensional Knapsack problem
6）Apply the Particle Swarm Optimization to the Multidimensional Knapsack Problem
7）Solving large-scale multidimensional knapsack problems with a new binary harmony search algorithm
8）A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem
9）An effective hybrid EDA-based algorithm for solving multidimensional knapsack problem
文章8：丢弃操作是确定性的，增项操作中，只针对一个松弛性最高的约束检索可以增加的变量。

其他

1）随机丢弃-确定增加：改进二进制布谷鸟搜索算法求解多维背包问题
2）随机丢弃：一种求解多背包问题的改进的人工鱼群算法
3）确定丢弃：求解０－１背包问题的二进制狼群算法
4）效用动态改变：同一个作者的两篇文章a) Self-adaptive check and repair
operator-based particle swarm optimization for the multidimensional knapsack problem（当解陷入局部最优一定时间后，将进入修正效用的阶段，重新进入搜索）;b) Three pseudo-utility ratio-inspired particle swarm optimization with local search for multidimensional knapsack problem
5）多目标0／1背包问题MOEA求解中的修复策略（不同背包赋予不同的权重，讨论了很多策略，非常详细）

讯享网

实现鼻祖文章chu的代码

function [bx, result, con] = GA_MKP(prob,alg) % 参考文献： % Chu P C , Beasley J E . A Genetic Algorithm for the Multidimensional % Knapsack Problem[J]. Journal of Heuristics, 1998, 4(1):63-86. % 功能：二进制遗传算法解MKP问题 % 输入 % prob 问题的属性 % prob.Nvar 变量数 % prob.weight 每个物品的权重 % prob.A 约束系数 % prob.R 约束右端项 % prob.bestP 目前为止该问题的最优解 % alg 搜索参数 包括 % alg.PS 人口规模 % alg.NG 最大迭代次数 % alg.pc 交叉概率 % alg.pu 变异概率 % alg.pr 替换概率 % 输出 % bx 最优解 % con 记录得到的最优解 % result 结构体 % result.bP 最优解的函数值 % result.ni 最优解对应选择照片的个数 % result.NGen 运行停止时迭代的次数 % result.T 运算时间 % result.bx 每次迭代停止时输出的最优解 % result.isfeasible 解是否可行的标志 % 子函数 修复算子 % [x,fit] = repair_MKP(x,prob) % 输入 % x： 输入的基因的值 % 输出 % x： 修复后的x值 % fit： 可行解的适应度值 % 参数设置 tic % 计时器 bestP = prob.bestP; % 精确解 weight = prob.weight; R = prob.R; A = prob.A; Nvar = prob.Nvar; % 基因长度 PS = alg.PS; % 种群大小 NG = alg.NG; % 最大迭代次数 n_competition = alg.n_competition; % 锦标赛选择个体数 nc = size(A,1); % 生成初始解 Parent = zeros(PS,Nvar); for i = 1:PS x = zeros(1,Nvar); T = 1:Nvar; nT = Nvar; j = T(ceil(rand * nT)); T(j ) = []; S = zeros(nc,1); while all(S + A(:,j) <= R) x(j) = 1; S = S + A(:,j); nT = nT-1; id= ceil(rand*nT); % 找到装入背包的变量 j = T(id); T(id) = []; end Parent(i,:) = x; end Fit = sum(bsxfun(@times, weight, Parent),2); [bP,id] = max(Fit); % 记录最优值 bx = Parent(id,:); con = zeros(NG,1); % 每一代的最优解 NGen = PS; % 迭代次数 evaluate_time = PS; % 评价次数 con(1:PS) = sort(Fit); %% 开始迭代 while bP < bestP && NGen < NG % 终止条件 达到了最优解或者最大评价次数 child = Parent(1,:); id =1; while any(all( bsxfun(@eq,child,Parent(id,:)), 2)) % 生成一个和父代不同的个体 % turnament selection T = 2 % 选择第一个个体 id1 = ceil(rand(n_competition,1)*PS); [~,k1] = max(Fit(id1)); P_1 = Parent(id1(k1),:); % 选择第二个个体 id2 = ceil(rand(n_competition,1)*PS); [~,k2] = max(Fit(id2)); P_2 = Parent(id1(k2),:); % Crossover and mutation % uniform crossover 两个父代个体产生一个子代个体 child = zeros(1,Nvar); id = rand(1,Nvar) < 0.5; child(id) = P_1(id); child(~id) = P_2(~id); % mutation 只变异两个位置 要使用吗？ k = ceil(rand*2); k = ceil(rand(1,2) * Nvar); while(k(1)==k(2)) k(2) = ceil(rand * Nvar); end child(k) = 1-child(k); % 修复和评价 [child,childFit] = repair_MKP(child, prob); evaluate_time = evaluate_time + 1; % 判断子代是否和父代中的个体重复 id = sum(child,2)==sum(Parent,2); end % 将父代中的最差解替换为子代 [~,min_P] = min(Fit); Parent(min_P,:) = child; Fit(min_P) = childFit; % 更新全局最优解 [~,g] = max(Fit); if Fit(g)>bP bx = Parent(g,:); bP = Fit(g); end con(NGen)=bP; % 记录最优解 if rem(NGen,10000)==0 % 图示化 disp(bP) plot(con(1:NGen)) pause(eps) end NGen = NGen+1; end % end for while % 输出 result.bP=sum(prob.weight.*bx); result.ni = sum(bx>0); result.NGen = NGen-1; result.evaluate_time = evaluate_time; result.bx = bx; result.T=toc; % 判断解是否可行 nc = sum(sum(prob.A.*bx,2)>prob.R); result.isfeasible = nc;

讯享网function [x,fit] = repair_MKP(x,prob) % 修复不可行解 % 输入 % x： 输入的解 % 输出 % x： 修复后的x的值 % fit： 可行解x的适应度值 % 输入基本信息 weight=prob.weight; % 目标函数中变量的系数 A = prob.A; % 约束中变量的系数 R = prob.R; % 约束右端项 Nvar = prob.Nvar; % 变量的个数 iden = 1:Nvar; x = x'; %% drop S = A*x; % 计算每一个约束的左端项之和 j = Nvar; % % 法一 文献中的处理方式 while any(S > R) if x(j)>0 x(j) = 0; S = S-A(:,j); end j = j-1; end % 法二 根据自己的理解稍作修改 % id = any(S > R); % while any(id) % if (x(j)>0)&&any(A(id,j)) % x(j) = 0; % S = S-A(:,j); % end % id = S > R; % j = j-1; % end %% add To_0 = iden(x==0); for j = To_0 if all(S + A(:,j)<= R) x(j) = 1; S = S + A(:,j); end end %% 输出 x = x'; fit = sum(weight.*x);

数据和代码链接