【背包问题】基于matlab量子免疫克隆算法求解背包问题【含Matlab源码 424期】
一、获取代码方式
获取代码方式1：
完整代码已上传我的资源：【背包问题】基于matlab量子免疫克隆算法求解背包问题【含Matlab源码 424期】
获取代码方式2：
通过订阅紫极神光博客付费专栏，凭支付凭证，私信博主，可获得此代码。
备注：
订阅紫极神光博客付费专栏，可免费获得1份代码（有效期为订阅日起，三天内有效）；
二、背包问题简介
1【背包问题】
背包问题(Knapsack problem)是一种组合优化的NP完全问题。
问题描述为：给定一组物品，每种物品都有自己的重量weight和价格value，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
2【0-1背包问题】
对每个物品i 只有 装入/不装入背包 两种情况。
我们有n种物品，物品j的重量为wj，价格为pj。
我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。
如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。
令V（i，j）表示前i个物品中能够装入容量为j的背包中的物品价值最大值，则可得到动态规划函数：
V(i,0) = V(0,j)=0; //把前i个物品装入容量为0的背包 和 把0个物品装入容量为j的背包，价值均为0
V(i,j) = V(i-1,j) j<wi //如果第i个物品的重量大于背包容量wi>j，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值相同，即物品i不装入背包
V(i,j) = max{ V(i-1,j)，V(i-1,j-wi)+vi } j>wi // 1.如果把第i个物品装入背包，则背包中物品的价值=把前i-1个物品装入容量为j-wi背包中的价值加上第i个物品的价值vi； 2. 如果第i个物品没有装入背包，则背包中价值=前i-1个物品装入容量为j的背包中所取得的价值。 取二者中价值较大者。
step 1：只装入前1个物品，确定各种情况下的背包能够得到的最大价值；
step 2：只装人前2个物品，确定各种情况下的背包能够得到的最大价值；.
step n：…
最后V(n,C)便是容量为C的背包中装入n个物品时取得的最大价值。
为了得到V(n,C) 需想前推到V(n-1,C)。如果V(n,C)>V(n-1,C),则第n个物品装入背包，前n-1个物品装入容量为C-wn的背包中；否则，第n个物品没有被装入背包，前n-1个物品被装入容量为C的背包中。
直到确定第一个物品是否被装入背包中。
得到：
当 V(i,j)= V(i-1,j)， xi = 0；
当 V(i,j) > V(i-1,j)， xi = 1，j = j-wi；
三、量子免疫克隆算法简介
四、部分源代码
clear;
C=[253 245 243 239 239 239 238 238 237 232 231 231 230 229 228 227 224 217 213 207 203 201 195 194 191 187 187 177 175 171 169 168 165 164 161 160 158 150 149 147 141 140 139 136 135 132 128 126 122 120 119 116 116 114 111 110 105 105 104 103 93 92 90 79 78 77 76 76 75 73 62 62 61 60 60 59 57 56 53 53 51 50 44 44 42 42 38 36 34 28 27 24 22 18 12 10 7 4 4 1];
W=[253 245 243 239 239 239 238 238 237 232 231 231 230 229 228 227 224 217 213 207 203 201 195 194 191 187 187 177 175 171 169 168 165 164 161 160 158 150 149 147 141 140 139 136 135 132 128 126 122 120 119 116 116 114 111 110 105 105 104 103 93 92 90 79 78 77 76 76 75 73 62 62 61 60 60 59 57 56 53 53 51 50 44 44 42 42 38 36 34 28 27 24 22 18 12 10 7 4 4 1];
V=6666;
a=2.40;
q=(sqrt(1/2)).*ones(20,100);
[N,L] = size(q); ger =500; pm=0.0088; pc=0.88; fat=0.1;
disp(sprintf('Number of generations: %d',ger));
disp(sprintf('Population size: %d',N/2));
% General parameters & Initial operations
vmfit = []; it = 1; vx = []; T=[]; vw=[];
f='dot(v,C1,2)';
updatef=0;
% Generations
t0 = clock;
c1=0;
while it <= ger
itemp=[1 3 5 7 9 11 13 15 17 19];
v=observe(q(itemp,:));
rate=C./W;
[a,ind] = sort(rate);
for j=1:N/2
i1=1;
%repair
knoverfilled=0;
if dot(v(j,:),W)>6666
knoverfilled=1;
end
while knoverfilled==1
v(j,ind(i1))=0;
if dot(v(j,:),W)<=6666
knoverfilled=0;
end
i1=i1+1;
end
v(j,:)=v(j,:);
end
%and/or Crossver
for i=1:N/2
cind(i)=i;
end
for i=1:N/2
point=unidrnd(N/2-i+1);
temp=cind(i);
cind(i)=cind(i+point-1);
cind(i+point-1)=temp;
end
for i=1:2:N/2
p=rand(1);
if(p<pc)
c1=and(v(cind(i),:),v(cind(i+1),:));
c2=or(v(cind(i),:),v(cind(i+1),:));
v(cind(i),:)=c1;
v(cind(i+1),:)=c2;
end
end
for j=1:N/2
i1=1;
%repair
knoverfilled=0;
if dot(v(j,:),W)>6666
knoverfilled=1;
end
while knoverfilled==1
v(j,ind(i1))=0;
if dot(v(j,:),W)<=6666
knoverfilled=0;
end
i1=i1+1;
end
v(j,:)=v(j,:);
end
C1=ones(N/2,1)*C;
fit=eval(f);
[sol,indb] = max(fit);
maxf=sol;
max1=v(indb,:);
minf=min(fit);
if updatef>=sol
maxf=updatef;
max1=updatec;
else
maxf=sol;
max1=v(indb,:);
end
%量子变异
for i=1:2:size(q,1)
for j=1:size(q,2)
if v((i+1)/2,j)==max1(1,j)
if max1(1,j)==0
s=0;
angle=0;
else
if q(i,j)*q(i+1,j)>0
s=1;
angle=0.015;
end
if q(i,j)*q(i+1,j)<0
s=-1;
angle=0.015;
end
if q(i,j)==0
s=0;
angle=0.015;
end
if q(i+1,j)==0
s=1;
angle=0.015;
end
end
elseif v((i+1)/2,j)==0
if maxf>fit((i+1)/2)
s=0;
angle=0;
else
if q(i,j)*q(i+1,j)>0
s=-1;
angle=0.015;
end
if q(i,j)*q(i+1,j)<0
s=1;
angle=0.015;
end
if q(i,j)==0
s=1;
angle=0.015;
end
if q(i+1,j)==0
s=0;
angle=0.015;
end
end
else
if maxf>fit((i+1)/2)
if q(i,j)*q(i+1,j)>0
s=-1;
angle=0.015;
end
if q(i,j)*q(i+1,j)<0
s=1;
angle=0.015;
end
if q(i,j)==0
s=1;
angle=0.015;
end
if q(i+1,j)==0
s=0;
angle=0.015;
end
else
if q(i,j)*q(i+1,j)>0
s=1;
angle=0.015;
end
if q(i,j)*q(i+1,j)<0
s=-1;
angle=0.015;
end
if q(i,j)==0
s=0;
angle=0.015;
end
if q(i+1,j)==0
s=1;
angle=0.015;
end
end
end
o=s*angle*pi;
u=[cos(o) -sin(o);sin(o) cos(o)];
temp1=[q(i,j);q(i+1,j)];
temp2=u*temp1;
q(i,j)=temp2(1,1);
q(i+1,j)=temp2(2,1);
end
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
五、运行结果
六、matlab版本及参考文献
1 matlab版本
2014a
2 参考文献
[1] 包子阳,余继周,杨杉.智能优化算法及其MATLAB实例（第2版）[M].电子工业出版社，2016.
[2]张岩,吴水根.MATLAB优化算法源代码[M].清华大学出版社，2017.
文章来源: qq912100926.blog.csdn.net，作者：海神之光，版权归原作者所有，如需转载，请联系作者。
原文链接：qq912100926.blog.csdn.net/article/details/114223754
- 点赞
- 收藏
- 关注作者
评论（0）