遺傳算法詳解及matlab代碼實作

這裡寫目錄标題

• 1. 定義
• • • • 主要特點
      • 對象
      • 基本操作
      • 核心内容
• 2. 常用詞彙
• • • • 基因型(genotype)
      • 表現型
      • 編碼(coding)
      • 解碼(decoding)
      • 個體（individual）
      • 種群（population）
      • 适應度(fitness)
• 3. 形象了解
• 4. 遺傳算法的一般步驟
• 5. matlab代碼實作
• • • • 涉及了一個染色體長度的計算
      • 按照算法流程圖進行
      • 0 主函數
      • 1 初始化
      • 2 計算目标函數值
      • 3 計算适應度函數
      • 4 選擇
      • 5 交叉
      • 6 變異
      • 7 求出每一代 中最大得适應值及其個體
• 6. gaot 工具箱實作遺傳算法
• • • • 注：gaot工具箱要加入路徑

1. 定義

遺傳算法（Genetic Algorithm, GA）是模拟達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模拟自然進化過程搜尋最優解的方法。

主要特點

• 直接對結構對象進行操作，不存在求導和函數連續性的限定；
• 具有内在的隐并行性和更好的全局尋優能力；
• 采用機率化的尋優方法，不需要确定的規則就能自動擷取和指導優化的搜尋空間，自适應地調整搜尋方向。

對象

一種群體中的所有個體

基本操作

選擇、交叉和變異

核心内容

• 參數編碼
• 初始群體的設定
• 适應度函數的設計
• 遺傳操作設計
• 控制參數設定

2. 常用詞彙

基因型(genotype)

性狀染色體的内部表現。

編碼樣式，把自變量轉換為如二進制數串。

方法有：二進制編碼法、浮點編碼法、符号編碼法。

表現型

染色體決定的性狀的外部表現。

自變量取值。

編碼(coding)

DNA中遺傳資訊在一個長鍊上按一定的模式排列。

遺傳編碼可看作從表現型到基因型的映射。

解碼(decoding)

基因型到表現型的映射。

個體（individual）

指染色體帶有特征的實體。

就是一個基因型的樣本

種群（population）

個體的集合，該集合内個體數稱為種群。

樣本集合

适應度(fitness)

度量某個物種對于生存環境的适應程度。

評價名額函數

3. 形象了解

既然我們把函數曲線了解成一個一個山峰和山谷組成的山脈。那麼我們可以設想所得到的每一個解就是一隻袋鼠，我們希望它們不斷的向着更高處跳去，直到跳到最高的山峰。是以求最大值的過程就轉化成一個“袋鼠跳”的過程。

下面介紹介紹“袋鼠跳”的幾種方式。

1. 爬山算法：一隻袋鼠朝着比現在高的地方跳去。它找到了不遠處的最高的山峰。但是這座山不一定是最高峰。這就是爬山算法，它不能保證局部最優值就是全局最優值。
2. 模拟退火：袋鼠喝醉了。它随機地跳了很長時間。這期間，它可能走向高處，也可能踏入平地。但是，它漸漸清醒了并朝最高峰跳去。這就是模拟退火算法。
3. 遺傳算法：有很多袋鼠，它們降落到喜瑪拉雅山脈的任意地方。這些袋鼠并不知道它們的任務是尋找珠穆朗瑪峰。但每過幾年，就在一些海拔高度較低的地方射殺一些袋鼠。于是，不斷有袋鼠死于海拔較低的地方，而越是在海拔高的袋鼠越是能活得更久，也越有機會生兒育女。就這樣經過許多年，這些袋鼠們竟然都不自覺地聚攏到了一個個的山峰上，可是在所有的袋鼠中，隻有聚攏到珠穆朗瑪峰的袋鼠被帶回了美麗的澳洲。

4. 遺傳算法的一般步驟

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

   

   具體二進制編碼方式、輪盤選擇、單點交叉、基本位變異是最為簡單好了解的。參考

   https://blog.csdn.net/u012422446/article/details/68061932

https://www.jianshu.com/p/ae5157c26af9

在看代碼實作前，先看這個例子，會手動計算後更易了解。

算法例子：

https://blog.csdn.net/u012422446/article/details/68061932

5. matlab代碼實作

下面就用代碼實作袋鼠如何爬上這座山的最高峰。

% 即求下列函數的最大值 %

% f(x)=x+10sin(5x)+7cos(4x) x∈[0,10] %

涉及了一個染色體長度的計算

就是在自變量區間，多長的染色體滿足精度要求。

