1、遺傳算法1. 遺傳算法的簡單原理 遺傳算法(Genetic Algorithm, GA)是一種基于自然群體遺傳演化機制的高效探索算法，它摒棄了傳統的搜索方式，模擬自然界生物進化過程，采用人工進化的方式對目標空間進行隨機化搜索。它將問題域中的可能解看作是群體的一個個體或染色體，并將每一個體編碼成符號串形式，模擬達爾文的遺傳選擇和自然淘汰的生物進化過程，對群體反復進行基于遺傳學的操作（遺傳，交叉和變異），根據預定的目標適應度函數對每個個體進行評價，依據適者生存，優勝劣汰的進化規則，不斷得到更優的群體，同時以全局并行搜索方式來搜索優化群體中的最優個體，求得滿足要求的最優解。我們先通過一個例子來了解遺

2、傳算法的原理： 假定我們要求函數的極大值，其中為自然數，。現在，我們將每一個數看成一個生命體，通過進化，我們看誰能最后生存下來，誰就是我們所尋找的數。編碼:我們將每一個數作為一個生命體，那么必須給其賦予一定的基因，這個過程叫做編碼。我們可以把變量編碼成5位長的二進制無符號整數表示形式，比如可表示為01101的形式，也就是說，數13的基因為01101。初始群體的生成: 由于遺傳的需要，我們必須設定一些初始的生物群體，讓其作為生物繁殖的第一代，需要說明的是，初始群體的每個個體都是通過隨機方法產生的，這樣便可以保證生物的多樣性和競爭的公平性。適應度評估檢測: 生物的進化服從適者生存，優勝劣汰的進化規

3、則，因此，我們必須規定什么樣的基因是“優”的，什么樣的基因是“劣”的，在這里，我們稱為適應度。顯然，由于我們要求的最大值，因此，能使函數值較大的基因是優的，使函數值較小的基因是劣的，因此，我們可以將原函數定義為適應度函數，用來衡量某一生物體的適應程度。選擇：接下來，我們便可以進行優勝劣汰的過程，這個過程在遺傳算法里叫做選擇。注意，選擇應該是一個隨機的過程，基因差的生物體不一定會被淘汰，只是其被淘汰概率比較大罷了，這與自然界中的規律是相同的。因此，我們可以采取賭輪的方式來進行選擇。交叉操作：接下來進行交叉繁殖，隨機選出兩個生物體，讓其交換一部分基因，這樣便形成了兩個新的生物體，為第二代。變異：生

4、物界中不但存在著遺傳，同時還存在著變異，在這里我們也引入變異，使生物體的基因中的某一位以一定的概率發生變化，這樣引入適當的擾動，能避免局部極值的問題。以上的算法便是最簡單的遺傳算法，通過以上步驟不斷地進化，生物體的基因便逐漸地趨向最優，最后便能得到我們想要的結果。2 遺傳算法的步驟 從上面的例子中，我們便能得到遺傳算法的一般步驟，如下圖所示： 3 遺傳算法的應用 遺傳算法主要是用來尋優，它具有很多優點：它能有效地避免局部最優現象，有及其頑強的魯棒性，并且在尋優過程中，基本不需要任何搜索空間的知識和其他輔助信息等等。為了介紹遺傳算法的應用，我們將前面的例子進行完，整個過程如下： 初始群體 011

5、01 11000 01000 10011 x的值 13 24 8 19 適應度 169 576 64 361選擇概率 0.14 0.49 0.06 0.31 選擇上的計數（來自賭輪） 1 2 0 1 交叉處 0110|1 1100|0 11|000 10|011 下一代群體 01100 11001 11011 10000 x的值 12 25 27 16 適應度 144 625 729 256 求解過程：將自變量在給定的范圍內進行編碼，得到種群編碼，按照所選擇的適應度函數并通過選擇復制，交叉重組與變異對個體進行篩選與進化，使適應度值大的個體被保留，適應度小的個體被淘汰，新的群體繼承了上一代的信息

6、，同時又優于上一代，這樣反復循環，直到滿足條件，最后留下來的個體集中分布在最優解周圍，篩選出其中的個體作為問題的解。4遺傳算法的程序設計 （1）謝爾菲德遺傳算法工具箱-英國謝爾菲德大學開發 特點：1）使用MATLAB高級語言編寫； 2）對問題使用M文件編寫，可以看見源代碼； 3）為用戶提供了廣泛多樣的實用函數。 安裝：1）解壓謝爾菲德遺傳算法工具箱，得到謝爾菲德遺傳算法工具箱文件夾，內含DOC文件夾與gatbx文件夾； 2）將謝爾菲德遺傳算法工具箱文件夾拷貝到MATLABbin目錄下； 3）為謝爾菲德遺傳算法工具箱文件設置工作路徑：雙擊MATLAB，運行MATLAB，在MATLAB窗口中選擇路

