2022年2022年量子遗传算法求解背包问题程序 .pdf

《2022年2022年量子遗传算法求解背包问题程序 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年量子遗传算法求解背包问题程序 .pdf（7页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、%qga n=100;%群体规模g=100;%进化代数m=50; w=80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1; %物品重量p=220,208,198,192,108,108,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77

2、,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1; %物品价值% clf clear global m n;% 全局变量， m 为染色体串长，即背包问题中的物品数量，n 为群体规模m=input(please input chromsome length m=:);% 输入串长w=80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,1

3、5,10,10,10,4,4,2,1 p=220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1 C=1000; save mwpC m w p C %knapsack clf clear global m n;% 全局变量， m 为染色体串长，即背包问题中的物品数量，n 为群体规模m=input(please inp

4、ut chromsome length m=:);% 输入串长for i=1:m w(i)=1+rand()*9;% 物品重量p(i)=w(i)+5; %物品价值end C=sum(w)/2;% 限制重量w,p save mwpc m w p C % 保留数据，重复试验使用相同的数据%初始化群体，规模1，染色体位数10，%n=input(please input population size n=:);% 群体规模%g=input(please input max-generation g=:);% 进化代数for i=1:m a(i)=1/sqrt(2);% 0态系数b(i)=1/sqrt

5、(2); % 1态系数end %MAX=zeros(number,g) % 保持的最高适应度值%BEST=zeros(number,m)% 保持的问题最优解名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - q=zeros(2,m,n);% 定义群体染色体for j=1:n for i=1:m q(:,i,j)=a(i),b(i);%单个染色体。即q(1,i,j) 为第 j 个染色体的第i 位的 0态系数，%q(1,i,j) 为第

6、j 个染色体的第i 位的 1态系数end end functionq=initialize(n,m) t=0; while tq(1,i,j)2 % 如果 ra(i,j)2, 则该位二进制串置为1，即取该物品x(j,i)=1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - else x(j,i)=0;% 该为二进制串置为0，即不取该物品end end end plot(x); %repair 修改超重的问题解，即选择的物品重量

7、不能超过限重C functionoverfiled=repair(n,m,k,x,C) overfiled=0;% 不超重n=100; m=50; x=zeros(n,m); w=80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1; %物品重量c=1000; C=sum(w)/2;% 限制重量for j=1:n if sum(x(j,:)*w)C %超重ov

