助力國賽 | 第5彈 遺傳演算法

助力國賽 | 第5彈 遺傳演算法

來自專欄 MATLAB學習5 人贊了文章

前言

上次談到了灰色預測，我們繼續沿著大綱往前走，本次介紹的是遺傳演算法。

遺傳演算法（Genetic Algorithms，簡稱GA）是幾大非經典演算法中比較常見的一種，是模擬大自然生物進化機制的一種演算法，遵循適者生存、優勝劣汰的原則，通俗的講就是在尋優過程中有用的保留無用的則剔除。如果在實際問題和工程應用中表現為在所有可行的解決方法中找出最符合問題要求的條件得解決方法，即尋優。

由於考慮到這是初次接觸到遺傳演算法，因而將會通過一個簡單的小例子過一遍操作步驟和程序設計。MATLAB雖然有相應的工具包，但本次不採用，我們通過「硬編碼」來實現。因而本文先簡單介紹遺傳演算法的基本原理，然後通過一個求函數最大值的例子來進一步說明。如果各位想進一步加深了解遺傳演算法的相關情況，可以查閱有關資料。

• 基本原理
• 程序設計

基本原理

遺傳演算法（Genetic Algorithms，簡稱GA）是一種基於自然選擇原理和自然遺傳機制的搜索（尋優）演算法，它是模擬自然界中的生命進化機制，在人工系統中實現特定目標的優化。遺傳演算法的實質是通過群體搜索技術，根據適者生存的原則逐代進化，最終得到最優解或准最優解。它必須做以下操作：初始群體的產生、求每一個體的適應度、根據適者生存的原則選擇優良個體、被選出的優良個體兩兩配對，通過隨機交叉其染色體的基因並隨機變異某些染色體的基因後生成下一代群體，按此方法使群體逐代進化，直到滿足進化終止條件，可以用以下過程圖來表示：

下面簡單說明一下操作步驟：

1.編碼

遺傳演算法在進行搜索之前先將解空間的解數據表示成遺傳空間的基因型串結構數據，這些串結構數據的不同組合便構成了不同的點，所以我們可以通過控制編碼來控制求解問題的約束條件。

2.初始群體的生成

隨機產生N個初始串結構數據，每個串結構數據稱為一個個體，N個個體構成了一個群體，GA以這N個串結構數據作為初始點開始進行進化。

3.適應度評估

適應度表明個體或解的優劣性。不同的問題，適應性函數的定義方式也不同，這個要根據具體問題來確定。

4.選擇

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

5.交叉

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

6.變異

變異首先在群體中隨機選擇一個個體，對於選中的個體以一定的概率隨機地改變串結構數據中某個串的值。和生物界一樣，GA中變異發生的概率很低，通常取值很小。

程序設計

為了更好的是各位了解如何通過MATLAB來實現遺傳演算法，下面將會通過一個例子來說明。

在此之前，先介紹下遺傳演算法的適應值在MATLAB程序中的基本格式。

設有隨機初始化種群P(t) = {x1,x2,...xn}，計算P(t)中個體的適應值。

Begint = 0初始化P(t)計算P(t)的適應值while(不滿足停止準則) do begin t = t+1 從P(t+1)中選擇P(t) 重組P(t)計算P(t)的適應值end

題目如下：

首先對題目做一個分析，很容易看出這是一個周期函數，其最大值應該為17，在x=π/2取到。

先用MATLAB來做一個圖來看看樣子：

並且應用窮舉的方法來找出最大值

code:

x = 0:0.00001:5;y = 9.*sin(5*x)+8.*cos(4*x);max_y = max(y);i = find(y == max_y);max_x = 0+(i-1)*0.00001;[max_x max_y,]plot(x,y,max_x,max_y,r*);

1.初始化

遺傳演算法MATLAB子程序如下：

%初始化function pop = initpop(popsize,chromlength)pop = round(rand(popsize,chromlength));%rand隨機產生每個單元為{0,1}行數為popsize，列數為chromlength的矩陣%round對矩陣的每個單元進行圓整，從而產生初始種群end

其中，

• initpop.m函數的功能是實現群體的初始化
• popsize表示群體的大小
• chromlength表示染色體的長度（二值數的長度），長度大小取決於變數的二進位編碼的長度。

2.目標函數值

二進位數轉十進位數

code:

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

二進位編碼轉十進位數

code:

%將二進位編碼轉化成十進位function pop2 = decodechrom(pop,spoint,length)pop1 = pop(:,spoint:spoint+length-1)pop2 = decodebinary(pop1);end

decodechrom.m函數的功能是將染色體（或二進位編碼）轉化為十進位，參數spoint表示待解碼的二進位串的起始位值；參數length表示所截取的長度。

定義所求函數

為了方便以後修改，將目標函數單獨定義為一個函數文件。

