遺傳算法基本思想

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

遺傳算法的主要步驟

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

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

（3）計(jì)算個(gè)體適應(yīng)度：利用適應(yīng)度函數(shù)計(jì)算各個(gè)個(gè)體的適應(yīng)度大小。適應(yīng)度函數(shù)（Fitness Function）的選取直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解，因?yàn)樵谶M(jìn)化搜索中基本不利用外部信息，僅以適應(yīng)度函數(shù)為依據(jù)，利用種群每個(gè)個(gè)體的適應(yīng)程度來(lái)指導(dǎo)搜索。

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

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

遺傳編碼

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

二進(jìn)制編碼

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

實(shí)數(shù)編碼

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

遺傳算法流程

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

2）個(gè)體評(píng)價(jià)P(t)。計(jì)算群體中各個(gè)個(gè)體的適應(yīng)度

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

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

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

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

實(shí)際演示 

計(jì)算函數(shù)

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

仿真過(guò)程如下：

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

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

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

%%%%%%%%%%%%%%%%%%%%實(shí)值遺傳算法求函數(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;             %隨機(jī)獲得初始種群
%%%%%%%%%%%%%%%%%%%%%%按適應(yīng)度升序排列%%%%%%%%%%%%%%%%%%%%%%%
for np=1:NP
    MSLL(np)=func2(f(:,np));
end
[SortMSLL,Index]=sort(MSLL);                            
Sortf=f(:,Index);
%%%%%%%%%%%%%%%%%%%%%%%遺傳算法循環(huán)%%%%%%%%%%%%%%%%%%%%%%%%%%
for gen=1:G
    %%%%%%%%%%%%%%采用君主方案進(jìn)行選擇交叉操作%%%%%%%%%%%%%%%%
    Emper=Sortf(:,1);                      %君主染色體
    NoPoint=round(D*Pc);                   %每次交叉點(diǎn)的個(gè)數(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
    %%%%%%%%%%%%%%%%%%%%%子種群按適應(yīng)度升序排列%%%%%%%%%%%%%%%%%%
    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];       %子代和父代的適應(yīng)度值合并
    [SortMSLL1,Index]=sort(MSLL1);    %適應(yīng)度按升序排列
    Sortf1=f1(:,Index);               %按適應(yīng)度排列個(gè)體
    SortMSLL=SortMSLL1(1:NP);         %取前NP個(gè)適應(yīng)度值
    Sortf=Sortf1(:,1:NP);             %取前NP個(gè)個(gè)體
    trace(gen)=SortMSLL(1);           %歷代最優(yōu)適應(yīng)度值
end
Bestf=Sortf(:,1);                     %最優(yōu)個(gè)體 
trace(end)                            %最優(yōu)值
figure
plot(trace)
xlabel('迭代次數(shù)')
ylabel('目標(biāo)函數(shù)值')
title('適應(yīng)度進(jìn)化曲線')
%%%%%%%%%%%%%%%%%%%%%%%%%%%適應(yīng)度函數(shù)%%%%%%%%%%%%%%%%%%%%%%%%%%%
function result=func2(x)
summ=sum(x.^2);
result=summ;
end

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

最新評(píng)論