量子遺傳算法求解背包問題程序

%qgan=100;%群體規(guī)模g=100;%進(jìn)化代數(shù)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,;%物品重量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];%物品價值%clfclearglobalmn;%全局變量，m為染色體串長，即背包問題中的物品數(shù)量，n為群體規(guī)模m=input('pleaseinputchromsomelengthm=:');%輸入串長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,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;savemwpCmwpC%knapsackclfclearglobalmn;%全局變量，m為染色體串長，即背包問題中的物品數(shù)量，n為群體規(guī)模m=input('pleaseinputchromsomelengthm=:');%輸入串長fori=1:mw(i)=1+rand()*9;%物品重量p(i)=w(i)+5; %物品價值endC=sum(w)/2;%限制重量w,psavemwpcmwpC%保留數(shù)據(jù)，重復(fù)試驗使用相同的數(shù)據(jù)%初始化群體，規(guī)模1，染色體位數(shù)10，%n=input('pleaseinputpopulationsizen=:');%群體規(guī)模%g=input('pleaseinputmax-generationg=:');%進(jìn)化代數(shù)fori=1:ma(i)=1/sqrt(2);%‘0’態(tài)系數(shù)b(i)=1/sqrt(2);%‘1’態(tài)系數(shù)end%MAX=zeros(number,g)%保持的最高適應(yīng)度值%BEST=zeros(number,m)%保持的問題最優(yōu)解q=zeros(2,m,n);%定義群體染色體forj=1:nfori=1:mq(:,i,j)=[a(i),b(i)]';%單個染色體。即q(1,i,j)為第j個染色體的第i位的‘0’態(tài)系數(shù)，%q(1,i,j)為第j個染色體的第i位的‘1’態(tài)系數(shù)endendfunction[q]=initialize(n,m)t=0;whilet<g%進(jìn)化循環(huán)t=t+1;observe;repair;evaluate;update;%量子門更新，產(chǎn)生下一代的量子態(tài)染色體store;endendfort=1:gmaxqga10(t)=mean(MAX(:,t));aveqga10(t)=mean(ave(:,t));endsavedata/datamaxqga10aveqga10fornumber=1:30plot(MAX(number,:));endplot(maxqga10,'r-');holdon;plot(aveqga10);%observe%x=zeros(n,m)function[x]=observe(n,m,q)n=100;m=50;q=zeros(2,m,n);%定義群體染色體forj=1:n%共有n個個體fori=1:m%每個個體為m位r=rand();ifr>q(1,i,j)A2%如果r>a(i,j)A2,則該位二進(jìn)制串置為1，即取該物品x(j,i)=1;elsex(j,i)=0;%該為二進(jìn)制串置為0,即不取該物品endendendplot(x);%repair修改超重的問題解，即選擇的物品重量不能超過限重Cfunction[overfiled]=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,;%物品重量c=1000;C=sum(w)/2;%限制重量forj=1:nifsum(x(j,:)*w')>C%超重overfiled=1;%超重符號endwhileoverfiledk=fix(1+rand()*(m-1));%選擇其中一個物品放棄,fix是求最接近0的整數(shù)x(j,k)=0;ifsum(x(j,:)*w')<=C%不超重了overfiled=0;endendwhile~overfiled%不超重k=fix(1+rand()*(m-1));%盡可能的再多選一個物品x(j,k)=1;ifsum(x(j,:)*w')>C%超重了overfiled=1;endendx(j,k)=0;%將剛才選擇后導(dǎo)致超重的那個物品丟棄x(j,:);endplot(k,fix(k));holdon;plot(k);plot(x);%evaluate評估%fit=zeros(1,n);function[f,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]; %物品價值forj=1:n%n個個體fori=1:m%m位。即m個物品fit(j)=sum(x(j,:)*p');%問題解的適應(yīng)度，即選擇物品的總價值endend%forj=n:-1:2%iffit(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的位置，即本代最優(yōu)解的對應(yīng)序號g=100;t=1:g;ift==0ave0(n)=mean(fit);elseave(n,t)=mean(fit);endplot(f,t);holdon;plot(f);%update量子門更新策略function[sign,BEST,angle,q]=update(n,m,t,z)n=100;m=50;g=100;t=1:g;forj=1:n%n個個體，依次更新ift==1iffit(j)>=MAX0(number);sign=1;elsesign=0;endelseif fit(j)>=MAX(number,t-1)%本代的最優(yōu)解比上代保持的最優(yōu)解sign=1;elsesign=0;endi=0;whilei<m%n位i=i+1;ifx(j,i)==0%新解此位狀態(tài)為‘0’，即第j個個體的第i位為0ifBEST(number,i)==0%上代保持的最優(yōu)解此位為0angle=0;%不旋轉(zhuǎn)elseifsign==0%上代保持的最優(yōu)解此位為‘1’，且新解不如上代保持的最優(yōu)解適應(yīng)度值高angle=0;%不旋轉(zhuǎn)elseifq(1,i,j)*q(2,i,j)>0%上代保持的最優(yōu)解此位為T，且新解比上代保持的最優(yōu)解適應(yīng)度%值高，且新解的‘0’態(tài)、‘1’態(tài)系數(shù)同號，即在一、三象限angle=-0.05*pi;%順時針旋轉(zhuǎn)，使下一代系數(shù)更靠近‘0’態(tài)elseifq(2,i,j)==0%上代保持的最優(yōu)解此位為‘1’，且新解比上代保持的最優(yōu)解適應(yīng)度值高，%且新解在實軸上，即b(i)即‘0’態(tài)，不旋轉(zhuǎn)angle=0;elseangle=0.05*pi;%新解比上代保持的最優(yōu)解適應(yīng)度高，還包括兩種情況，%一是新解在虛軸上，即a(i)處于‘1’態(tài)，此時無論順時針還是逆時針旋轉(zhuǎn)%都可以，使下個狀態(tài)更靠近‘0’態(tài)，本程序使用順指針逆時針旋轉(zhuǎn)，%第二種情況是在二四象限，此時必須逆時針旋轉(zhuǎn)endelseifBEST(n,i)==0%新解狀態(tài)為1，且保持的最優(yōu)解狀態(tài)為0ifsign==0%新解適應(yīng)度值小于保持的最優(yōu)解適應(yīng)度值ifq(1,i,j)*q(2,i,j)>0%一三象限，所以順時針旋轉(zhuǎn)angle=-0.01*pi;elseifq(2,i,j)==0%新解適應(yīng)度值小于保持的最優(yōu)值，且新解在實軸上，不旋轉(zhuǎn)？？angle=0;else%兩種情況。一是新解在虛軸上，即在‘1’態(tài)，順時針逆時針%旋轉(zhuǎn)都可，本程序使用逆時針旋轉(zhuǎn)，二是在三四象限，逆時針旋轉(zhuǎn)angle=0.01*pi;endelseifq(1,i,j)*q(2,i,j)>0%新解為1，保持的最優(yōu)解為0，且新解適應(yīng)度值比保持的最優(yōu)解高，%且在一三象限，所以逆時針旋轉(zhuǎn)angle=0.025*pi;elseifq(1,i,j)==0%新解為1，保持的最優(yōu)解為0，且新解適應(yīng)度值比保持的最優(yōu)解高，新解在虛軸上，不旋轉(zhuǎn)angle=0;else%新解為1，保持的最優(yōu)解為0，且新解適應(yīng)度值比保持的最優(yōu)解高，兩種情況%一是新解在虛軸上，順時針逆時針旋轉(zhuǎn)都可，本程序使用順時針旋轉(zhuǎn)，二是在三四象限，順時針旋轉(zhuǎn)angle=-0.025*pi;endelseif sign==0%新解和保持的最優(yōu)解都是1，且新解適應(yīng)度值小于保持最優(yōu)解ifq(1,i,j)*q(2,i,j)>0%一三象限，逆時針旋轉(zhuǎn)？angle=0.005*pi;elseifq(1,i,j)==0%新解在虛軸上angle=0;else %兩種情況。一是新解在實軸上，逆時針順時針旋轉(zhuǎn)都可，本程序采用順時針，二是三四象限，順時針旋轉(zhuǎn)angle=-0.005*pi;endelseifq(1,i,j)*q(2,i,j)>0%新解和保持的最優(yōu)解都是1，且新解適應(yīng)度值高于保持最優(yōu)解,逆時針旋轉(zhuǎn)angle=0.025*pi;elseifq(1,i,j)==0 %新解和保持的最優(yōu)解都是1，且新解適應(yīng)度值高于保持最優(yōu)解，且新解在虛軸上，不旋轉(zhuǎn)angle=0;else %新解和保持的最優(yōu)解都是1，且新解適應(yīng)度值高于保持最優(yōu)解。包括兩種情況%一是新解在實軸上，逆時針旋轉(zhuǎn)順時針旋轉(zhuǎn)都可以。本程序采用順時針旋轉(zhuǎn)%二是在二四象限，順時針旋轉(zhuǎn)angle=-0.025*pi;endz=[cos(angle),-sin(angle);sin(angle),cos(angle)]*[q(1,i,j),q(2,i,j)]';%采用量子門更新q(1,i,j)=z(1);q(2,i,j)=z(2);%新的‘0’態(tài)、‘1’態(tài)系數(shù)endend%storefunction[MAX,BEST]=store(f,v,t)g=100;t=1:g;xdatain=[-1:1];ydatain=[-1:1];ift==0 %第一次觀測，即初始化觀測MAX0(number)=f;BEST(number,:)=x(v,:);elseift==1%循環(huán)中的第一代iffit>MAX0(number)%，如果本代最優(yōu)解比初始化的最優(yōu)解適應(yīng)度高，則第一代保持的最優(yōu)解即為本代最優(yōu)解MAX(number,t)=fit;BEST(number,:)=x(v,:);elseMAX(nu