遺傳算法（Genetic Algorithm)

遺傳算法（Genetic Algorithm)

1 原理

遺傳算法（Genetic Algorithm）是一類借鑒生物界的進化規律（适者生存，優勝劣汰遺傳機制）演化而來的随機化搜尋方法。它是由美國的J.Holland教授1975年首先提出，其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有内在的隐并行性和更好的全局尋優能力；采用機率化的尋優方法，能自動擷取和指導優化的搜尋空間，自适應地調整搜尋方向，不需要确定的規則。遺傳算法的這些性質，已被人們廣泛地應用于組合優化、機器學習、信号處理、自适應控制和人工生命等領域。它是現代有關智能計算中的關鍵技術之一。

遺傳算法是模拟達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型。它的思想源于生物遺傳學和适者生存的自然規律，是具有“生存＋檢測”的疊代過程的搜尋算法。遺傳算法以一種群體中的所有個體為對象，并利用随機化技術指導對一個被編碼的參數空間進行高效搜尋。其中，選擇、交叉和變異構成了遺傳算法的遺傳操作；參數編碼、初始群體的設定、适應度函數的設計、遺傳操作設計、控制參數設定五個要素組成了遺傳算法的核心内容。 作為一種新的全局優化搜尋算法，遺傳算法以其簡單通用、魯棒性強、适于并行處理以及高效、實用等顯著特點，在各個領域得到了廣泛應用，取得了良好效果，并逐漸成為重要的智能算法之一。

遺傳算法的基本步驟 ：

我們習慣上把Holland1975年提出的GA稱為傳統的GA。它的主要步驟如下：

編碼：GA在進行搜尋之前先将解空間的解資料表示成遺傳空間的基因型串結構資料，這些串結構資料的不同組合便構成了不同的點。

初始群體的生成：随機産生N個初始串結構資料，每個串結構資料稱為一個個體， N個個體構成了一個群體。GA以這N個串結構資料作為初始點開始疊代。

适應性值評估檢測：适應性函數表明個體或解的優劣性。不同的問題，适應性函數的定義方式也不同。

選擇：選擇的目的是為了從目前群體中選出優良的個體，使它們有機會作為父代為下一代繁殖子孫。遺傳算法通過選擇過程展現這一思想，進行選擇的原則是适應性強的個體為下一代貢獻一個或多個後代的機率大。選擇實作了達爾文的适者生存原則。

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

變異：變異首先在群體中随機選擇一個個體，對于選中的個體以一定的機率随機地改變串結構資料中某個串的值。同生物界一樣，GA中變異發生的機率很低，通常取值在0.001~0.01之間。變異為新個體的産生提供了機會。

GA的計算過程為：

選擇編碼方式

産生初始群體

計算初始群體的适應性值

如果不滿足條件 {

   選擇

   交換

   變異

   計算新一代群體的适應性值

}

遺傳算法的特點：

遺傳算法作為一種快捷、簡便、容錯性強的算法，在各類結構對象的優化過程中顯示出明顯的優勢。與傳統的搜尋方法相比，遺傳算法具有如下特點：

搜尋過程不直接作用在變量上，而是在參數集進行了編碼的個體。此編碼操作， 使得遺傳算法可直接對結構對象（集合、序列、矩陣、樹、圖、鍊和表）進行操作。

搜尋過程是從一組解疊代到另一組解，采用同時處理群體中多個個體的方法，降 低了陷入局部最優解的可能性，并易于并行化。

采用機率的變遷規則來指導搜尋方向，而不采用确定性搜尋規則。

對搜尋空間沒有任何特殊要求（如連通性、凸性等），隻利用适應性資訊，不需要 導數等其它輔助資訊，适應範圍更廣。

2.執行個體

求函數-100*(x(1)^2-x(2))^2-(1-x(1))^2的最小值,兩個變量的取值範圍是from [-2.048;-2.048] to [2.048;2.048].

1）使用ga工具箱

X = ga(@(x) -100*(x(1)^2-x(2))^2-(1-x(1))^2,2,[],[],[],[],[-2.048;-2.048],[2.048;2.048])

2）未使用ga工具箱

% // Generic Algorithm for function f(x1,x2) optimum