8、erfiled=1;% 超重符号end while overfiled k=fix(1+rand()*(m-1);%选择其中一个物品放弃,fix 是求最接近0 的整数x(j,k)=0; if sum(x(j,:)*w)C % 超重了overfiled=1; end end x(j,k)=0;% 将刚才选择后导致超重的那个物品丢弃x(j,:); end plot(k,fix(k); hold on; plot(k); plot(x); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3

9、 页，共 7 页 - - - - - - - - - %evaluate 评估%fit=zeros(1,n); functionf,v=observe(n,m,p) n=100; m=50; x=zeros(n,m); p=220,208,198,192,108,108,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1; %物品价值for j=1:n %n 个

10、个体for i=1:m %m 位。即 m 个物品fit(j)=sum(x(j,:)*p);%问题解的适应度，即选择物品的总价值end end %for j=n:-1:2 %if fit(j)fit(j-1) % t=fit(j); %fit(j)=fit(j-1); % fit(j-1)=t; % end %end f,v=max(fit);%f位 fit 中的最大值，v 为最大 fit 的位置，即本代最优解的对应序号g=100; t=1:g; if t=0 ave0(n)=mean(fit); else ave(n,t)=mean(fit); end plot(f,t); hold on;

11、plot(f); % update 量子门更新策略functionsign,BEST,angle,q=update(n,m,t,z) n=100; m=50; g=100; t=1:g; for j=1:n %n 个个体，依次更新if t=1 if fit(j)=MAX0(number); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - sign=1; else sign=0; end elseif fit(j)=MAX(num

12、ber,t-1)%本代的最优解比上代保持的最优解sign=1; else sign=0; end i=0; while i0 %上代保持的最优解此位为 1 ，且新解比上代保持的最优解适应度%值高，且新解的0态、1态系数同号，即在一、三象限angle=-0.05*pi;% 顺时针旋转，使下一代系数更靠近0态elseif q(2,i,j)=0 % 上代保持的最优解此位为1 ，且新解比上代保持的最优解适应度值高，%且新解在实轴上，即b(i) 即 0态，不旋转angle=0; else angle=0.05*pi;% 新解比上代保持的最优解适应度高，还包括两种情况，%一是新解在虚轴上，即a(i)处于

13、1态，此时无论顺时针还是逆时针旋转%都可以，使下个状态更靠近0态，本程序使用顺指针逆时针旋转，%第二种情况是在二四象限，此时必须逆时针旋转end elseif BEST(n,i)=0 % 新解状态为1，且保持的最优解状态为0 if sign=0 % 新解适应度值小于保持的最优解适应度值if q(1,i,j)*q(2,i,j)0%一三象限，所以顺时针旋转angle=-0.01*pi; elseif q(2,i,j)=0 % 新解适应度值小于保持的最优值，且新解在实轴上，不旋转？angle=0; else %两种情况。一是新解在虚轴上，即在1态，顺时针逆时针%旋转都可，本程序使用逆时针旋转，二是在

14、三名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 四象限，逆时针旋转angle=0.01*pi; end elseif q(1,i,j)*q(2,i,j)0 %新解为 1，保持的最优解为0，且新解适应度值比保持的最优解高，%且在一三象限，所以逆时针旋转angle=0.025*pi; elseif q(1,i,j)=0 %新解为 1，保持的最优解为0，且新解适应度值比保持的最优解高，新解在虚轴上，不旋转angle=0; else

15、%新解为 1， 保持的最优解为0， 且新解适应度值比保持的最优解高，两种情况%一是新解在虚轴上，顺时针逆时针旋转都可，本程序使用顺时针旋转，二是在三四象限，顺时针旋转angle=-0.025*pi; end elseif sign=0% 新解和保持的最优解都是1， 且新解适应度值小于保持最优解if q(1,i,j)*q(2,i,j)0 %一三象限，逆时针旋转？angle=0.005*pi; elseif q(1,i,j)=0 %新解在虚轴上angle=0; else %两种情况。一是新解在实轴上，逆时针顺时针旋转都可，本程序采用顺时针，二是三四象限，顺时针旋转angle=-0.005*pi;

16、end elseif q(1,i,j)*q(2,i,j)0 %新解和保持的最优解都是1，且新解适应度值高于保持最优解 ,逆时针旋转angle=0.025*pi; elseif q(1,i,j)=0 %新解和保持的最优解都是1，且新解适应度值高于保持最优解，且新解在虚轴上，不旋转angle=0; else %新解和保持的最优解都是1，且新解适应度值高于保持最优解。包括两种情况%一是新解在实轴上，逆时针旋转顺时针旋转都可以。本程序采用顺时针旋转%二是在二四象限，顺时针旋转angle=-0.025*pi; end z=cos(angle),-sin(angle);sin(angle),cos(ang

17、le)*q(1,i,j),q(2,i,j);%采用量子门更新q(1,i,j)=z(1);q(2,i,j)=z(2);%新的 0态、1态系数end end 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - %store functionMAX,BEST=store(f,v,t) g=100; t=1:g; xdatain=-1:1; ydatain=-1:1; if t=0 %第一次观测，即初始化观测MAX0(number)=f;

18、BEST(number,:)=x(v,:); elseif t=1 % 循环中的第一代if fitMAX0(number) %,如果本代最优解比初始化的最优解适应度高，则第一代保持的最优解即为本代最优解MAX(number,t)=fit; BEST(number,:)=x(v,:); else MAX(number,t)=MAX0(number); BEST(number,:)=BEST(number,:); end elseif fitMAX(number,t-1) %循环中本代最优解比上代保持的最优解适应度高，则本代最优解为本代保持的最优解MAX(number,t)=fit; BEST(number,:)=x(v,:); else MAX(number,t)=MAX(number,t-1);%循环中本代最优解比上代保持的最优解适应度低，则本代保持的最优解认为上代保持的最优解BEST(number,:)=BEST(number,:); end 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -