計算智能與深度學習 課件 4遺傳算法-2

第4章遺傳算法（續(xù)）

4.1遺傳算法簡介

4.1.1遺傳算法的產(chǎn)生與發(fā)展

4.1.2生物進化理論和遺傳學的基本知識

4.1.3遺傳算法的思路與特點

4.1.4遺傳算法的基本操作

4.1.5遺傳算法的應用4.2基本遺傳算法

4.2.1簡單函數(shù)優(yōu)化的實例

4.2.2遺傳基因型

4.2.3適應度函數(shù)及其尺度變換

4.2.4遺傳操作——選擇

4.2.5遺傳操作——交叉/基因重組

4.2.6遺傳操作——變異

4.2.7算法的設計與實現(xiàn)

4.2.8模式定理4.3遺傳算法的改進

4.3.1CHC算法

4.3.2自適應遺傳算法

4.3.3基于小生境技術的遺傳算法4.4遺傳算法的應用

4.4.1解決帶約束的函數(shù)優(yōu)化問題

4.4.2解決多目標優(yōu)化問題

4.4.3解決組合優(yōu)化問題

4.4.4遺傳算法在過程建模中的應用

4.4.5遺傳算法在模式識別中的應用4.2基本遺傳算法

問題的提出一元函數(shù)求最大值：4.2.1簡單函數(shù)優(yōu)化的實例

4.2基本遺傳算法

問題的提出用微分法求取f(x)的最大值：解有無窮多個：4.2.1簡單函數(shù)優(yōu)化的實例

4.2基本遺傳算法

問題的提出當i為奇數(shù)時xi對應局部極大值點，i為偶數(shù)時xi對應局部極小值。x19即為區(qū)間[-1,2]內的最大值點：此時，函數(shù)最大值f(x19)比f(1.85)=3.85稍大。4.2.1簡單函數(shù)優(yōu)化的實例

4.2基本遺傳算法

編碼表現(xiàn)型：x

基因型：二進制編碼（串長取決于求解精度）

串長與精度之間的關系：若要求求解精度到6位小數(shù)，區(qū)間長度為2-(-1)＝3，即需將區(qū)間分為3/0.000001=3×106等份。所以編碼的二進制串長應為22位。4.2.1簡單函數(shù)優(yōu)化的實例

4.2基本遺傳算法

產(chǎn)生初始種群產(chǎn)生的方式：隨機產(chǎn)生的結果：長度為22的二進制串產(chǎn)生的數(shù)量：種群的大小（規(guī)模），如30，50，…111101001110000101100011001100111010101011101010100011110010000100101111001001110011100100011001010011000000110000011010010000000000……4.2.1簡單函數(shù)優(yōu)化的實例

4.2基本遺傳算法

計算適應度不同的問題有不同的適應度計算方法本例：直接用目標函數(shù)作為適應度函數(shù)①將某個體轉化為[-1,2]區(qū)間的實數(shù)：

s=<1000101110110101000111>→x=0.637197②計算x的函數(shù)值（適應度）：

f(x)=xsin(10πx)+2.0=2.5863454.2.1簡單函數(shù)優(yōu)化的實例

4.2基本遺傳算法

計算適應度

二進制與十進制之間的轉換：第一步，將一個二進制串（b21b20…b0）轉化為10進制數(shù)：第二步，x’對應的區(qū)間[-1,2]內的實數(shù)：4.2.1簡單函數(shù)優(yōu)化的實例

(0000000000000000000000)→-1(1111111111111111111111)→24.2基本遺傳算法

遺傳操作選擇：輪盤賭選擇法；交叉：單點交叉；變異：小概率變異4.2.1簡單函數(shù)優(yōu)化的實例

4.2基本遺傳算法

模擬結果

設置的參數(shù)：種群大小50；交叉概率0.75；變異概率0.05；最大代數(shù)200。

得到的最佳個體：

smax=<1111001100111011111100>;xmax=1.8506;f(xmax)=3.8503;4.2.1簡單函數(shù)優(yōu)化的實例

4.2基本遺傳算法

模擬結果

進化的過程：4.2.1簡單函數(shù)優(yōu)化的實例

世代數(shù)自變量適應度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.85034.2基本遺傳算法