将 x 的值用一個10位的二值形式表示為二值問題，一個10位的二值數提供的分辨率是每位 (10-0)/(2^10-1)≈0.01

将變量域 [0,10] 離散化為二值域 [0,1023], x=0+10*b/1023, 其中 b 是 [0,1023] 中的一個二值數。

按照算法流程圖進行

初始化-進入循環（計算目标函數值-計算适應度-選擇-交叉-變異）-到達疊代次數-輸出循環過程中達到的最優值。

每個函數儲存為一個m檔案

0 主函數

% 下面舉例說明遺傳算法 %
% 求下列函數的最大值 %
% f(x)=x+10*sin(5x)+7*cos(4x) x∈[0,10] %
% 将 x 的值用一個10位的二值形式表示為二值問題，一個10位的二值數提供的分辨率是每為 (10-0)/(2^10-1)≈0.01 
% 将變量域 [0,10] 離散化為二值域 [0,1023], x=0+10*b/1023, 其中 b 是 [0,1023] 中的一個二值數。 %
% %
%--------------------------------------------------------------------------------------------------------------%
%--------------------------------------------------------------------------------------------------------------


% 2.0 主程式
%遺傳算法主程式
%Name:genmain05.m
%要求精度不大于0.01，
clear
clc
popsize=20;                         %群體大小
chromlength=10;                  %字元串長度(個體長度)
pc=0.6;                                %交叉機率，隻有在随機數小于pc時，才會産生交叉
pm=0.001;                           %變異機率


pop=initpop(popsize,chromlength);               %随機産生初始群體
for i=1:2000                                                        %20為遺傳代數
        [objvalue]=calobjvalue(pop);                  %計算目标函數
        fitvalue=calfitvalue(objvalue);                 %計算群體中每個個體的适應度

        [newpop]=selection(pop,fitvalue);                 %複制
        [newpop1]=crossover(newpop,pc);               %交叉
        [newpop2]=mutation(newpop1,pm);               %變異
        
        [objvalue]=calobjvalue(newpop2);                 %計算目标函數
        fitvalue=calfitvalue(objvalue);                       %計算群體中每個個體的适應度
        
        [bestindividual,bestfit]=best(newpop2,fitvalue);     %求出群體中适應值最大的個體及其适應值
        y(i)=bestfit;                                                              %傳回的 y 是自适應度值，而非函數值
        x(i)=decodechrom(bestindividual,1,chromlength)*10/1023;      %将自變量解碼成十進制
        pop=newpop2;
end
fplot('x+10*sin(5*x)+7*cos(4*x)',[0 10])
hold on
plot(x,y,'r*')                                          
hold on

[z ,index]=max(y);             %計算最大值及其位置
x5=x(index)                     %計算最大值對應的x值
ymax=z

           

1 初始化

主函數中調用，生成20個個體，按照精度要求選擇染色體的長度

initpop.m

% 2.1初始化(編碼)
% initpop.m函數的功能是實作群體的初始化，popsize表示群體的大小，chromlength表示染色體的長度(二值數的長度)，
% 長度大小取決于變量的二進制編碼的長度(在本例中取10位)。

%初始化
function pop=initpop(popsize,chromlength) 
pop=round(rand(popsize,chromlength)); 

% rand随機産生每個單元為 {0,1} 行數為popsize，列數為chromlength的矩陣，

% round對矩陣的每個單元進行圓整四舍五入。這樣産生的初始種群。
           

2 計算目标函數值

calobjvalue.m

% 2.2.3 計算目标函數值
% calobjvalue.m函數的功能是實作目标函數的計算，其公式采用本文示例仿真，可根據不同優化問題予以修改。
%遺傳算法子程式
%Name: calobjvalue.m
%實作目标函數的計算，将 二值域 中的數轉化為 變量域的數
function [objvalue]=calobjvalue(pop)
temp1=decodechrom(pop,1,10);   %将pop每行轉化成十進制數
x=temp1*10/1023;                         %在精度不大于0.01時，最小整數為1023，即需要10位二進制
objvalue=x+10*sin(5*x)+7*cos(4*x);   %計算目标函數值
           

decodechrom.m

（主要針對多個變量時候的一條染色體拆分，此處的例子不用拆分，pop1=pop）

% 2.2.2 将二進制編碼轉化為十進制數(2)
% decodechrom.m函數的功能是将染色體(或二進制編碼)轉換為十進制，參數spoint表示待解碼的二進制串的起始位置
% (對于多個變量而言，如有兩個變量，采用20為表示，每個變量10位，則第一個變量從1開始，另一個變量從11開始。本例為1)，
% 參數1ength表示所截取的長度（本例為10）。
%遺傳算法子程式
%Name: decodechrom.m
%将二進制編碼轉換成十進制

