智能控制理論及應(yīng)用 課件 第11章-11.1遺傳算法

主要內(nèi)容11.1遺傳算法11.2粒子群優(yōu)化算法11.1遺傳算法11.1.1引言11.1.2基本概念11.1.3遺傳算法的具體實(shí)現(xiàn)

11.1.4遺傳算法的運(yùn)算流程總結(jié)

第11章11.1遺傳算法11.1.1引言自適應(yīng)啟發(fā)式搜索算法進(jìn)化算法達(dá)爾文的進(jìn)化論自然選擇中的適者生存孟德?tīng)栠z傳學(xué)理論適者生存基因遺傳第11章11.1.1引言11.1.1引言遺傳算法最早由美國(guó)的J.H.Holland教授及其學(xué)生于1975年提出直到90年代才流行起來(lái)。參考文獻(xiàn)：Holland,J.H.(1992)GeneticAlgorithms.ScientificAmerican,267,66-73./10.1038/scientificamerican0792-66第11章11.1.1引言11.1.2基本概念●Population(種群）：它是給定問(wèn)題所有可能（編碼）解決方案的一個(gè)子集。Individual（個(gè)體）：種群中的一個(gè)解。第11章11.1.2基本概念11.1.2基本概念●Chromosomes（染色體）：染色體是給定問(wèn)題的這樣一個(gè)解。Gene(基因）：基因是染色體上的一個(gè)特定位置。第11章11.1.2基本概念11.1.2基本概念●Fitnessfunction(適應(yīng)度函數(shù))適應(yīng)度即生物群體中個(gè)體適應(yīng)生存環(huán)境的能力。在遺傳算法中，用來(lái)評(píng)價(jià)個(gè)體優(yōu)劣的數(shù)學(xué)函數(shù)，稱為個(gè)體的適應(yīng)度函數(shù)。第11章11.1.2基本概念●GeneticOperators(遺傳操作)包含選擇、交叉、變異三個(gè)主要的操作。第11章11.1.2基本概念11.1.2基本概念適應(yīng)度比例選擇：

p(xi)：選擇概率選擇與復(fù)制對(duì)于一個(gè)包含N個(gè)個(gè)體的種群s，從s中隨機(jī)選擇N個(gè)染色體N次，每次選擇的概率為每個(gè)染色體

xi∈s的選擇概率p(xi)。第11章11.1.2基本概念交叉交換兩個(gè)父代的部分基因

二進(jìn)制編碼交叉單點(diǎn)交叉兩點(diǎn)交叉多點(diǎn)交叉均勻交叉

實(shí)數(shù)編碼交叉第11章11.1.2基本概念交叉單點(diǎn)交叉

兩點(diǎn)交叉第11章11.1.2基本概念交叉多點(diǎn)交叉均勻交叉第11章11.1.2基本概念變異染色體的隨機(jī)變化。二進(jìn)制變異：位翻轉(zhuǎn)

單點(diǎn)變異

多點(diǎn)變異實(shí)值變異：用值域內(nèi)的隨機(jī)值替換原基因值（隨機(jī)重置）第11章11.1.2基本概念變異二進(jìn)制變異：位翻轉(zhuǎn)

單點(diǎn)變異

多點(diǎn)變異第11章11.1.2基本概念使用遺傳算法來(lái)求函數(shù)y=x2在區(qū)間[0,31]上的最大值。y=x2

31

XY11.1.3遺傳算法的具體實(shí)現(xiàn)第11章11.1.3遺傳算法的具體實(shí)現(xiàn)解:(1)初始化:確定種群大小:4編碼:5位二進(jìn)制隨機(jī)生成初始種群:

s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(2)定義適應(yīng)度函數(shù):f(x)=x2

第11章11.1.3遺傳算法的具體實(shí)現(xiàn)解:(3)計(jì)算當(dāng)前代的適應(yīng)度值s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)它們的適應(yīng)度值分別為

f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361第11章11.1.3遺傳算法的具體實(shí)現(xiàn)解:(4)執(zhí)行遺傳操作選擇操作:計(jì)算每個(gè)個(gè)體的選擇概率P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31

f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361第11章11.1.3遺傳算法的具體實(shí)現(xiàn)s40.31s20.49s10.14s30.06●roulette-wheel

selection

algorithm賭輪選擇法第11章11.1.3遺傳算法的具體實(shí)現(xiàn)在[0,1]之間隨機(jī)生成4個(gè)隨機(jī)數(shù)，如：

r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503染色體適應(yīng)值選擇概率累積概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001第11章11.1.3遺傳算法的具體實(shí)現(xiàn)因此，在選擇之后，我們得到了以下種群：s1’=11000（24）,s2’=01101（13）s3’=11000（24）,s4’=10011（19）第11章11.1.3遺傳算法的具體實(shí)現(xiàn)交叉假設(shè)

pc=100%讓s1'和s2'成對(duì),s3'和s4'成對(duì)。分別交換各自的最后兩個(gè)基因以獲得新的染色體：

s1’=11000（24）,s2’=01101（13）s3’=11000（24）,s4’=10011（19）s1’’=11001（25）,s2’’=01100（12）s3’’=11011（27）,s4’’=10000（16）第11章11.1.3遺傳算法的具體實(shí)現(xiàn)變異設(shè)置變異概率

pm=0.001。

因此，在種群中只有0.02的基因可能會(huì)發(fā)生突變。

5×4×0.001=0.02顯然0.02<1，因此，在這一輪的變異操作中沒(méi)有變異發(fā)生。第11章11.1.3遺傳算法的具體實(shí)現(xiàn)從而得到第二代種群S2

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）第11章11.1.3遺傳算法的具體實(shí)現(xiàn)第二代染色體適應(yīng)值選擇概率累積概率s1=110016250.360.36s2=011001440.080.44s3=110117290.410.85s4=100002560.151.00第11章11.1.3遺傳算法的具體實(shí)現(xiàn)

假設(shè)在這一輪的選擇-繁殖操作中，種群S2中的所有4個(gè)染色體都被選中s1’=11001（25）,s2’=01100（12）

s3’=11011（27）,s4’=10000（16）

交叉：

讓s1'和s2',s3'和s4'分別交換它們各自最后三個(gè)基因s1’’=11100（28）,s2’’=01001（9）

s3’’=11000（24）,s4’’=10011（19）

在這輪中沒(méi)有發(fā)生變異第11章11.1.3遺傳算法的具體實(shí)現(xiàn)第三代種群S3被衍生出來(lái)。s1=11100（28）,s2=01001（9）

s3=11000（24）,s4=10011（19）

第11章11.1.3遺傳算法的具體實(shí)現(xiàn)

第三代染色體適應(yīng)值選擇概率累積概率s1=111007840.440.44s2=01001810.040.48s3=110005760.320.80s4=100113610.201.00第11章11.1.3遺傳算法的具體實(shí)現(xiàn)假設(shè)選擇-繁殖后的種群是:

s1’=11100（28）,s2’=11100（28）

s3’=11000（24）,s4’=10011（19）交叉:

讓s1'和s2’,s3'和s4'分別交換最后兩個(gè)基因s1’’=11111（31）,s2’’=11100（28）

s3’’=11000（24）,s4’’=10000（16）

這輪沒(méi)有發(fā)生變異第11章11.1.3遺傳算法的具體實(shí)現(xiàn)因此，我們得到了第四代S4：

s1=11111（31）,s2=11100（28）

s3=11000（24）,s4=10000（16）

第11章11.1.3遺傳算法的具體實(shí)現(xiàn)YYy=x2

8131924

X第一代y=x2

12162527

XY第二代y=x2

9192428

XY第三代y=x2

16242831

X第四代第11章11.1.3遺傳算法的具體實(shí)現(xiàn)11.1.4

遺傳算法的運(yùn)算流程第11章11.1.4遺傳算法的運(yùn)算流程11.1.4

遺傳算法的運(yùn)算流程第11章11.1.4遺傳算法的運(yùn)算流程11.1.5仿真示例【例11.1】用遺傳算法求下列函數(shù)的最大值。第11章11.1.5仿真示例MATLAB代碼%初始化參數(shù)clearall;%清除所有變量closeall;%關(guān)閉圖形clc;%清屏NP=50;%種群數(shù)量L=20;%二進(jìn)制數(shù)串長(zhǎng)度Pc=0.8;%交叉率Pm=0.1;%變異率G=50;%最大遺傳代數(shù)Xs=10;%自變量的上限Xx=0;%自變量的下限f=randi([0,1],NP,L);%隨機(jī)獲得初始種群%%%%%%%%%%%%%%%%%%%%%%%%%遺傳算法循環(huán)第11章11.1.5仿真示例MATLAB代碼%%%%%%%%%%%%將二進(jìn)制解碼為定義域范圍內(nèi)十進(jìn)制%%%%%%%%%%%%%%fori=1:NPU=f(i,:);m=0;forj=1:Lm=U(j)*2^(j-1)+m;endx(i)=Xx+m*(Xs-Xx)/(2^L-1);Fit(i)=func1(x(i));endmaxFit=max(Fit);%最大值

minFit=min(Fit);%最小值

rr=find(Fit==maxFit);fBest=f(rr(1,1),:);%歷代最優(yōu)個(gè)體

xBest=x(rr(1,1));Fit=(Fit-minFit)/(maxFit-minFit);%歸一化適應(yīng)度值第11章11.1.5仿真示例MATLAB代碼Fit=(Fit-minFit)/(maxFit-minFit);%歸一化適應(yīng)度值

%%%%%%%%%%%%%%%%%%基于輪盤賭的選擇操作%%%%%%%%%%%%%%%%%%%sum_Fit=sum(Fit);fitvalue=Fit./sum_Fit;fitvalue=cumsum(fitvalue);ms=sort(rand(NP,1));fiti=1;newi=1;whilenewi<=NPif(ms(newi))<fitvalue(fiti)nf(newi,:)=f(fiti,:);newi=newi+1;elsefiti=fiti+1;endend第11章11.1.5仿真示例MATLAB代碼%%%%%%%%%%%%%%%%%%%%%%基于概率的交叉操作fori=1:2:NPp=rand;ifp<Pcq=randi([0,1],1,L);forj=1:Lifq(j)==1temp=nf(i+1,j);nf(i+1,j)=nf(i,j);nf(i,j)=temp;endendendend第11章11.1.5仿真示例MATLAB代碼%%%%%%%%%%%%%%%%%%%基于概率的變異操作i=1;whilei<=round(NP*Pm)h=randi([1,NP],1,1);%隨機(jī)選取一個(gè)需要變異的染色體

forj=1:round(L*Pm)