遺傳算法基本思想

遺傳算法（Genetic Algorithm, GA）起源于對生物系統(tǒng)所進行的計算機模擬研究。它是模仿自然界生物進化機制發(fā)展起來的隨機全局搜索和優(yōu)化方法，借鑒了達爾文的進化論和孟德爾的遺傳學說。其本質(zhì)是一種高效、并行、全局搜索的方法，能在搜索過程中自動獲取和積累有關(guān)搜索空間的知識，并自適應地控制搜索過程以求得最佳解。

遺傳算法的主要步驟

（1）編碼：將問題的候選解用染色體表示，實現(xiàn)解空間向編碼空間的映射過程。遺傳算法不直接處理解空間的決策變量，而是將其轉(zhuǎn)換成由基因按一定結(jié)構(gòu)組成的染色體。編碼方式有很多，如二進制編碼、實數(shù)向量編碼、整數(shù)排列編碼、通用數(shù)據(jù)結(jié)構(gòu)編碼等等。本文將采用二進制編碼的方式，將十進制的變量轉(zhuǎn)換成二進制，用0和1組成的數(shù)字串模擬染色體，可以很方便地實現(xiàn)基因交叉、變異等操作。 

（2）種群初始化：產(chǎn)生代表問題可能潛在解集的一個初始群體（編碼集合）。種群規(guī)模設(shè)定主要有以下方面的考慮：從群體多樣性方面考慮，群體越大越好，避免陷入局部最優(yōu)；從計算效率方面考慮，群體規(guī)模越大將導致計算量的增加。應該根據(jù)實際問題確定種群的規(guī)模。產(chǎn)生初始化種群的方法通常有兩種：一是完全隨機的方法產(chǎn)生；二是根據(jù)先驗知識設(shè)定一組必須滿足的條件，然后根據(jù)這些條件生成初始樣本。

（3）計算個體適應度：利用適應度函數(shù)計算各個個體的適應度大小。適應度函數(shù)（Fitness Function）的選取直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解，因為在進化搜索中基本不利用外部信息，僅以適應度函數(shù)為依據(jù)，利用種群每個個體的適應程度來指導搜索。

（4）進化計算：通過選擇、交叉、變異，產(chǎn)生出代表新的解集的群體。選擇（selection）：根據(jù)個體適應度大小，按照優(yōu)勝劣汰的原則，淘汰不合理的個體；交叉（crossover）：編碼的交叉重組，類似于染色體的交叉重組；變異（mutation）：編碼按小概率擾動產(chǎn)生的變化，類似于基因突變。

（5）解碼：末代種群中的最優(yōu)個體經(jīng)過解碼實現(xiàn)從編碼空間向解空間的映射，可以作為問題的近似最優(yōu)解。這是整個遺傳算法的最后一步，經(jīng)過若干次的進化過程，種群中適應度最高的個體代表問題的最優(yōu)解，但這個最優(yōu)解還是一個由0和1組成的數(shù)字串，要將它轉(zhuǎn)換成十進制才能供我們理解和使用。

遺傳編碼

遺傳編碼將變量轉(zhuǎn)化為基因組的表示形式，優(yōu)化變量的編碼機制有二進制編碼、十進制編碼（實數(shù)編碼）等。

二進制編碼

這里簡單介紹以下二進制編碼的實現(xiàn)原理。例如，求實數(shù)區(qū)間[0,4]上函數(shù)f(x)的最大值，傳統(tǒng)的方法是不斷調(diào)整自變量x的值，假設(shè)使用二進制編碼新式，我們可以由長度6的未穿表示變量x，即從000000到111111，并將中間的取值映射到實數(shù)區(qū)間[0,4]內(nèi)。由于哦才能夠整數(shù)上來看，6位長度二進制表示范圍為0~63，所以對應的[0,4]區(qū)間，每個相鄰值之間的階躍值為4/64≈0.00635。這個就是編碼的精度，編碼精度越高，所得到的解的質(zhì)量也越高。

實數(shù)編碼

在解決高維、連續(xù)優(yōu)化問題等是，經(jīng)常采用實數(shù)編碼方式。實數(shù)編碼的優(yōu)點是計算精度搞，便于和經(jīng)典連續(xù)優(yōu)化算法結(jié)合。

遺傳算法流程

1）初始化。設(shè)置進化代數(shù)計數(shù)器g=0，設(shè)置最大進化代數(shù)G，隨機生成NP個個體作為初始群體P(0)

2）個體評價P(t)。計算群體中各個個體的適應度

3）選擇運算。將選擇算子作用域群體，根據(jù)個體適應度，按照一定的規(guī)則和方法，選擇一些優(yōu)良個體遺傳到下一代群體。

4）交叉運算。將交叉算子作用于群體，對選中的成對個體，以某一概率交換他們之間的部分染色體，產(chǎn)生新的個體

5）變異運算。將變異算子作用于群體，對選中的個體，以某一概率改變某一個或某一些基因值為其他的等位基因。群體P(t)經(jīng)過選擇、交叉、和變異運算之后得到下一代群體P(t+1)。計算其適應度值，并根據(jù)適應度值進行排序，準備進行下一代遺傳操作。