編碼原則完備性（completeness）：問題空間的所有解都能表示為所設計的基因型；健全性（soundness）：任何一個基因型都對應于一個可能解；非冗余性（non-redundancy）：問題空間和表達空間一一對應。4.2.2遺傳基因型

4.2基本遺傳算法

多種編碼方式二進制編碼；浮點數(shù)編碼；格雷碼編碼；符號編碼；復數(shù)編碼；DNA編碼等。4.2.2遺傳基因型

4.2基本遺傳算法

二進制編碼與浮點數(shù)編碼的比較在交叉操作時，二進制編碼比浮點數(shù)編碼產(chǎn)生新個體的可能性多，而且產(chǎn)生的新個體不受父個體所構成的超體的限制；在變異操作時，二進制編碼的種群穩(wěn)定性比浮點數(shù)編碼差。4.2.2遺傳基因型

4.2基本遺傳算法

適應度函數(shù)的重要性適應度函數(shù)的選取直接影響遺傳算法的收斂速度以及能否找到最優(yōu)解。一般而言，適應度函數(shù)是由目標函數(shù)變換而成的，對目標函數(shù)值域的某種映射變換稱為適應度的尺度變換（fitnessscaling）。4.2.3適應度函數(shù)及其尺度變換

4.2基本遺傳算法

幾種常見的適應度函數(shù)直接轉換若目標函數(shù)為最大化問題：Fit(f(x))=f(x)

若目標函數(shù)為最小化問題：Fit(f(x))=-f(x)4.2.3適應度函數(shù)及其尺度變換

4.2基本遺傳算法

幾種常見的適應度函數(shù)界限構造法1

若目標函數(shù)為最大化問題：若目標函數(shù)為最小化問題：4.2.3適應度函數(shù)及其尺度變換

4.2基本遺傳算法

幾種常見的適應度函數(shù)界限構造法2

若目標函數(shù)為最大化問題：若目標函數(shù)為最小化問題：

c為目標函數(shù)的保守估計值。4.2.3適應度函數(shù)及其尺度變換

4.2基本遺傳算法

適應度函數(shù)的作用適應度函數(shù)設計不當有可能出現(xiàn)欺騙問題：（1）進化初期，個別超常個體控制選擇過程；（2）進化末期，個體差異太小導致陷入局部極值。4.2.3適應度函數(shù)及其尺度變換

4.2基本遺傳算法

適應度函數(shù)的設計單值、連續(xù)、非負、最大化合理、一致性計算量小通用性強4.2.3適應度函數(shù)及其尺度變換

4.2基本遺傳算法

適應度函數(shù)的線性變換法

f’=α*f+β

系數(shù)的確定滿足以下條件：①f’avg=favg②f’max=cmultf’avg

cmult=1.0~2.04.2.3適應度函數(shù)及其尺度變換

4.2基本遺傳算法

適應度函數(shù)的冪函數(shù)變換法

f’=fk

k與所求優(yōu)化相關4.2.3適應度函數(shù)及其尺度變換

k4.2基本遺傳算法

適應度函數(shù)的指數(shù)變換法

f’=e-af

a決定了復制的強制性，其值越小，復制的強制性就越趨向于那些具有最大適應性的個體。4.2.3適應度函數(shù)及其尺度變換

α4.2基本遺傳算法

幾個概念選擇壓力（selectionpressure）:最佳個體選中的概率與平均個體選中概率的比值；偏差（bias）：個體正規(guī)化適應度與其期望再生概率的絕對差值；個體擴展（spread）：單個個體子代個數(shù)的范圍；多樣化損失（lossofdiversity）：在選擇階段未選中個體數(shù)目占種群的比例；4.2.4遺傳操作——選擇

4.2基本遺傳算法

幾個概念選擇強度（selectionintensity）:將正規(guī)高斯分布應用于選擇方法，期望平均適應度；選擇方差（selectionvariance）：將正規(guī)高斯分布應用于選擇方法，期望種群適應度的方差。4.2.4遺傳操作——選擇

4.2基本遺傳算法

個體選擇概率的常用分配方法按比例的適應度分配（proportionalfitnessassignment）某個體i，其適應度為fi，則其被選取的概率Pi為：4.2.4遺傳操作——選擇

個體ff2P12.56.250.1821.01.000.0333.09.000.2641.21.440.0452.14.410.1360.80.640.0272.56.250.1881.31.690.0590.90.810.02101.83.240.094.2基本遺傳算法

