matlab 遺傳優化算法_【優化求解】遺傳算法解決背包問題

問題描述

背包問題

為了簡單起見，我此處隻介紹01背包問題。當然其實01背包問題用動态規劃很容易就能實作。但遺傳算法的意義卻絕不是動态規劃可以代替的。動态規劃隻能解決一些一定有明确解的問題，但事實上現在主流問題很少是有明确解的，大多數都是優化問題，也就是隻能尋找局部最優解，并認為局部最優解已經足夠好了。

clearclcpopsize=100; %種群大小n=7;CW=120; %背包大小 可容納的總重量w=[40 40 30 5 15 35 30]; %各個物品的重量，7個個體v=[30 60 25 8 10 40 60]; %各個物品的價值，7個個體t=200;%疊代次數pc=0.9; %交叉率pm=0.05; %變異率pop=initpop(popsize,n); %産生初始種群for i=1:popsize[objvalue]=calobjvalue(pop,n,popsize,v,w,CW); %計算目标函數[fitvalue]=calfitvalue(objvalue); %計算群體中每個個體的适應度[newpop]=selection(pop,fitvalue); %進行選擇計算[newpop1]=crossover(newpop,pc); %進行交叉計算[newpop2]=mutation(newpop1,pm); %進行變異計算[newobjvalue]=newcalobjvalue(newpop2,n,popsize,v,w,CW); %計算最新代目标函數值，經過選擇交叉變異後的下一代[newfitvalue]=newcalfitvalue(newobjvalue); %計算最新代的個體适應度[bestweight,bestvalue,point]=best(newpop2,newfitvalue,w); %計算最優個體重量，價值，和位置 y(i)=max(bestvalue);%記錄最大價值g(i)=max(bestweight);%記錄最大重量n(i)=i;%記錄位置pop=newpop2;%疊代重複endi=1:100;plot(y(i),'-b*')xlabel('疊代次數')ylabel('最大價值');title('最優點變化趨勢');legend('最優點');grid on[z index]=max(y);po=n(index)%最優代數位置W=g(index)%最優重量chose=(point./w==1)     %選擇的物品V=z%最優價值
           

function [bestweight,bestvalue,point]=best(newpop2,newfitvalue,w)%尋找最優個體，包括其重量和價值。[px,py]=size(newpop2);bestvalue=newfitvalue(1);for i=2:pxif newfitvalue(i)>bestvaluebestvalue=newfitvalue(i);endend[z index]=max(newfitvalue);%計算最優價值，和最優重量。bestweight=0;point=[];for i=index;for j=1:pybestweight=w(j)*newpop2(i,j)+bestweight;endpoint=[point;newpop2(index,:).*w];end
           

function [fitvalue]=calfitvalue(objvalue)% 計算個體的适應值%遺傳算法子程式%Name:calfitvalue.mfitvalue=objvalue;
           

function [newpop1]=crossover(newpop,pc)%交叉%遺傳算法子程式%Name: crossover.m[px,py]=size(newpop);newpop1=zeros(px,py);for i=1:2:px-1ps=rand;if pscpoint=round(rand*py);newpop1(i,:)=[newpop(i,1:cpoint),newpop(i+1,cpoint+1:py)];newpop1(i+1,:)=[newpop(i+1,1:cpoint),newpop(i,cpoint+1:py)];elsenewpop1(i,:)=newpop(i,:);newpop1(i+1,:)=newpop(i+1,:);endend
           

function pop=initpop(popsize,n)%生成初始種群%遺傳算法子程式%Name: initpop.mpop=round(rand(popsize,n));
           

function [newfitvalue]=newcalfitvalue(newobjvalue)% 計算新一代的個體的适應值%遺傳算法子程式%Name:newcalfitvalue.mnewfitvalue=newobjvalue;% function [newobjvalue]=newcalobjvalue(newpop2,n,popsize,v,w,CW)% %計算新一代的目标函數值% [px,py]=size(newpop2);% for i=1:px% sum(i)=0;% sum1(i)=0;% for j=1:py% sum(i)=sum(i)+v(j)*newpop2(i,j);% sum1(i)=sum1(i)+w(j)*newpop2(i,j);% end% if sum1(i)>CW% sum(i)=0;% else% sum(i)=sum(i);% end% newobjvalue(i)=sum(i);% end
           

function [newobjvalue]=newcalobjvalue(newpop2,n,popsize,v,w,CW)%計算新一代的目标函數值[px,py]=size(newpop2);for i=1:pxsum(i)=0;sum1(i)=0;for j=1:pysum(i)=sum(i)+v(j)*newpop2(i,j);sum1(i)=sum1(i)+w(j)*newpop2(i,j);endif sum1(i)>CWsum(i)=0;elsesum(i)=sum(i);endnewobjvalue(i)=sum(i);end
           

function [newpop]=selection(pop,fitvalue)%選擇操作 ，輪盤賭的選擇方法totalfit=sum(fitvalue);%求适應度值之和pfitvalue=fitvalue/totalfit;%單個個體被選擇的機率mfitvalue=cumsum(pfitvalue); %如 fitvalue=[1 2 3 4]，則 cumsum(fitvalue)=[1 3 6 10][px,py]=size(pop);ms=sort(rand(px,1)); %從小到大排列fitin=1;newin=1;newpop=zeros(size(pop));while newin<=pxif mfitvalue(fitin)>ms(newin)newpop(newin,:)=pop(fitin,:);newin=newin+1;elsefitin=fitin+1;endend
           

往期回顧>>>>>>

【模式識别】Matlab指紋識别【優化求解】A*算法解決三維路徑規劃問題  matlab自動識别銀行卡号【優化求解】模拟退火遺傳實作帶時間窗的車輛路徑規劃問題【數學模組化】Matlab實作SEIR模型【優化求解】基于NSGA-2的求解多目标柔性工廠中的房間排程算法【優化求解】蟻群算法求最優值 分享朋友圈獲贊10即可擷取該源碼