7、徑設置窗口：Set path； 4)在Set path中選擇 Add folder項； 5）設置如下：謝爾菲德遺傳算法工具箱文件；謝爾菲德遺傳算法工具箱文件DOC；謝爾菲德遺傳算法工具箱文件gatbx；謝爾菲德遺傳算法工具箱文件gatbxtest_fns。點擊SAVE保存，再點擊CLOSE關閉Set path窗口。 6）將文件夾的所有字母改為小寫字母。 7）測試：在Command Window窗口鍵入：help crtbp。 謝爾菲德遺傳算法工具箱中主要函數函數分類 函數 功能 創建 種群crtbase 創建基向量crtbp 創建離散的隨機種群 crtrp 創建實數隨機種群適應度計算ranki

8、ng 基于排序的適應度分配scaling 比率適應度計算選擇函數reins一致隨機和基于適應度的重插入rws輪盤選擇select高級選擇例程sus隨即便利采樣交叉算子recdis高級重組recint中間重組recline線性重組recmut具有變異特征的線性重組recombin高級重組算子xovdp兩點交叉算子xovdprs減少代理的兩點交叉xovmp通常多點交叉xovsh洗牌交叉xovshrs減少代理的洗牌交叉xovsp單點交叉xovsprs減少代理的單點交叉變異算子mut離散變異mutate高級變異函數mutbga實值變異子種群的支持migrate在子種群間交換個體實用函數bs2rv二進制

9、串到實值的轉換rep矩陣的復制常用函數1創建離散的隨機種群Chrom, Lind,BaseV=crtbp(Nind,Lind)Chrom, Lind,BaseV=crtbp(Nind,Base)Chrom, Lind,BaseV=crtbp(Nind,Lind,Base)（注意：Base 的列數就是Lind,即染色體的長度）Chrom, Lind,BaseV=crtbp(5，10)Chrom, Lind,BaseV=crtbp(5，2 3 4 5 6 7 8 9)2適應度計算函數FitnV=ranking(ObjV)3.選擇算子select4.交叉算子recombin5.變異算子mut6.重插

