遺傳算法原理及其matlab程式實作

遺傳算法原理及其matlab實作

• 一、遺傳算法背景
• 二、遺傳算法原理及其數學模型
• • 2.1 編碼方式
  • • 2.1.1 二進制編碼
    • 2.1.2 浮點數編碼
  • 2.2 種群初始化
  • 2.3 計算初始種群的适應度函數值
  • 2.4 對初始種群個體進行篩選—天澤（以輪盤賭方式進行選擇）
  • 2.5 個體染色體交叉及突變
  • 2.6 精英選擇及其作用
• 三、遺傳算法中關鍵參數的設定及作用
• • 3.1 不同編碼方式的差別及其作用
  • 3.2 交叉算子與突變算子
  • 3.3 精英數量
• 四、遺傳算法matlab實作代碼
• • 4.1 主程式
  • 4.2 種群初始化
  • 4.3 适應度計算
  • 4.4 選擇淘汰
  • 4.5 變異處理
  • 4.6 變異是否超出自變量範圍判斷
  • 4.7 交叉處理
  • 4.8 最差個體統計
  • 4.9 計算平均适應度值
  • 4.10 繪制結果
  • 4.11 仿真效果如下：
• 5 結尾篇

一、遺傳算法背景

    遺傳算法的主要思想是借鑒于達爾文的自然選擇下的進化論模型。通過借鑒生物進化論，遺傳算法将要解決的問題模拟成一個生物進化的過程，通過複制、交叉、突變等操作産生下一代的解，并逐漸淘汰掉适應度函數值低的解，增加适應度函數值高的解。這樣進化N代後就很有可能會進化出适應度函數值很高的個體，也就是你的目标函數值的最優化結果。是時候展現真正的技術了：

    遺傳算法中對目标的優化過程就好比生活中妹子在找男友時不斷優化一樣。假定影響妹子找男友的标準受兩個變量的影響（也就是我們在優化時的自變量），此處假定為顔值和能力。最後對男生的綜合評價（也就是适應度函數值）當然越高越好，于是乎在妹子一輪又一輪的篩選中（也就是遺傳算法中的疊代過程）最後找到自己最滿意的那位，但是記住，在這個過程中妹子可不會傻乎乎的減少自己的樣本量，她會将評分低的個體淘汰後再引入新個體，這樣才能保住自己最後找到的是最滿意的！欲知妹子如何進行篩選，又如何引入新樣本，請客官往下看：

二、遺傳算法原理及其數學模型

    看了遺傳算法的背景介紹發現好像也沒多難，事實真的如此嗎？對人而言，是乎很好了解，可問題是我們是在計算機上進行這個過程，該如何讓計算機了解剛才的過程呢？

    假的在妹子心中對男友名額的方式為：

f ( x , y ) = s i n ( x ) + c o s ( y ) + 0.1 ∗ x + 0.1 ∗ y f(x,y) =sin(x)+cos(y)+0.1*x+0.1*y f(x,y)=sin(x)+cos(y)+0.1∗x+0.1∗y

其中：x：代表男生的顔值       y：代表男生的能力

2.1 編碼方式

    首先，我們将計算機假定成生活裡的妹子，現在她要開始找男朋友了！！！

    在該執行個體中，一個包含兩條條染色體，分别為x，y。染色體上各自包含一組基因組。

    基因 ( Gene ) ：一個遺傳因子。

    染色體 ( Chromosome ) ：一組的基因，有N個基因片段組成。

    個體 ( individual ) ：單個生物，由M條染色體構成。

    群體（population）：一群個體。

    在上述的例子中自變量有x，y。每個染色體由N個基因片段組成（由幾個基因片段取決于你的編碼精度），是以在本例子中：

一個個體=兩條條染色體(因為隻有兩個自變量)=N個基因

    将染色體表達為基因的過程，稱之為編碼，常見的編碼格式有二進制編碼和浮點編碼。

