最優化算法與matlab應用5：遺傳算法

最優化算法與matlab應用5：遺傳算法

本文節選于王正林《精通MATLAB_科學計算》第2版

遺傳算法GA是一種直接的随機搜尋方法，它是在适者生存的自然進化過程中逐漸建立的。算法原理類似于模拟退火，适用于尋找具有多個極值的目标函數的全局最小解。

算法步驟

交叉：交叉操作是遺傳算法中最主要的遺傳操作。通過交叉操作可以得到新一代個體，新個體組合了其父輩個體的特性。交叉展現了資訊交換的思想。

變異：變異首先在群體中随機選擇一個個體，對于選中的個體以一定的機率随機地改變串結構資料中某個串的值。變異發生的機率很低，通常取0.001-0.01之間。

Matlab調用函數

function [xo,fo] = genetic(f,x0,l,u,Np,Nb,Pc,Pm,eta,kmax)

%f為待求函數,x0初值，l，u上下限，Np群體大小，Nb每一個變量的基因值（二進制數）

%Pc交叉機率，Pm變異機率，eta學習率，kmax最大疊代次數

主程式檔案：

function [xo,fo] = genetic(f,x0,l,u,Np,Nb,Pc,Pm,eta,kmax)
% 基因算法求f(x）最小值 s.t. l <= x <= u
%f為待求函數,x0初值，l，u上下限，Np群體大小，Nb每一個變量的基因值（二進制數）
%Pc交叉機率，Pm變異機率，eta學習率，kmax最大疊代次數
N = length(x0);
%%%%%确定各變量預設值
if nargin < 10
    kmax = 100; %最大疊代次數預設為100
end
if nargin < 9|eta > 1|eta <= 0
    eta = 1;  %學習率eta,(0 < eta < 1)
end
if nargin < 8
    Pm = 0.01; %變異機率預設0.01
end
if nargin < 7
    Pc = 0.5; %交叉機率預設0.5
end
if nargin < 6
    Nb = 8*ones(1,N);%每一變量的基因值（二進制數）
end
if nargin < 5
    Np = 10; %群體大小（染色體數）
end
%%%%%生成初始群體
NNb = sum(Nb);
xo = x0(:)'; l = l(:)'; u = u(:)';
fo = feval(f,xo);
X(1,:) = xo;
for n = 2:Np
    X(n,:) = l + rand(size(x0)).*(u - l); %初始群體随機數組
end
P = gen_encode(X,Nb,l,u);  %編碼為2進制字串
for k = 1:kmax
    X = gen_decode(P,Nb,l,u);  %解碼為10進制數
    for n = 1:Np
        fX(n) = feval(f,X(n,:));
    end
    [fxb,nb] = min(fX);   %選擇最适合的，函數值最小的
    if fxb < fo
        fo = fxb;
        xo = X(nb,:);
    end
    fX1 = max(fxb) - fX; %将函數值轉化為非負的适合度值
    fXm = fX1(nb);
    if fXm < eps  %如果所有的染色體值相同，終止程式
        return;
    end
    %%%%%複制下一代
    for n = 1:Np
        X(n,:) = X(n,:) + eta*(fXm - fX1(n))/fXm*(X(nb,:) - X(n,:));%複制準則
    end
    P = gen_encode(X,Nb,l,u); %對下一代染色體編碼
    %%%%%%随機配對/交叉得新的染色體數組
    is = shuffle([1:Np]);
    for n = 1:2:Np - 1
        if rand < Pc
            P(is(n:n + 1),:) = crossover(P(is(n:n + 1),:),Nb);
        end
    end
    %%%%%%變異
    P = mutation(P,Nb,Pm);
end
           

function P = gen_encode(X,Nb,l,u)
%将群體X的狀态編碼為二進制數組P
Np=size(X,1); %群體大小
N = length(Nb); %變量（狀态）維數
for n = 1:Np
    b2 = 0;
    for m = 1:N
        b1 = b2+1;
        b2 = b2 + Nb(m);
        Xnm =(2^Nb(m)- 1)*(X(n,m) - l(m))/(u(m) - l(m)); %編碼方程
        P(n,b1:b2) = dec2bin(Xnm,Nb(m)); %10進制轉換為2進制
    end
end
           

function X = gen_decode(P,Nb,l,u)
% 将二進制數組P解碼為群體X的狀态矩陣
Np = size(P,1); %群體大小
N = length(Nb); %變量維數
for n = 1:Np
    b2 = 0;
    for m = 1:N
        b1 = b2 + 1;
        b2 = b1 + Nb(m) - 1;
        X(n,m) = bin2dec(P(n,b1:b2))*(u(m) - l(m))/(2^Nb(m) - 1) + l(m); %解碼方程
    end
end
           

function chrms2 = crossover(chrms2,Nb)
%兩個染色體間的交叉
Nbb = length(Nb);
b2 = 0;
for m = 1:Nbb
    b1 = b2 + 1;
    bi = b1 + mod(floor(rand*Nb(m)),Nb(m));
    b2 = b2 + Nb(m);
    tmp = chrms2(1,bi:b2);
    chrms2(1,bi:b2) = chrms2(2,bi:b2);
    chrms2(2,bi:b2) = tmp;
end
           

function P = mutation(P,Nb,Pm)
%變異
Nbb = length(Nb);
for n = 1:size(P,1)
    b2 = 0;
    for m = 1:Nbb
        if rand < Pm
            b1 = b2 + 1;
            bi = b1 + mod(floor(rand*Nb(m)),Nb(m)); 
            b2 = b2 + Nb(m);
            P(n,bi) = ~P(n,bi);
        end
    end
end
           

function is = shuffle(is)
%打亂染色體次序
N = length(is);
for n = N:-1:2
    in = ceil(rand*(n - 1));
    tmp = is(in);is(in) = is(n); is(n) = tmp; %将第n個元素與第in個元素交換
end
           

執行個體：

求解無限制最優化問題。

f = inline('x(1)^4-16*x(1)^2-5*x(1)*x(2)+x(2)^4-16*x(2)^2-5*x(2)','x');
l = [-5 -5]; %下限
u = [5 5]; %上限
x0 = [0 0];
Np = 30; %群體大小
Nb = [12 12]; %代表每個變量的二進制位數
Pc = 0.5;  %交叉機率
Pm = 0.01; %變異機率
eta = 0.8;   %學習率
kmax = 200; %最大疊代次數
[xos,fos]=fminsearch(f,x0)
[xo_gen,fo_gen] = genetic(f,x0,l,u,Np,Nb,Pc,Pm,eta,kmax)