6）終止條件判斷：若g≤G，則g=g+1，轉(zhuǎn)到步驟2）；若g＞G，則終止計算

實際演示 

計算函數(shù)

的最小值。這是一個簡單的平方和問函數(shù)，只有一個極小點，理論最小值f(0,0,...,0)=0

仿真過程如下：

（1）初始化種群數(shù)目為NP=100，染色體基因維數(shù)D=10，最大進化迭代數(shù)G=1000，交叉概率為P_c=0.8，變異概率P_m=0.1

（2）產(chǎn)生初始種群，計算給體適應度值；進行始數(shù)編碼的安澤以及交叉和變異操作。選擇和交叉操作采用“君主方案”，即在對群體根據(jù)適應度值高低進行排序的基礎(chǔ)上，用最優(yōu)個體與其他偶數(shù)位的所有個體進行交叉，每次交叉產(chǎn)生兩個新個體。在交叉過后，對信產(chǎn)所的群體進行多點變異產(chǎn)生子群體，再計算器適應度值，然后和父群體合并，并且根據(jù)適應度值進行排序，取前NP個個體為新群體，進行下一次遺傳操作。

（3）判斷是否滿足終止條件：若滿足，結(jié)束搜索過程，輸出最優(yōu)值；若不滿足，繼續(xù)迭代優(yōu)化

%%%%%%%%%%%%%%%%%%%%實值遺傳算法求函數(shù)極值%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all;                           %清除所有變量
close all;                           %清圖
clc;                                 %清屏
D=10;                                %基因數(shù)目    
NP=100;                              %染色體數(shù)目
Xs=20;                               %上限          
Xx=-20;                              %下限
G=1000;                               %最大遺傳代數(shù)
f=zeros(D,NP);                       %初始種群賦空間
nf=zeros(D,NP);                      %子種群賦空間
Pc=0.8;                              %交叉概率
Pm=0.1;                              %變異概率
f=rand(D,NP)*(Xs-Xx)+Xx;             %隨機獲得初始種群
%%%%%%%%%%%%%%%%%%%%%%按適應度升序排列%%%%%%%%%%%%%%%%%%%%%%%
for np=1:NP
    MSLL(np)=func2(f(:,np));
end
[SortMSLL,Index]=sort(MSLL);                            
Sortf=f(:,Index);
%%%%%%%%%%%%%%%%%%%%%%%遺傳算法循環(huán)%%%%%%%%%%%%%%%%%%%%%%%%%%
for gen=1:G
    %%%%%%%%%%%%%%采用君主方案進行選擇交叉操作%%%%%%%%%%%%%%%%
    Emper=Sortf(:,1);                      %君主染色體
    NoPoint=round(D*Pc);                   %每次交叉點的個數(shù)
    PoPoint=randi([1 D],NoPoint,NP/2);   %交叉基因的位置
    nf=Sortf;
    for i=1:NP/2
        nf(:,2*i-1)=Emper;
        nf(:,2*i)=Sortf(:,2*i);
        for k=1:NoPoint
            nf(PoPoint(k,i),2*i-1)=nf(PoPoint(k,i),2*i);
            nf(PoPoint(k,i),2*i)=Emper(PoPoint(k,i));
        end
    end
    %%%%%%%%%%%%%%%%%%%%%%%%%%變異操作%%%%%%%%%%%%%%%%%%%%%%%%%
    for m=1:NP
        for n=1:D
            r=rand(1,1);
            if r<Pm
                nf(n,m)=rand(1,1)*(Xs-Xx)+Xx;
            end
        end
    end
    %%%%%%%%%%%%%%%%%%%%%子種群按適應度升序排列%%%%%%%%%%%%%%%%%%
    for np=1:NP 
          NMSLL(np)=func2(nf(:,np));   
    end
    [NSortMSLL,Index]=sort(NMSLL);           
    NSortf=nf(:,Index);
    %%%%%%%%%%%%%%%%%%%%%%%%%產(chǎn)生新種群%%%%%%%%%%%%%%%%%%%%%%%%%%
    f1=[Sortf,NSortf];                %子代和父代合并
    MSLL1=[SortMSLL,NSortMSLL];       %子代和父代的適應度值合并
    [SortMSLL1,Index]=sort(MSLL1);    %適應度按升序排列
    Sortf1=f1(:,Index);               %按適應度排列個體
    SortMSLL=SortMSLL1(1:NP);         %取前NP個適應度值
    Sortf=Sortf1(:,1:NP);             %取前NP個個體
    trace(gen)=SortMSLL(1);           %歷代最優(yōu)適應度值
end
Bestf=Sortf(:,1);                     %最優(yōu)個體 
trace(end)                            %最優(yōu)值
figure
plot(trace)
xlabel('迭代次數(shù)')
ylabel('目標函數(shù)值')
title('適應度進化曲線')
%%%%%%%%%%%%%%%%%%%%%%%%%%%適應度函數(shù)%%%%%%%%%%%%%%%%%%%%%%%%%%%
function result=func2(x)
summ=sum(x.^2);
result=summ;
end

到此這篇關(guān)于Matlab利用遺傳算法GA求解非連續(xù)函數(shù)問題詳解的文章就介紹到這了,更多相關(guān)Matlab遺傳算法求解非連續(xù)函數(shù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論