2.1.1 二進制編碼

    二進制編碼通俗的将就是将我們的自變量從十進制映射到N位的二進制，而N取決于我們要求的精度，例如求解精度為 e=0.02，那麼我們需要将x的區間[-10 10]，切分成(10−(−10))/0.02=1000 份。

又因為采用二進制編碼是以實際需要的編碼位數為：

2 9 = 512 < 1000 < 2 十 = 1024 2^9=512<1000<2^十 =1024 29=512<1000<2十=1024

故當我們需要精度為0.02時，采用二進制編碼最少需要10位數。那麼實際的求解精度為：

e = 20 / 1024 ≈ 0.01953 e=20/1024≈0.01953 e=20/1024≈0.01953

按照本文的例子，可以想到以下的映射,也就是對基因進行編碼：

0000000000=-10(因為0000000000代表 區間起點：-10) 1111111111=10(因為1111111111代表 區間終點：10) 這 0000000000，和 1111111111就 可以看成兩條染色體，其上分别有十個基因片段。

    同樣，既然有編碼，那一定就有解碼：其實說白了就是把二進制數轉換成十進制，然後在映射到自變量的取值範圍内。我就知道你們特麼絕對是一聽就懂，一做就不會！

我知道，你們現在絕對流着口水等例子呢！

例子來了！！！

假如，現在某個染色體的基因為0101101011，那麼它對應到自變量的取值空間（[-10 10]）的實數為

[ 0 ∗ 2 9 + 1 ∗ 2 8 + 0 ∗ 2 7 + 1 ∗ 2 6 + 1 ∗ 2 5 + 0 ∗ 2 4 + 1 ∗ 2 3 + 0 ∗ 2 2 + 1 ∗ 2 0 ] ∗ ( 20 / 1024 ) − ( − 10 ) = 17 [0*2^9+1*2^8+0*2^7+1*2^6+1*2^5+0*2^4+1*2^3+0*2^2+1*2^0]*(20/1024)-(-10)=17 [0∗29+1∗28+0∗27+1∗26+1∗25+0∗24+1∗23+0∗22+1∗20]∗(20/1024)−(−10)=17

懂了沒！！！

至于如何生成10位的二進制數，當然是用matlab裡面的rand指令了呀！！！生成一個1X10的矩陣就行了呀！！！

2.1.2 浮點數編碼

    至于浮點型編碼，其原理與二進制類似也是随機生成一個0到1之間的随機數，再映射到自變量取值空間，例如：0.3567對應的自變量實數為：

0.3567 ∗ [ 10 − ( − 10 ) ] − ( 10 ) = − 2.866 0.3567*[10-(-10)]-(10)=-2.866 0.3567∗[10−(−10)]−(10)=−2.866

2.2 種群初始化

    其實質就是生成一個初始化種群以供後面選擇，就像一開始妹子随機選了100個男的當備胎，最後的最優個體從這裡面不斷優化得到！！！

2.3 計算初始種群的适應度函數值

    對生成的初始種群計算其個體的适應度值，這時種群中的個體就會因為适應度值大小不同而産生先後順序，該過程可以了解為進化論物競天擇裡的物競過程，也就是自我競争，至于天澤，卧槽，當然是妹子說了算啊，不一定你最牛皮人家就一定要你啊，這就好比有錢人不一定比窮人活的久啊，雖然大機率确實有錢人活的久，啊！萬惡的金錢！！！可是我還是好想暴富！！！——真香！

2.4 對初始種群個體進行篩選—天澤（以輪盤賭方式進行選擇）

    自然界中，越有錢的個體就越有可能活得久。但是也不能說錢越多的就肯定活的久，隻能是從機率上來說更多。（畢竟有些人命是真的硬）。那麼我們怎麼來建立這種機率關系呢？下面我們介紹一種常用的選擇方法――輪盤賭（Roulette Wheel Selection）選擇法。假設種群數目,某個個體其适應度為,則其被選中的機率為：