個體選擇概率的常用分配方法基于排序的適應度分配（rank-basedfitnessassignment）線性排序（byBaker）

μ為種群大小，i為個體序號，ηmax代表選擇壓力。4.2.4遺傳操作——選擇

4.2基本遺傳算法

個體選擇概率的常用分配方法基于排序的適應度分配（rank-basedfitnessassignment）非線性排序（byMichalewicz）

i為個體序號，c為排序第一的個體的選擇概率。4.2.4遺傳操作——選擇

4.2基本遺傳算法

常用選擇方法輪盤賭選擇法（roulettewheelselection）

4.2.4遺傳操作——選擇

個體1234567891011適應度2.01.81.61.41.21.00.80.60.40.20.1選擇概率0.180.160.150.130.110.090.070.060.030.020.0累計概率0.180.340.490.620.730.820.890.950.981.001.004.2基本遺傳算法

常用選擇方法隨機遍歷抽樣法（stochasticuniversalsampling）

4.2.4遺傳操作——選擇

個體1234567891011適應度2.01.81.61.41.21.00.80.60.40.20.1選擇概率0.180.160.150.130.110.090.070.060.030.020.0累計概率0.180.340.490.620.730.820.890.950.981.001.00設定n為需要選擇的個體數(shù)目，等距離選擇個體，選擇指針的距離為1／n。第一個指針的位置由[0，l／n]區(qū)間的均勻隨機數(shù)決定。如圖所示，需要選擇6個個體，指針間的距離為l／6＝o.167，第一個指針的隨機位置為0.1，按這種選擇方法被選中作為交配集個體為：1．2，3．4，6，8。

4.2基本遺傳算法

常用選擇方法局部選擇法（localselection）

(1)線形鄰集4.2.4遺傳操作——選擇

在局部選擇法中，每個個體處于一個約束環(huán)境中，稱為局部鄰域(而其他選擇方法中視整個種群為個體之鄰域)，個體僅與其鄰近個體產(chǎn)生交互，該鄰域的定義由種群的分布結構給出。鄰域可被當作潛在的交配伙伴。首先均勻隨機地選擇一半交配種群，選擇方法可以是隨機遍歷方法也可以是截斷選擇方法，然后對每個被選個體定義其局部鄰域，在鄰域內部選擇交配伙伴。4.2基本遺傳算法

常用選擇方法局部選擇法（localselection）

(2)兩對角鄰集4.2.4遺傳操作——選擇

4.2基本遺傳算法

常用選擇方法局部選擇法（localselection）

(2)兩對角鄰集4.2.4遺傳操作——選擇

4.2基本遺傳算法

常用選擇方法截斷選擇法（truncationselection）個體按適應度排列，只有優(yōu)秀個體能夠稱為父個體，參數(shù)為截斷閥值（被選作父個體的百分比）。4.2.4遺傳操作——選擇

截斷閥值1％10％20％40％50％80％選擇強度2.661.761.20.970.80.344.2基本遺傳算法

常用選擇方法錦標賽選擇法（tournamentselection）隨機從種群中挑選一定數(shù)目個體，其中最好的個體作為父個體，此過程重復進行完成個體的選擇。4.2.4遺傳操作——選擇

競賽規(guī)模12351030選擇強度00.560.851.151.532.044.2基本遺傳算法

實值重組離散重組子個體的每個變量可以按等概率隨機地挑選父個體。4.2.5遺傳操作——交叉/基因重組

父個體112

25

5父個體2123

4

34子個體1123

4

5子個體212

4

344.2基本遺傳算法

實值重組中間重組子個體＝父個體1＋α×（父個體2－父個體1）

α是比例因子，由[-d,1+d]上均勻分布地隨機數(shù)產(chǎn)生。

d=0時為中間重組，一般取d=0.25。子代的每個變量均產(chǎn)生一個α

。4.2.5遺傳操作——交叉/基因重組

4.2基本遺傳算法

實值重組中間重組

4.2.5遺傳操作——交叉/基因重組

父個體112255父個體2123434子個體1子個體2α值樣本10.51.1-0.1α值樣本20.10.80.512＋0.5×（123－12）=67.567.525＋1.1×（4－25）=1.91.92.112＋0.1×（123－12）=23.123.18.219.54.2基本遺傳算法