10、入函數reins7.實用函數bs2rvPhen=bs2rv(Chrom,FieldD),其中FieldD=len;lb;ub;code;scale;lbin;ubin8.實用函數rep謝爾菲德遺傳算法工具箱應用舉例例1. 用遺傳算法求的最小值。遺傳算法參數設置種群規模最大遺傳代數個體長度代溝交叉概率變異概率4020200.950.70.01程序清單如下：clcclear allclose all% 畫出函數圖figure(1);hold on;lb=1;ub=2; %函數自變量范圍1,2ezplot('sin(10*pi*X)/X',lb,ub); %畫出函數曲線xlabel(

11、'自變量/X')ylabel('函數值/Y')% 定義遺傳算法參數NIND=40; %個體數目MAXGEN=20; %最大遺傳代數PRECI=20; %變量的二進制位數GGAP=0.95; %代溝px=0.7; %交叉概率pm=0.01; %變異概率trace=zeros(2,MAXGEN); %尋優結果的初始值FieldD=PRECI;lb;ub;1;0;1;1; %區域描述器Chrom=crtbp(NIND,PRECI); %產生初始種群% 優化gen=0; %代計數器X=bs2rv(Chrom,FieldD); %計算初始種群的十進制轉換ObjV=sin(

12、10*pi*X)./X; %計算目標函數值while gen<MAXGEN FitnV=ranking(ObjV); %分配適應度值 SelCh=select('sus',Chrom,FitnV,GGAP); %選擇 SelCh=recombin('xovsp',SelCh,px); %重組 SelCh=mut(SelCh,pm); %變異 X=bs2rv(SelCh,FieldD); %子代個體的十進制轉換 ObjVSel=sin(10*pi*X)./X; %計算子代的目標函數值 Chrom,ObjV=reins(Chrom,SelCh,1,1,ObjV

13、,ObjVSel); %重插入子代到父代，得到新種群 X=bs2rv(Chrom,FieldD); gen=gen+1; %代計數器增加 %獲取每代的最優解及其序號，Y為最優解,I為個體的序號 Y,I=min(ObjV); trace(1,gen)=X(I); %記下每代的最優值 trace(2,gen)=Y; %記下每代的最優值endplot(trace(1,:),trace(2,:),'bo'); %畫出每代的最優點grid on;plot(X,ObjV,'b*'); %畫出最后一代的種群hold off% 畫進化圖figure(2);plot(1:MAXG

14、EN,trace(2,:);grid onxlabel('遺傳代數')ylabel('解的變化')title('進化過程')bestY=trace(2,end);bestX=trace(1,end);fprintf('最優解:nX=',num2str(bestX),'nY=',num2str(bestY),'n')例2. 用遺傳算法求的最大值。遺傳算法參數設置種群規模最大遺傳代數個體長度代溝交叉概率變異概率405040（2個，每個長20）0.950.70.01程序清單如下：clcclear allc

15、lose all% 畫出函數圖figure(1);lbx=-2;ubx=2; %函數自變量x范圍-2,2lby=-2;uby=2; %函數自變量y范圍-2,2ezmesh('y*sin(2*pi*x)+x*cos(2*pi*y)',lbx,ubx,lby,uby,50); %畫出函數曲線hold on;% 定義遺傳算法參數NIND=40; %個體數目MAXGEN=50; %最大遺傳代數PRECI=20; %變量的二進制位數GGAP=0.95; %代溝px=0.7; %交叉概率pm=0.01; %變異概率trace=zeros(3,MAXGEN); %尋優結果的初始值FieldD

16、=PRECI PRECI;lbx lby;ubx uby;1 1;0 0;1 1;1 1; %區域描述器Chrom=crtbp(NIND,PRECI*2); %初始種群% 優化gen=0; %代計數器XY=bs2rv(Chrom,FieldD); %計算初始種群的十進制轉換X=XY(:,1);Y=XY(:,2);ObjV=Y.*sin(2*pi*X)+X.*cos(2*pi*Y); %計算目標函數值while gen<MAXGEN FitnV=ranking(-ObjV); %分配適應度值 SelCh=select('sus',Chrom,FitnV,GGAP); %選擇

17、 SelCh=recombin('xovsp',SelCh,px); %重組 SelCh=mut(SelCh,pm); %變異 XY=bs2rv(SelCh,FieldD); %子代個體的十進制轉換 X=XY(:,1);Y=XY(:,2); ObjVSel=Y.*sin(2*pi*X)+X.*cos(2*pi*Y); %計算子代的目標函數值 Chrom,ObjV=reins(Chrom,SelCh,1,1,ObjV,ObjVSel); %重插入子代到父代，得到新種群 XY=bs2rv(Chrom,FieldD); gen=gen+1; %代計數器增加 %獲取每代的最優解及其序號

18、，Y為最優解,I為個體的序號 Y,I=max(ObjV); trace(1:2,gen)=XY(I,:); %記下每代的最優值 trace(3,gen)=Y; %記下每代的最優值endplot3(trace(1,:),trace(2,:),trace(3,:),'bo'); %畫出每代的最優點grid on;plot3(XY(:,1),XY(:,2),ObjV,'bo'); %畫出最后一代的種群hold off% 畫進化圖figure(2);plot(1:MAXGEN,trace(3,:);grid onxlabel('遺傳代數')ylabel(

19、'解的變化')title('進化過程')bestZ=trace(3,end);bestX=trace(1,end);bestY=trace(2,end);fprintf('最優解:nX=',num2str(bestX),'nY=',num2str(bestY),'nZ=',num2str(bestZ),'n')作業：用遺傳算法求函數的最小值。clcclear allclose all% 畫出函數圖figure(1);lbx1=-2;ubx1=2; %函數自變量x1范圍-2,2lbx2=-2;ubx2

20、=2; %函數自變量x2范圍-2,2ezmesh('-20*exp(-0.2*sqrt(x12+x22)/2)-exp(cos(2*pi*x1)+cos(2*pi*x2)/2)+20+2.71289',lbx1,ubx1,lbx2,ubx2,50); %畫出函數曲線hold on;% 定義遺傳算法參數NIND=40; %個體數目MAXGEN=50; %最大遺傳代數PRECI=20; %變量的二進制位數GGAP=0.95; %代溝px=0.7; %交叉概率pm=0.01; %變異概率trace=zeros(3,MAXGEN); %尋優結果的初始值FieldD=PRECI PREC

21、I;lbx lby;ubx uby;1 1;0 0;1 1;1 1; %區域描述器Chrom=crtbp(NIND,PRECI*2); %初始種群% 優化gen=0; %代計數器XY=bs2rv(Chrom,FieldD); %計算初始種群的十進制轉換X=XY(:,1);Y=XY(:,2);ObjV=Y.*sin(2*pi*X)+X.*cos(2*pi*Y); %計算目標函數值while gen<MAXGEN FitnV=ranking(-ObjV); %分配適應度值 SelCh=select('sus',Chrom,FitnV,GGAP); %選擇 SelCh=recombin('xovsp',SelCh,px); %重組 SelCh=mut(SelCh,pm); %變異 XY=bs2rv(SelCh,FieldD);