比如我們有5條染色體，他們所對應的适應度評分分别為：5，7，10，13，15。

是以累計總适應度為：

是以各個個體被選中的機率分别為：

    呵呵，有人會問為什麼我們把它叫成輪盤賭選擇法啊？其實你隻要看看下圖的輪盤就會明白了。這個輪盤是按照各個個體的适應度比例進行分塊的。你可以想象一下，我們轉動輪盤，輪盤停下來的時候，指針會随機地指向某一個個體所代表的區域，那麼非常幸運地，這個個體被選中了。（很明顯，适應度評分越高的個體被選中的機率越大。）

是以說！！！有錢真的可以活的久！！！

2.5 個體染色體交叉及突變

    應該說這兩個步驟就是使到子代不同于父代的根本原因（注意，不是優于哈！！！，隻有經過自然的選擇後，才會出現子代優于父代的傾向，這就好像博士父母的子女照樣特麼國小考試不及格一個道理！！！）。對于這兩種遺傳操作，二進制編碼和浮點型編碼在處理上有很大的差異，其中二進制編碼的遺傳操作過程，比較類似于自然界裡面的過程，下面将分開講述。

    從生物學中我們可以知道，染色體聯會的過程中，分别來自父母雙方之間的染色體常常發生交叉，并且互相交換一部分染色體，如圖。事實上，二進制編碼的基因交換過程也非常類似這個過程――随機把其中幾個位于同一位置的編碼進行交換，産生新的個體，如圖所示。

    通過這兩種處理，可以使被選擇下來的個體産生新的變化，也就是産生新的變化！！！引入新變換來進行下一次自然選擇！！！

2.6 精英選擇及其作用

    精英選擇的作用是保留每一次疊代過程中的最優個體，讓其不再進行突變或者交叉變換，這樣就會最大程度的保持最優解的繼承性，而不會因為不斷的交叉或者突變而導緻最優解的結構被破壞，進而又産生一些沒有意義的疊代！！！至于精英保留的個數，目前沒有嚴格的理論支撐，我一般保留總群體的百分之十，也就是對前百分之十的個體進行直接保留！！！

三、遺傳算法中關鍵參數的設定及作用

3.1 不同編碼方式的差別及其作用

    根據個人經驗哈（高手勿噴！），二進制編碼進行優化的時候效果不明顯，就是容易陷入局部最優化，因為二進制編碼的話在進行交叉和突變後，把它反映到自變量實數空間後變化十分小，而不容易得到全局最優解！！！浮點型編碼的話，進行交叉和突變處理後反映到自變量實數空間變化較大，于上一代有明顯差異，更容易得到全局的最優解！！！

3.2 交叉算子與突變算子

    交叉算子與突變算子其實就是決定是否進行交叉變換和突變變換的門檻值，在傳統遺傳算法中，這兩個門檻值在疊代過程中是定值，其實這樣處理的效果不好，正确的是根據種群疊代的次數越來越多，也就是種群個體平均水準越來越好之後，交叉和突變越不容易進行，就好比，一個代碼，剛開始的時候很不完善，易于修改（看成突變和交叉），但是到後面不斷優化以後，代碼越來越完善之後，越來越不容易修改了（突變和交叉），是以在改進遺傳算法中，應該引入自适應交叉和突變算子，讓其随着疊代次數的增加而降低！！！至于按什麼規律降，，，，，，，，，這麼簡單的問題！！！，，，，，，，,，，我也不會啊！！！看論文吧

3.3 精英數量

    說實話，這玩意兒和交叉、突變算子變化剛好相反，這個是在前期保留的少，後期應該加多，畢竟到後期大家都牛皮的的嘛！！！至于按什麼規律保留，，，，我還是不知道！！！随緣，多試幾次，哪個效果好要哪個！！！

