%貪婪算法、遺傳算法解決背包問(wèn)題
%初始化參數(shù)
clear?all;%清除所有變量
close?all;%清圖
clc;%清屏
N=50;%種群數(shù)量
L=50;%二進(jìn)制位串長(zhǎng)度
c=[98?92?95?70?72?70?83?80?65?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?56?50?30?20?15?10?8?5?3?1?];%初始化物品質(zhì)量
value=[300?318?298?192?180?180?265?242?160?138?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?20?25?15?10?20?10?7?5?2?2];%初始化物品價(jià)值
g=value./c;%價(jià)值密度（價(jià)值/重量）貪婪算法
m1=1000;%總重量約束值
v=randi（[01]NL）;%隨機(jī)生成50組初始解50x50
v=greedy（vcgm1）;%貪婪算法修復(fù)解
G=500;%最大遺傳代數(shù)
pc=0.5;%交叉率
pm=0.01;%變異率
nf=zeros（NL）;
%遺傳算法循環(huán)
for?gen=1:G
????fit?=v*value‘;%當(dāng)前解計(jì)算的總價(jià)值50x1
????%選擇個(gè)體
????maxfit=max（fit）;%最大適應(yīng)度值
????minfit=min（fit）;%最小適應(yīng)度值
????rr=find（fit==maxfit）;%返回最大適應(yīng)度值下標(biāo)
????fBest=v（rr（11）:）;%歷代最優(yōu)個(gè)體最優(yōu)染色體編碼
????fitt=（fit-minfit）/（maxfit-minfit）;%歸一化適應(yīng)度值
????%基于輪盤(pán)賭的復(fù)制操作
????sum_fit=sum（fitt）;%種群中所有個(gè)體的適應(yīng)度和
????fitvalue=fitt./sum_fit;%個(gè)體被選中的概率
????fitvalue=cumsum（fitvalue）;%數(shù)組（50x1矩陣）第1列第n行元素是前n行元素的累加和
????ms=sort（rand（N1））;%生成服從均勻分布的隨機(jī)數(shù)50x1的矩陣，并對(duì)其升序排列
????fiti=1;
????newi=1;
????while?newi<=N&&fiti<=N
????????if?（ms（newi））????????????nf（newi:）=v（fiti:）;
????????????newi=newi+1;
????????else
????????????fiti=fiti+1;
????????end
????end
????%基于概率的交叉操作
????for?i=1:2:N%50組數(shù)據(jù)兩兩交叉
????????p=rand;%產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r
????????if?ppc所產(chǎn)生的兩個(gè)子代僅是親代的各自副本
????????????q=randi（[01]1L）;%隨機(jī)生成1x50
????????????for?j=1:L
????????????????if?q（j）==1
????????????????????temp=nf（i+1j）;
????????????????????nf（i+1j）=nf（ij）;
????????????????????nf（ij）=temp;
????????????????end
????????????end
????????end
????end
??%基于概率的變異操作
????i=1;
????while?i<=round（N*pm）%個(gè)體變異數(shù)
????????h=randi（N）;%隨機(jī)選取一個(gè)需要變異的染色體（1~50隨機(jī)選擇）
????????for?j=1:round（L*pm）%基因變異數(shù)
????????????g=randi（L）;%隨機(jī)選取需要變異的基因數(shù)（1~50隨機(jī)選擇）
????????????nf（hg）=~nf（hg）;
????????end
????????i=i+1;
????end
????nf=greedy（nfcgm1）;
????nfit=nf*value‘;%新解計(jì)算的總價(jià)值50x1
????newv=[v;nf];%子代和父代合并100x50
????newfit=[fit;nfit];%子代和父代的適度值合并（100x1）
????[nnewfitIndex]=sort（newfit‘descend‘）;%適度值按降序排列
????sortf=newv（Index:）;%按適度值排列個(gè)體
????nsortf=nnewfit（1:N）;%取前N個(gè)適應(yīng)度值
????nf=sortf（1:N:）;%取前N個(gè)個(gè)體
????v=nf;
????trace（gen）=nsortf（11）;%歷代最優(yōu)適應(yīng)度
end
Bestf=sortf（1:）;%最優(yōu)個(gè)體
trace（end）;%最優(yōu)值
figure
plot（trace）
xlabel（‘迭代次數(shù)‘）
ylabel（‘目標(biāo)函數(shù)值‘）
title（‘適應(yīng)度進(jìn)化曲線‘）

?屬性????????????大小?????日期????時(shí)間???名稱(chēng)
-----------?---------??----------?-----??----
?????文件?????????550??2017-06-14?15:41??greedy.m
?????文件????????2866??2017-06-14?16:34??genetic.m