基本遺傳算法(GA)的算法原理、步驟、及Matlab實作

算法原理

遺傳算法可以用來求函數的極值。

（1）用二進制編碼來離散自變量，碼長根據離散精度來确定。碼長為 log2[（max−min)/精度+1]

（2）交叉方法采用單點交叉

（3）變異是根據變異機率反轉子代某個位的值

（4）選擇政策采用輪盤賭政策，令 PPi=∑ij=1pi,PP0=0 ,其中 PPi 為累計機率， pi 為個體的選擇機率，公式為: pi=fitness(xi)∑NPi=1fitness(xi) ,其中 fitnessxi 為個體的适應度，共輪轉 NP 次，每次輪轉時，産生随機數 r ,當PPi−1<=r<PPi時選擇個體 i <script type="math/tex" id="MathJax-Element-10">i</script>。

算法步驟

基本遺傳算法的基本步驟是：

1. 随機産生種群，
2. 用輪盤賭政策确定個體的适應度，判斷是否符合優化準則，若符合，輸出最佳個體及其最優解，結束，否則，進行下一步
3. 依據适應度選擇再生個體，适應度高的個體被選中的機率高，适應度低的個體被淘汰
4. 按照一定的交叉機率和交叉方法，生成新的個體
5. 按照一定的變異機率和變異方法，生成新的個體
6. 由交叉和變異産生新一代種群，傳回步驟2

算法的實作

%基本遺傳算法，一維無限制優化
function [ xv,fv ] = mGA( fitness,a,b,NP,NG,Pc,Pm,eps )
% 待優化的目标函數：fitness
% 自變量下界：a
% 自變量上界：b
% 種群個體數：NP
% 最大進化代數：NG
% 雜交常數：Pc
% 變異常數：Pm
% 自變量離散精度：eps
% 目标函數取最大值是的自變量值：xv
% 目标函數的最小值：fv

L=ceil(log2((b-a)/eps+)); %碼長
x=zeros(NP,L);
for i=:NP
    x(i,:)=Initial(L);
    fx(i)=fitness(Dec(a,b,x(i,:),L));
end
for k=:NG
    sumfx=sun(fx);
    Px=fx/sumfx;
    PPx=;
    PPx()=Px();
    for i=:NP  %根據輪盤賭确定父親
        PPx(i)=PPx(i-)+PPx(i);
    end
    for i=:NP
        sita=rand();
        for n=:NP
            if sita <= PPx(n)
                SelFather = n;
                break;
            end
        end
        Selmother=floor(rand()*(NP-))+;   %随機選擇母親
        posCut=floor(rand()*(L-))+;   %随機确定交叉點
        r1=rand();
        if r1<=Pc
            nx(i,:posCut)=x(SelFather,:posCut);
            nx(I,(posCut+):L)=x(Selmother,(posCut+):L);
            r2=rand();
            if r2<=Pm    %變異
                posMut=round(rand()*(L-)+);
                nx(i,posMut)=~nx(i,posMut);
            end
        else
            nx(i,:)=x(SelFather,:);
        end
    end
    x=nx;
    for i=:NP
        fx(i)=fitness(Dec(a,b,x(i,:),L);
    end
end
fv=-inf;
for i=:NP
    fitx=fitness(Dec(a,b,x(i,:),L));
    if fitx > fv
        fv=fitx;
        xv=Dec(a,b,x(i,:),L);
    end
end
end

function result=Initial(length)     %初始化函數
    for i=:length
        r=rand();
        result(i)=round(r);
    end
end
function y=Dec(a,b,x,L)     %二進制轉十進制
    base=^((L-):-:);
    y=dot(base,x);
    y=a+y*(b-)/(^L-)'
end