四、遺傳算法matlab實作代碼

    可以，又到了大家期待的代碼展示環節（别跟我說什麼原理，數學公式，沒代碼的講解都是扯淡！！！）下面我們将按照遺傳算法的流程圖順序相應給出代碼，為了便于了解，我們先給出主程式，再分别給出子程式：

4.1 主程式

clc;
clear;
%% 基礎參數
N = 100;  %種群内個體數目
N_chrom = 2; %染色體節點數，也就是每個個體有多少條染色體，其實說白了就是看适應函數裡有幾個自變量。
iter = 1000; %疊代次數，也就是一共有多少代
mut = 0.2;  %突變機率
acr = 0.2; %交叉機率
best = 1;
chrom_range = [-10 -10;10 10];%每個節點的值的區間
chrom = zeros(N, N_chrom);%存放染色體的矩陣
fitness = zeros(N, 1);%存放染色體的适應度
fitness_ave = zeros(1, iter);%存放每一代的平均适應度
fitness_best = zeros(1, iter);%存放每一代的最優适應度
chrom_best = zeros(1, N_chrom+1);%存放目前代的最優染色體與适應度
%% 初始化，這隻是用于生成第一代個體，并計算其适應度函數
chrom = Initialize(N, N_chrom, chrom_range); %初始化染色體
fitness = CalFitness(chrom, N, N_chrom); %計算适應度
chrom_best = FindBest(chrom, fitness, N_chrom); %尋找最優染色體
fitness_best(1) = chrom_best(end); %将目前最優存入矩陣當中
fitness_ave(1) = CalAveFitness(fitness); %将目前平均适應度存入矩陣當中
%% 用于生成以下其餘各代，一共疊代多少步就一共有多少代
for t = 2:iter
    chrom = MutChrom(chrom, mut, N, N_chrom, chrom_range, t, iter); %變異
    chrom = AcrChrom(chrom, acr, N, N_chrom); %交叉
    fitness = CalFitness(chrom, N, N_chrom); %計算适應度
    chrom_best_temp = FindBest(chrom, fitness, N_chrom); %尋找最優染色體
    if chrom_best_temp(end)>chrom_best(end) %替換掉目前儲存的最優
        chrom_best = chrom_best_temp;
    end
    %%替換掉最劣
    [chrom, fitness] = ReplaceWorse(chrom, chrom_best, fitness);
    fitness_best(t) = chrom_best(end); %将目前最優存入矩陣當中
    fitness_ave(t) = CalAveFitness(fitness); %将目前平均适應度存入矩陣當中
end
%% 作圖
figure(1)
plot(1:iter, fitness_ave, 'r', 1:iter, fitness_best, 'b')
grid on
legend('平均适應度', '最優适應度')
e=PlotModel(chrom_best);
%% 輸出結果
disp(['最優染色體為', num2str(chrom_best(1:end-1))])
disp(['最優适應度為', num2str(chrom_best(end))])
           

4.2 種群初始化

function chrom_new = Initialize(N, N_chrom, chrom_range)
chrom_new = rand(N, N_chrom);
for i = 1:N_chrom %每一列乘上範圍
    chrom_new(:, i) = chrom_new(:, i)*(chrom_range(2, i)-chrom_range(1, i))+chrom_range(1, i);
end
           

4.3 适應度計算

function fitness = CalFitness(chrom, N, N_chrom)
fitness = zeros(N, 1);
%開始計算适應度
for i = 1:N
    x = chrom(i, 1);
    y = chrom(i, 2);
    fitness(i) = sin(x)+cos(y)+0.1*x+0.1*y;%%該函數是定義的适應度函數，也可稱為代價函數，用于以後篩選個體的評價名額
end
           

4.4 選擇淘汰

function chrom_best = FindBest(chrom, fitness, N_chrom)
chrom_best = zeros(1, N_chrom+1);
[maxNum, maxCorr] = max(fitness);%因為所有個體對應的适應度大小都被存放在fitness矩陣中
chrom_best(1:N_chrom) =chrom(maxCorr, :);
chrom_best(end) = maxNum;
           