code:

%目標函數function y = fun0(x) y = 9*sin(5*x)+8*cos(4*x);end

計算目標函數值

calobjvalue.m函數的功能是實現目標函數的計算。

code:

function [objvalue] = calobjvalue(pop)temp1 = decodechrom(pop,1,16); %將pop每行轉化為十進位x = temp1*5/(2^16-1); %將二值域中的數轉化為變數域的數objvalue= fun0(x); %計算目標函數值end

3.計算個體的適應值

code:

%計算個體的適應值function fitvalue = calfitvalue(objvalue)global Cmin;Cmin = 0;[px,py] = size(objvalue);for i = 1:px if objvalue(i) + Cmin>0 temp = objvalue(i) + Cmin; else temp = 0.0; end fitvalue(i) = temp;endfitvalue = fitvalue

4.選擇複製

選擇或者複製操作是決定哪些個體可以進入下一代。一般採用賭輪盤選擇法選擇，是一個比較好用且簡單的方法。一般根據如下方程進行選擇：

選擇的步驟如下（平台所限，使用圖片）：

code:

%選擇複製function [newpop] = selection(pop,fitvalue)totalfit = sum(fitvalue); %求適應值之和fitvalue = fitvalue/totalfit; %單個個體被選中的概率fitvalue = cumsum(fitvalue); %累積概率[px,py] = size(pop);ms = sort(rand(px,1)); %從小到大排列fitin = 1;newin = 1;while newin<=px if(ms(newin))<fitvalue(fitin) newpop(newin) = pop(fitin); newin = newin+1; else fitin = fitin+1; endend

5.交叉

群體中的每個個體之間都以一定的概率pc進行交叉，即兩個個體從各自字元串的某一位置（一般是隨機確定）開始相互交換，其實也就是生物進化中的基因分裂和重組。

例如，假設2個父代個體x1，x2為：

x1 = 0100110x2 = 1010001

如果從每個個體的第3位開始交叉，則新一代y1,y2為：

y1 = 0100001y2 = 1010110

這樣2個子代個體就分別具有了2個父代個體的某些特徵。

利用交叉我們有可能有父代個體在子代組合成更具有更高適應度的個體。事實上交叉也是遺傳演算法區別於其他傳統優化方法的主要特徵之一。

code:

%交叉function [newpop] = crossover(pop,pc)[px,py] = size(pop);newpop = ones(size(pop));for i = 1:2:px-1 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); endend

6.變異

變異，這個很好理解。基因突變是普遍存在於生物進化過程中的。變異是指父代中每個個體的每一位都以pm的概率翻轉，即「1」變成「0」，「0」變成「1」。

遺傳演算法的變異特性可以使得求解過程隨機地搜索到解可能存在的整個空間，因此可以在一定程度上求得全局最優解。

code:

%變異function [newpop] = mutation(pop,pm)[px,py] = size(pop);newpop = ones(size(pop));for i = 1:px if(rand<pm) mpoint = round(rand*py); 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); endend

7.求出群體中最大的適應值即個體

code:

%求出群體中最大的適應值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); endend

8.主程序

code:

clear allclcpopsize = 20; %群體大小chromlength = 16; %字元串長度（個體長度）pc = 0.7; %交叉概率pm = 0.005; %變異概率maxgen = 50; %迭代次數pop = initpop(popsize,chromlength); %隨機產生初始群體for i = 1:maxgen [objvalue] = calobjvalue(pop); %計算目標函數值 fitvalue = calfitvalue(objvalue); %計算群體中每個個體的適應度 [newpop] = selection(pop,fitvalue); %複製 [newpop] = crossover(pop,pc); %交叉 [newpop] = mutation(pop,pm); %變異 [bestindividual,bestfit] = best(pop,fitvalue); %求出群體中適應值最大的個體及其適應值 y(i) = max(bestfit); n(i) = i; pop5 = bestindividual; x(i) = decodechrom(pop5,1,chromlength)*5/(2^16-1); pop = newpop;end%繪製最優點圖像figure(1);ezplot(fun0,[0,5]);title(函數圖像);hold onplot(x(1),y(1),rp);[x(1),y(1)]hold off%繪製進化過程figure(2);plot(1:maxgen,y);grid onxlabel(遺傳代數);xlabel(解的變化);title(進化過程);

運行了很多次，挑選其中9次最好效果如下：

最後需要注意，對於參數確定的範圍為：

• 群體大小：20-100
• 迭代次數：100-500
• 交叉概率：0.4-0.99
• 變異概率：0.0001-0.1

並不是每一次運行結果都能滿足需要，遺傳演算法並沒有那樣的「偉大」。往往需要運行很多次，才能得出比較精確的答案。

編輯不易，歡迎推廣

推薦閱讀：