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

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

11.1.4遺傳算法的運算流程總結

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

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

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

二進制編碼交叉單點交叉兩點交叉多點交叉均勻交叉

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

兩點交叉第11章11.1.2基本概念交叉多點交叉均勻交叉第11章11.1.2基本概念變異染色體的隨機變化。二進制變異：位翻轉

單點變異

多點變異實值變異：用值域內的隨機值替換原基因值（隨機重置）第11章11.1.2基本概念變異二進制變異：位翻轉

單點變異

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

31

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

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

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

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

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

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遺傳算法的具體實現(xiàn)解:(4)執(zhí)行遺傳操作選擇操作:計算每個個體的選擇概率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遺傳算法的具體實現(xiàn)s40.31s20.49s10.14s30.06●roulette-wheel

selection

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

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

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

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遺傳算法的具體實現(xiàn)變異設置變異概率

pm=0.001。

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

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

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

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

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

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

交叉：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8131924

X第一代y=x2

12162527

XY第二代y=x2

9192428

XY第三代y=x2

16242831

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

遺傳算法的運算流程第11章11.1.4遺傳算法的運算流程11.1.4

遺傳算法的運算流程第11章11.1.4遺傳算法的運算流程11.1.5仿真示例【例11.1】用遺傳算法求下列函數(shù)的最大值。第11章11.1.5仿真示例MATLAB代碼%初始化參數(shù)clearall;%清除所有變量closeall;%關閉圖形clc;%清屏NP=50;%種群數(shù)量L=20;%二進制數(shù)串長度Pc=0.8;%交叉率Pm=0.1;%變異率G=50;%最大遺傳代數(shù)Xs=10;%自變量的上限Xx=0;%自變量的下限f=randi([0,1],NP,L);%隨機獲得初始種群%%%%%%%%%%%%%%%%%%%%%%%%%遺傳算法循環(huán)第11章11.1.5仿真示例MATLAB代碼%%%%%%%%%%%%將二進制解碼為定義域范圍內十進制%%%%%%%%%%%%%%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)個體

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

%%%%%%%%%%%%%%%%%%基于輪盤賭的選擇操作%%%%%%%%%%%%%%%%%%%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);%隨機選取一個需要變異的染色體

forj=1:round(L*Pm)