實值重組中間重組

4.2.5遺傳操作——交叉/基因重組

4.2基本遺傳算法

實值重組線性重組

4.2.5遺傳操作——交叉/基因重組

父個體112255父個體2123434子個體1子個體2α值樣本10.5α值樣本20.112＋0.5×（123－12）=67.567.525＋0.5×（4－25）=14.514.519.512＋0.1×（123－12）=23.123.122.97.94.2基本遺傳算法

實值重組線性重組

4.2.5遺傳操作——交叉/基因重組

4.2基本遺傳算法

二進制交叉單點交叉

4.2.5遺傳操作——交叉/基因重組

4.2基本遺傳算法

二進制交叉多點交叉

4.2.5遺傳操作——交叉/基因重組

4.2基本遺傳算法

二進制交叉均勻交叉

4.2.5遺傳操作——交叉/基因重組

父個體101110011010

父個體210101100101子個體11

11

011

11

1

1

1子個體20

01

100

00

0

0

0

樣本101100011010樣本2100111001014.2基本遺傳算法

實值變異一般采用：二進制變異

4.2.6遺傳操作——變異

4.2基本遺傳算法

主程序

4.2.7算法的設計與實現(xiàn)

%用遺傳算法進行簡單函數(shù)的優(yōu)化clearbn=22;%個體串長度inn=50;%初始種群大小gnmax=200;%最大代數(shù)pc=0.75;%交叉概率pm=0.05;%變異概率Continue…4.2基本遺傳算法

主程序

4.2.7算法的設計與實現(xiàn)

%產(chǎn)生初始種群，0,1向量s=round(rand(inn,bn));%計算適應度,返回適應度f和累積概率p[f,p]=objf(s);Continue…4.2基本遺傳算法

主程序

4.2.7算法的設計與實現(xiàn)

gn=1;whilegn<gnmax+1forj=1:2:inn%選擇操作seln=sel(s,p);%交叉操作scro=cro(s,seln,pc);scnew(j,:)=scro(1,:);scnew(j+1,:)=scro(2,:);%變異操作smnew(j,:)=mut(scnew(j,:),pm);smnew(j+1,:)=mut(scnew(j+1,:),pm);endContinue…4.2基本遺傳算法

主程序

4.2.7算法的設計與實現(xiàn)

s=smnew;%產(chǎn)生了新的種群%計算新種群的適應度[f,p]=objf(s);

%記錄當前代最好和平均的適應度

[fmax,nmax]=max(f);fmean=mean(f);ymax(gn)=fmax;ymean(gn)=fmean;Continue…4.2基本遺傳算法

主程序

4.2.7算法的設計與實現(xiàn)

%記錄當前代的最佳個體x=n2to10(s(nmax,:));xx=-1.0+x*3/(power(2,bn)-1);xmax(gn)=xx;

gn=gn+1endgn=gn-1;Continue…4.2基本遺傳算法

主程序

4.2.7算法的設計與實現(xiàn)

%繪制曲線subplot(2,1,1);plot(1:gn,[ymax;ymean]);title('歷代適應度變化','fonts',10);legend('最大適應度','平均適應度');string1=['最終適應度',num2str(ymax(gn))];gtext(string1);subplot(2,1,2);plot(1:gn,xmax,'r-');legend('自變量');string2=['最終自變量',num2str(xmax(gn))];gtext(string2);End4.2基本遺傳算法

計算適應度和累計概率函數(shù)

4.2.7算法的設計與實現(xiàn)

%計算適應度函數(shù)function[f,p]=objf(s);r=size(s);%讀取種群大小inn=r(1);%有inn個個體bn=r(2);%個體長度為bnContinue…4.2基本遺傳算法

計算適應度和累計概率函數(shù)

4.2.7算法的設計與實現(xiàn)

fori=1:innx=n2to10(s(i,:));%將二進制轉換為十進制xx=-1.0+x*3/(power(2,bn)-1);%轉化為[-1,2]區(qū)間的實數(shù)f(i)=ft(xx);%計算函數(shù)值，即適應度endf=f‘;%行向量轉列向量Continue…4.2基本遺傳算法

函數(shù)n2to10()

4.2.7算法的設計與實現(xiàn)

Continue…functionx=n2to10(s)x=0;forj=1:22x=x+s(j)*2^(22-j);end