function pop2=decodechrom(pop,spoint,length)          %1  10
pop1=pop(:,spoint:spoint+length-1);
pop2=decodebinary(pop1);                                           %将pop每行轉換成十進制值，結果是20*1的矩陣
           

decodebinary.m

%産生 [2^n 2^(n-1) ... 1] 的行向量，然後求和，将二進制轉化為十進制



function pop2=decodebinary(pop)
[px,py]=size(pop);                   %求pop行和列數
for i=1:py
pop1(:,i)=2.^(py-i).*pop(:,i);
end
pop2=sum(pop1,2);                 %求pop1的每行之和
           

3 計算适應度函數

calfitvalue.m

為了計算後續機率，把小于0的目标函數值設為0

% 2.3 計算個體的适應值
%遺傳算法子程式
%Name:calfitvalue.m
%計算個體的适應值
function fitvalue=calfitvalue(objvalue)

[px,py]=size(objvalue);                   %目标值有正有負
for i=1:px
        if objvalue(i)>0                    
                temp=objvalue(i);          
        else
                temp=0.0;
        end
        fitvalue(i)=temp;
end
fitvalue=fitvalue';

           

4 選擇

輪盤法選擇。

原理如下

下面以輪盤賭選擇為例給大家講解一下：

假如有５條染色體，他們的适應度分别為５、８、３、７、２。

那麼總的适應度為：F = 5 + 8 + 3 + 7 + 2 = 25。

那麼各個個體的被選中的機率為：

α1 = ( 5 / 25 ) * 100% = 20%=0.2

α2 = ( 8 / 25 ) * 100% = 32%=0.32

α3 = ( 3 / 25 ) * 100% = 12%=0.12

α4 = ( 7 / 25 ) * 100% = 28%=0.28

α5 = ( 2 / 25 ) * 100% = 8%=0.08

怎麼用代碼實作呢？

思想：

把α1-α5，按比例順序，放到長度為1的一維的線上，開始随機數生成。

了解成向線上随機撒一個點。撒到哪一段就是選擇了哪個個體。

eg:

點到0.25時候，處在α1之後，在α2段，是以α2個體被選擇一次。

再随機生成0.55，在α3段，是以α3個體被選擇一次。

為了便于排序，先把點生成好，按順序排列，從小到大的進行比較。

即如下代碼：

selection.m

function [newpop]=selection(pop,fitvalue) 
totalfit=sum(fitvalue);                   %求适應值之和
fitvalue=fitvalue/totalfit;                %單個個體被選擇的機率
fitvalue=cumsum(fitvalue);            %如 fitvalue=[1 2 3 4]，則 cumsum(fitvalue)=[1 3 6 10]，不明白為什麼要累加 
[px,py]=size(pop);                       %20*10
ms=sort(rand(px,1));                   %從小到大排列
fitin=1;
newin=1;
while newin<=px                          %選出20個新個體，有重複情況，和上面介紹的方法不太一樣
        if(ms(newin))<fitvalue(fitin)
                newpop(newin,:)=pop(fitin,:);
                newin=newin+1;
        else
                fitin=fitin+1;
        end
end
           

5 交叉

單點交叉，以0.6的機率對相鄰的兩個個體染色體随機選擇交叉，并随機選擇交叉的位置。

crossover.m

% 2.5 交叉
% 交叉(crossover)，群體中的每個個體之間都以一定的機率 pc 交叉，即兩個個體從各自字元串的某一位置
% （一般是随機确定）開始互相交換，這類似生物進化過程中的基因分裂與重組。例如，假設2個父代個體x1，x2為：
% x1=0100110
% x2=1010001
% 從每個個體的第3位開始交叉，交又後得到2個新的子代個體y1，y2分别為：
% y1＝0100001
% y2＝1010110
% 這樣2個子代個體就分别具有了2個父代個體的某些特征。利用交又我們有可能由父代個體在子代組合成具有更高适合度的個體。
% 事實上交叉是遺傳算法差別于其它傳統優化方法的主要特點之一。
%遺傳算法子程式
%Name: crossover.m
%交叉