clear all;

close all;

% // Parameters

Size = 80 ;

G = 100 ;

CodeL = 10 ;

umax = 2.048 ;

umin =- 2.048 ;

E = round(rand(Size, 2 * CodeL));     % // Initial Code 産生初始群體

% // Main Program

for  k = 1 : 1 :G

    time(k) = k;

     % // 選擇 % // 計算目标函數    

     for  s = 1 : 1 :Size  % // 對每一行

        m = E(s,:);

        y1 = 0 ;y2 = 0 ;

         % // Uncoding

        m1 = m( 1 : 1 :CodeL);

         for  i = 1 : 1 :CodeL

            y1 = y1 + m1(i) * 2 ^ (i - 1 );

        end

        x1 = (umax - umin) * y1 / 1023 + umin;  % // 計算參數1

        m2 = m(CodeL + 1 : 1 : 2 * CodeL);

         for  i = 1 : 1 :CodeL

            y2 = y2 + m2(i) * 2 ^ (i - 1 );

        end

        x2 = (umax - umin) * y2 / 1023 + umin;  % // 計算參數2

        F(s) = 100 * (x1 ^ 2 - x2) ^ 2 + ( 1 - x1) ^ 2 ;  % // 計算目标函數 ，F是向量

    end

    Ji = 1 . / F;

     % // ****** Step 1 : Evaluate BestJ ******

    BestJ(k) = min(Ji);  % // 找到F中最大的一項，儲存到向量BestJ

    fi = F;                           % // Fitness Function

    [Oderfi,Indexfi] = sort(fi);      % // Arranging fi small to bigger

    Bestfi = Oderfi(Size);            % // Let Bestfi=max(fi)

    BestS = E(Indexfi(Size),:);       % // Let BestS=E(m), m is the Indexfi belong to max(fi)

    bfi(k) = Bestfi;

     % // ****** Step 2 : Select and Reproduct Operation******選擇F較大的fi項

    fi_sum = sum(fi);

    fi_Size = (Oderfi / fi_sum) * Size;

    fi_S = floor(fi_Size);        % // Selecting Bigger fi value ,fi_S為80項的向量,每一項為0或1,1表示該項被選擇

    kk = 1 ;

     for  i = 1 : 1 :Size

         for  j = 1 : 1 :fi_S(i)         % // Select and Reproduce

            TempE(kk,:) = E(Indexfi(i),:);

            kk = kk + 1 ;               % // kk is used to reproduce

        end

    end  % // 選擇完畢

    fprintf( ' size TempE %//d\n ' ,size(TempE))

     % // ************ Step 3 : Crossover Operation ************交換

    pc = 0.60 ;

    n = ceil( 20 * rand);

     for  i = 1 : 2 :(Size - 1 )

        temp = rand;

         if  pc > temp                   % // Crossover Condition

             for  j = n: 1 : 20

                TempE(i,j) = E(i + 1 ,j);

                TempE(i + 1 ,j) = E(i,j);

            end

        end

    end

    TempE(Size,:) = BestS;

    E = TempE;

    fprintf( ' size E %//d\n ' ,size(E))

% //     pause

     % // ************ Step 4: Mutation Operation **************

     % // pm=0.001;

     % // pm=0.001-[1:1:Size]*(0.001)/Size; % // Bigger fi, smaller Pm

     % // pm=0.0;    % // No mutation

    pm = 0.1 ;      % // Big mutation

     for  i = 1 : 1 :Size

         for  j = 1 : 1 : 2 * CodeL

            temp = rand;

             if  pm > temp                 % // Mutation Condition

                 if  TempE(i,j) == 0

                    TempE(i,j) = 1 ;

                 else

                    TempE(i,j) = 0 ;

                end

            end

        end

    end

     % // Guarantee TempPop(30,:) is the code belong to the best individual(max(fi))

    TempE(Size,:) = BestS;

    E = TempE;

end

Max_Value = Bestfi

BestS

x1

x2

figure( 1 );

plot(time,BestJ);

xlabel( ' Times ' );ylabel( ' Best J ' );

figure( 2 );

plot(time,bfi);

xlabel( ' times ' );ylabel( ' Best F ' );