4.5 變異處理

%% 用于對每代共100個個體進行變異處理
function chrom_new = MutChrom(chrom, mut, N, N_chrom, chrom_range, t, iter)
for i = 1:N %%N是個體總數，也就是每一代有多少頭袋鼠
    for j = 1:N_chrom  %N_chrom是染色體節點數，就是有幾條染色體
        mut_rand = rand; %随機生成一個數，代表自然裡的基因突變，然後用改值來決定是否産生突變。
        if mut_rand <=mut  %mut代表突變機率，即産生突變的門檻值，如果小于0.2的基因突變機率門檻值才進行基因突變處理，否者不進行突變處理
            mut_pm = rand; %增加還是減少
            mut_num = rand*(1-t/iter)^2;
            if mut_pm<=0.5
                chrom(i, j)= chrom(i, j)*(1-mut_num);
            else
                chrom(i, j)= chrom(i, j)*(1+mut_num);
            end
            chrom(i, j) = IfOut(chrom(i, j), chrom_range(:, j)); %檢驗是否越界
        end
    end
end
chrom_new = chrom;%%把變異處理完後的結果存在新矩陣裡
           

4.6 變異是否超出自變量範圍判斷

function c_new = IfOut(c, range)
if c<range(1) || c>range(2)
    if abs(c-range(1))<abs(c-range(2))
        c_new = range(1);
    else
        c_new = range(2);
    end
else
    c_new = c;
end
           

4.7 交叉處理

function chrom_new = AcrChrom(chrom, acr, N, N_chrom)
for i = 1:N
    acr_rand = rand;%生成一個代表該個體是否産生交叉的機率大小，用于判别是否進行交叉處理
    if acr_rand<acr %如果該個體的交叉機率值大于産生交叉處理的門檻值，則對該個體的染色體（兩條，因為此案例中有兩個自變量）進行交叉處理
        acr_chrom = floor((N-1)*rand+1); %要交叉的染色體
        acr_node = floor((N_chrom-1)*rand+1); %要交叉的節點
        %交叉開始
        temp = chrom(i, acr_node);
        chrom(i, acr_node) = chrom(acr_chrom, acr_node); 
        chrom(acr_chrom, acr_node) = temp;
    end
end
chrom_new = chrom;
           

4.8 最差個體統計

function [chrom_new, fitness_new] = ReplaceWorse(chrom, chrom_best, fitness)

max_num = max(fitness);
min_num = min(fitness);
limit = (max_num-min_num)*0.2+min_num;

replace_corr = fitness<limit;

replace_num = sum(replace_corr);
chrom(replace_corr, :) = ones(replace_num, 1)*chrom_best(1:end-1);
fitness(replace_corr) = ones(replace_num, 1)*chrom_best(end);
chrom_new = chrom;
fitness_new = fitness;

end
           

4.9 計算平均适應度值

function fitness_ave = CalAveFitness(fitness)
[N ,~] = size(fitness);
fitness_ave = sum(fitness)/N;
           

4.10 繪制結果

function y = PlotModel(chrom)
x = chrom(1);
y = chrom(2);
z = chrom(3);
figure(2)
scatter3(x, y, z, 'ko')
hold on
[X, Y] = meshgrid(-10:0.1:10);
Z =sin(X)+cos(Y)+0.1*X+0.1*Y;
mesh(X, Y, Z)
y=1;
           

4.11 仿真效果如下：

5 結尾篇

用心花時間寫了這麼多，這麼久！！！懂我的意思吧！！！

[1]: https://blog.csdn.net/emiyasstar__/article/details/6938608/

[2]: https://blog.csdn.net/xuehuafeiwu123/article/details/52327559

[3]: https://blog.csdn.net/tsroad/article/details/52464108

[4]: https://blog.csdn.net/emiyasstar__/article/details/6938608/