functionx=n2to10(s)x=s(1);forj=1:21x=x*2+s(j+1);end4.2基本遺傳算法

計算適應度和累計概率函數(shù)

4.2.7算法的設計與實現(xiàn)

%計算選擇概率fsum=0;fori=1:innfsum=fsum+f(i)*f(i);endfori=1:innps(i)=f(i)*f(i)/fsum;endContinue…4.2基本遺傳算法

計算適應度和累計概率函數(shù)

4.2.7算法的設計與實現(xiàn)

%計算累積概率p(1)=ps(1);fori=2:innp(i)=p(i-1)+ps(i);endp=p';Backtomain.m4.2基本遺傳算法

計算目標函數(shù)值函數(shù)

4.2.7算法的設計與實現(xiàn)

%目標函數(shù)functiony=ft(x);y=x.*sin(10*pi*x)+2;Backtoobjf.m4.2基本遺傳算法

選擇操作函數(shù)

4.2.7算法的設計與實現(xiàn)

%“選擇”操作functionseln=sel(s,p);inn=size(p,1);%從種群中選擇兩個個體fori=1:2r=rand;%產(chǎn)生一個隨機數(shù)prand=p-r;j=1;whileprand(j)<0j=j+1;endseln(i)=j;%選中個體的序號endBacktomain.m4.2基本遺傳算法

交叉操作函數(shù)

4.2.7算法的設計與實現(xiàn)

%“交叉”操作functionscro=cro(s,seln,pc);r=size(s);inn=r(1);bn=r(2);pcc=pro(pc);%根據(jù)交叉概率決定是否進行交叉操作，1則是，0則否Continue…4.2基本遺傳算法

交叉操作函數(shù)

4.2.7算法的設計與實現(xiàn)

ifpcc==1chb=round(rand*(bn-2))+1;%在[1,bn-1]范圍內隨機產(chǎn)生一個交叉位scro(1,:)=[s(seln(1),1:chb)s(seln(2),chb+1:bn)];scro(2,:)=[s(seln(2),1:chb)s(seln(1),chb+1:bn)];elsescro(1,:)=s(seln(1),:);scro(2,:)=s(seln(2),:);endBacktomain.m4.2基本遺傳算法

變異操作函數(shù)

4.2.7算法的設計與實現(xiàn)

%“變異”操作functionsnnew=mut(snew,pm);r=size(snew);bn=r(2);snnew=snew;Continue…4.2基本遺傳算法

變異操作函數(shù)

4.2.7算法的設計與實現(xiàn)

pmm=pro(pm);%根據(jù)變異概率決定是否進行變異操作，1則是，0則否ifpmm==1chb=round(rand*(bn-1))+1;%在[1,bn]范圍內隨機產(chǎn)生一個變異位snnew(chb)=abs(snew(chb)-1);endBacktomain.m4.2基本遺傳算法

運行程序

4.2.7算法的設計與實現(xiàn)

4.2基本遺傳算法

運行程序

4.2.7算法的設計與實現(xiàn)

4.2基本遺傳算法

運行程序

4.2.7算法的設計與實現(xiàn)

4.2基本遺傳算法

運行程序

4.2.7算法的設計與實現(xiàn)

4.2基本遺傳算法

模式將種群中的個體即基因串中的相似樣板稱為模式。在二進制編碼的串中，模式是基于三個字符集（0，1，*）的字符串，符號*代表任意字符，即0或1。如模式*1*描述了一個四個元的子集{010，011，110，111}。4.2.8模式定理

4.2基本遺傳算法

模式階和定義距模式H中確定位置的個數(shù)稱為模式H的模式階，記作O(H)，如O(011*1*)=4。模式階用來反映不同模式間確定性的差異，模式階越高，模式的確定性就越高，所匹配的樣本個數(shù)就越少。4.2.8模式定理

4.2基本遺傳算法

模式階和定義距模式H中第一個確定位置和最后一個確定位置之間的距離稱為模式的定義距，記作δ(H)，如

δ(011*1**)=4。階數(shù)相同的模式會有不同的性質，定義距就反映了這種性質的差異。4.2.8模式定理

4.2基本遺傳算法

智能優(yōu)化計算華東理工大學自動化系2007年模式定理（schematheorem）在給定時間步t,一個特定模式