function [newpop]=crossover(pop,pc)          %pc=0.6
[px,py]=size(pop);
newpop=ones(size(pop));
for i=1:2:px-1                                             %步長為2，是将相鄰的兩個個體進行交叉
        if(rand<pc)
                cpoint=round(rand*py);
                newpop(i,:)=[pop(i,1:cpoint),pop(i+1,cpoint+1:py)];
                newpop(i+1,:)=[pop(i+1,1:cpoint),pop(i,cpoint+1:py)];
        else
                newpop(i,:)=pop(i,:);
                newpop(i+1,:)=pop(i+1,:);
        end
end
           

6 變異

mutation.m

% 2.6 變異
% 變異(mutation)，基因的突變普遍存在于生物的進化過程中。變異是指父代中的每個個體的每一位都以機率 pm 翻轉，
%即由“1”變為“0”，或由“0”變為“1”。
%遺傳算法的變異特性可以使求解過程随機地搜尋到解可能存在的整個空間，是以可以 在一定程度上 求得全局最優解。
%遺傳算法子程式
%Name: mutation.m
%變異



function [newpop]=mutation(pop,pm)
        [px,py]=size(pop);
        newpop=ones(size(pop));
        for i=1:px
                if(rand<pm)
                        mpoint=round(rand*py);     %産生的變異點在1-10之間
                        if mpoint<=0
                                mpoint=1;                         %變異位置
                        end
                        newpop(i,:)=pop(i,:);
                        if any(newpop(i,mpoint))==0
                                newpop(i,mpoint)=1;
                        else
                                newpop(i,mpoint)=0;
                        end
                else
                newpop(i,:)=pop(i,:);
        end
end
           

7 求出每一代 中最大得适應值及其個體

best.m

% 2.7 求出群體中最大得适應值及其個體
%遺傳算法子程式
%Name: best.m
%求出第 t 代群體中适應值最大的值
function [bestindividual,bestfit]=best(pop,fitvalue)
[px,py]=size(pop);
bestindividual=pop(1,:);
bestfit=fitvalue(1);
for i=2:px
        if fitvalue(i)>bestfit
                bestindividual=pop(i,:);
                bestfit=fitvalue(i);
        end
end

           

程式結構

運作主程式

6. gaot 工具箱實作遺傳算法

注：gaot工具箱要加入路徑

main.m

%% I. 清空環境變量
%optimtool    solver   中選擇   GA
%添加 gaot工具箱
clear all
clc

%% II. 繪制函數曲線
x = 0:0.01:10;
y =x+ 10*sin(5*x)+7*cos(4*x);

figure
plot(x, y)
xlabel('自變量')
ylabel('因變量')
title('y =x+ 10*sin(5*x) + 7*cos(4*x)')
grid

%% III. 初始化種群
initPop = initializega(50,[0 10],'fitness');    %種群大小；變量變化範圍；适應度函數的名稱
%看一下initpop     第二列代表   适應度函數值
%% IV. 遺傳算法優化
[x endPop bpop trace] = ga([0 10],'fitness',[],initPop,[1e-6 1 1],'maxGenTerm',200,...
                           'normGeomSelect',0.08,'arithXover',2,'nonUnifMutation',[2 25 3]);
%變量範圍上下界；适應度函數；适應度函數的參數；初始種群；精度和顯示方式；終止函數的名稱；
%終止函數的參數；選擇函數的名稱；選擇函數的參數；交叉函數的名稱；交叉函數的參數；變異函數的名稱；變異函數的參數
%  X    最優個體     endpop   優化終止的最優種群    bpop 最優種群的進化軌迹   trace   進化疊代過程中
%最優的适應度函數值和适應度函數值矩陣

%% V. 輸出最優解并繪制最優點
x
hold on
plot (endPop(:,1),endPop(:,2),'ro')

%% VI. 繪制疊代進化曲線
figure(2)
plot(trace(:,1),trace(:,3),'b:')
hold on
plot(trace(:,1),trace(:,2),'r-')
xlabel('Generation'); ylabel('Fittness');
legend('Mean Fitness', 'Best Fitness')


           

fitness.m

function [sol, fitnessVal] = fitness(sol, options)

x = sol(1);

fitnessVal = x+10*sin(5*x)+7*cos(4*x);
%如果求最小值   可以   1/ 10*sin(5*x)+7*cos(4*x);

end


           

ref

https://blog.csdn.net/xuehuafeiwu123/article/details/52327559

https://blog.csdn.net/lee_shuai/article/details/52510713

https://blog.csdn.net/on2way/article/details/40084449

https://blog.csdn.net/on2way/article/details/40084581

————————————————

版權聲明：本文為CSDN部落客「rrr2」的原創文章，

原文連結：https://blog.csdn.net/qq_35608277/article/details/83785678