發(fā)布時間：2016-05-16 06:40

  本文關(guān)鍵詞：遺傳算法，由筆耕文化傳播整理發(fā)布。

簡單遺傳算法MATLAB實現(xiàn)

遺傳算法的概念最早是由Bagley J.D 于1967年提出的。后來Michigan大學(xué)的J.H.Holland教授于1975年開始對遺傳算法（Genetic Algorithm, GA）的機理進(jìn)行系統(tǒng)化的研究。遺傳算法是對達(dá)爾文生物進(jìn)化理論的簡單模擬，其遵循“適者生存”、“優(yōu)勝略汰”的原理。遺傳算法模擬一個人工種群的進(jìn)化過程，并且通過選擇、雜交以及變異等機制，種群經(jīng)過若干代以后，總是達(dá)到最優(yōu)（或近最優(yōu)）的狀態(tài)。

自從遺傳算法被提出以來，其得到了廣泛的應(yīng)用，特別是在函數(shù)優(yōu)化、生產(chǎn)調(diào)度、模式識別、神經(jīng)網(wǎng)絡(luò)、自適應(yīng)控制等領(lǐng)域，遺傳算法更是發(fā)揮了重大的作用，大大提高了問題求解的效率。遺傳算法也是當(dāng)前“軟計算”領(lǐng)域的重要研究課題。

本文首先結(jié)合MATLAB對遺傳算法實現(xiàn)過程進(jìn)行詳細(xì)的分析，然后通過1個實際的函數(shù)優(yōu)化案例對其應(yīng)用進(jìn)行探討。

1. 遺傳算法實現(xiàn)過程

現(xiàn)實生活中很多問題都可以轉(zhuǎn)換為函數(shù)優(yōu)化問題，所以本文將以函數(shù)優(yōu)化問題作為背景，對GA的實現(xiàn)過程進(jìn)行探討。大部分函數(shù)優(yōu)化問題都可以寫成求最大值或者最小值的形式，為了不是一般性，我們可以將所有求最優(yōu)值的情況都轉(zhuǎn)換成求最大值的形式，例如，求函數(shù)f(x)的最大值，

若是求函數(shù)f(x)的最小值，可以將其轉(zhuǎn)換成g(x)=-f(x)，然后求g(x)的最大值，

這里x可以是一個變量，也可是是一個由k個變量組成的向量, x=(x1, x2, …, xk)。每個xi, i=1,2,…,k, 其定義域為Di，Di=[ai, bi]。

一般規(guī)定f(x)在其定義域內(nèi)只取正值，若不滿足，可以將其轉(zhuǎn)換成以下形式，

其中C是一個正常數(shù)。

1.1 編碼與解碼

要實現(xiàn)遺傳算法首先需要弄清楚如何對求解問題進(jìn)行編碼和解碼。對于函數(shù)優(yōu)化問題，一般來說，有兩種編碼方式，一是實數(shù)編碼，一是二進(jìn)制編碼，兩者各有優(yōu)缺點，二進(jìn)制編碼具有穩(wěn)定性高、種群多樣性大等優(yōu)點，但是需要的存儲空間大，需要解碼過程并且難以理解；而實數(shù)編碼直接用實數(shù)表示基因，容易理解并且不要解碼過程，但是容易過早收斂，，從而陷入局部最優(yōu)。本文以最常用的二進(jìn)制編碼為例，說明遺傳編碼的過程。

從遺傳算法求解的過程來看，需要處理好兩個空間的問題，一個是編碼空間，另一個是解空間，如下圖所示

從解空間到編碼空間的映射過程成為編碼過程；從編碼空間到解空間的映射過程成為解碼過程。下面就以求解一個簡單的一維函數(shù)f(x) = -(x-1)^2+4, x的取值范圍為[-1,3]最大值為例，來說明編碼及解碼過程。

編碼：

在編碼之前需要確定求解的精度，在這里，我們設(shè)定求解的精度為小數(shù)點后四位，即1e-4。這樣可以將每個自變量xi的解空間劃分為。編碼過程一般在實現(xiàn)遺傳算法之前需要指定。

解碼：

解碼即將編碼空間中的基因串翻譯成解空間中的自變量的實際值的過程。對于二進(jìn)制編碼而言，每個二進(jìn)制基因串都可以這樣翻譯成一個十進(jìn)制實數(shù)值，。例如基因串0000110110000101，可以翻譯為，這里二進(jìn)制基因串轉(zhuǎn)變成十進(jìn)制是從左至右進(jìn)行的。

1.2 初始化種群

在開始遺傳算法迭代過程之前，需要對種群進(jìn)行初始化。設(shè)種群大小為pop_size，每個染色體或個體的長度為chromo_size，種群的大小決定了種群的多樣性，而染色體的長度則是由前述的編碼過程決定的。一般隨機生成初始種群，但是如果知道種群的實際分布，也可以按照此分布來生成初始種群。假設(shè)生成的初始種群為(v1, v2, …, vpop_size)。

1.3 選擇操作

選擇操作即從前代種群中選擇個體到下一代種群的過程。一般根據(jù)個體適應(yīng)度的分布來選擇個體。以初始種群(v1, v2, …, vpop_size)為例，假設(shè)每個個體的適應(yīng)度為(fitness(v1), fitness(v2),…, fitness(vpop_size))，一般適應(yīng)度可以按照解碼的過程進(jìn)行計算。以輪盤賭的方式選擇個體，如下圖

隨機轉(zhuǎn)動一下輪盤，當(dāng)輪盤停止轉(zhuǎn)動時，若指針指向某個個體，則該個體被選中。很明顯，具有較高適應(yīng)度的個體比具有較低適應(yīng)度的個體更有機會被選中。但是這種選擇具有隨機性，在選擇的過程中可能會丟失掉比較好的個體，所以可以使用精英機制，將前代最優(yōu)個體直接選到下一代中。

輪盤賭選擇具體算法如下（這里假定種群中個體是按照適應(yīng)度從小到大進(jìn)行排列的，如果不是，可以按照某種排序算法對種群個體進(jìn)行重排）：

Selection Algorithm var pop, pop_new;/*pop為前代種群，pop_new為下一代種群*/ var fitness_value, fitness_table;/*fitness_value為種群的適應(yīng)度，fitness_table為種群累積適應(yīng)度*/ for i=1:pop_size r = rand*fitness_table(pop_size);/*隨機生成一個隨機數(shù)，在0和總適應(yīng)度之間，因為fitness_table(pop_size)為最后一個個體的累積適應(yīng)度，即為總適應(yīng)度*/ first = 1; last = pop_size; mid = round((last+first)/2); idx = -1; /*下面按照排中法選擇個體*/ while (first <= last) && (idx == -1) if r > fitness_table(mid) first = mid; elseif r < fitness_table(mid) last = mid; else idx = mid; break; end if mid = round((last+first)/2); if (last - first) == 1 idx = last; break; end if end while for j=1:chromo_size pop_new(i,j)=pop(idx,j); end for end elitism p = pop_size-1; else p = pop_size; end if for i=1:p for j=1:chromo_size pop(i,j) = pop_new(i,j);/*若是精英選擇，則只將pop_new前pop_size-1個個體賦給pop，最后一個為前代最優(yōu)個體保留*/ end for end for

1.3 交叉操作

交叉操作是對任意兩個個體進(jìn)行的（在這里我們實現(xiàn)的算法是直接對相鄰的兩個個體進(jìn)行的）。隨機選擇兩個個體，如下圖所示

然后隨機生成一個實數(shù)0<=r<=1, 如果r<cross_rate， 0<cross_rate<1為交叉概率，則對這兩個個體進(jìn)行交叉，否則則不進(jìn)行。如果需要進(jìn)行交叉，再隨機選擇交叉位置(rand*chromo_size)，如果等于0或者1，將不進(jìn)行交叉。否則將交叉位置以后的二進(jìn)制串進(jìn)行對換（包括交叉位置）。（注意：有時候還可以進(jìn)行多點交叉，但是這里只討論單點交叉的情況）

單點交叉具體算法如下：

Crossover algorithm for i=1:2:pop_size if(rand < cross_rate)/*cross_rate為交叉概率*/ cross_pos = round(rand * chromo_size);/*交叉位置*/ if or (cross_pos == 0, cross_pos == 1) continue;/*若交叉位置為0或1，則不進(jìn)行交叉*/ end if for j=cross_pos:chromo_size pop(i,j)<->pop(i+1,j);/*交換*/ end for end if end for

1.4 變異操作

變異操作是對單個個體進(jìn)行的。首先生成一個隨機實數(shù)0<=r<=1, 如果r<mutate_rate，則對此個體進(jìn)行變異操作， 0<mutate_rate<1為變異概率，一般為一個比較小的實數(shù)。對每一個個體，進(jìn)行變異操作，如下圖所示

如個體需要進(jìn)行變異操作，首先需要確定變異位置(rand*chromo_size)，若為0則不進(jìn)行變異，否則則對該位置的二進(jìn)制數(shù)字進(jìn)行變異：1變成0, 0變成1.（當(dāng)然也可以選擇多點進(jìn)行變異）

單點變異的具體算法描述如下：

Mutation algorithm for i=1:pop_size if rand < mutate_rate/*mutate_rate為變異概率*/ mutate_pos = round(rand*chromo_size);/*變異位置*/ if mutate_pos == 0 continue;/*若變異位置為0，則不進(jìn)行變異*/ end if pop(i,mutate_pos) = 1 - pop(i, mutate_pos);/*將變異位置上的數(shù)字至反*/ end if end for

1.5 遺傳算法流程

遺傳算法計算流程圖如下圖所示

1.6 MATLAB程序?qū)崿F(xiàn)

初始化：

%初始化種群 %pop_size: 種群大小 %chromo_size: 染色體長度 function initilize(pop_size, chromo_size) global pop; for i=1:pop_size for j=1:chromo_size pop(i,j) = round(rand); end end clear i; clear j;

計算適應(yīng)度：（該函數(shù)應(yīng)該根據(jù)具體問題進(jìn)行修改，這里優(yōu)化的函數(shù)是前述的一維函數(shù)）

%計算種群個體適應(yīng)度，對不同的優(yōu)化目標(biāo)，此處需要改寫 %pop_size: 種群大小 %chromo_size: 染色體長度 function fitness(pop_size, chromo_size) global fitness_value; global pop; global G; for i=1:pop_size fitness_value(i) = 0.; end for i=1:pop_size for j=1:chromo_size if pop(i,j) == 1 fitness_value(i) = fitness_value(i)+2^(j-1); end end fitness_value(i) = -1+fitness_value(i)*(3.-(-1.))/(2^chromo_size-1); fitness_value(i) = -(fitness_value(i)-1).^2+4; end clear i; clear j;

對個體按照適應(yīng)度大小進(jìn)行排序：

%對個體按適應(yīng)度大小進(jìn)行排序，并且保存最佳個體 %pop_size: 種群大小 %chromo_size: 染色體長度 function rank(pop_size, chromo_size) global fitness_value; global fitness_table; global fitness_avg; global best_fitness; global best_individual; global best_generation; global pop; global G; for i=1:pop_size fitness_table(i) = 0.; end min = 1; temp = 1; temp1(chromo_size)=0; for i=1:pop_size min = i; for j = i+1:pop_size if fitness_value(j)<fitness_value(min); min = j; min~=i temp = fitness_value(i); fitness_value(i) = fitness_value(min); fitness_value(min) = temp; for k = 1:chromo_size temp1(k) = pop(i,k); pop(i,k) = pop(min,k); pop(min,k) = temp1(k); i=1:pop_size if i==1 fitness_table(i) = fitness_table(i) + fitness_value(i); else fitness_table(i) = fitness_table(i-1) + fitness_value(i); end end fitness_table fitness_avg(G) = fitness_table(pop_size)/pop_size; if fitness_value(pop_size) > best_fitness best_fitness = fitness_value(pop_size); best_generation = G; for j=1:chromo_size best_individual(j) = pop(pop_size,j); end end clear i; clear j; clear k; clear min; clear temp; clear temp1;

選擇操作：

%輪盤賭選擇操作 %pop_size: 種群大小 %chromo_size: 染色體長度 %cross_rate: 是否精英選擇 function selection(pop_size, chromo_size, elitism) global pop; global fitness_table; for i=1:pop_size r = rand * fitness_table(pop_size); first = 1; last = pop_size; mid = round((last+first)/2); idx = -1; while (first <= last) && (idx == -1) if r > fitness_table(mid) first = mid; elseif r < fitness_table(mid) last = mid; else idx = mid; break; end mid = round((last+first)/2); if (last - first) == 1 idx = last; break; j=1:chromo_size pop_new(i,j)=pop(idx,j); elitism p = pop_size-1; else p = pop_size; end for i=1:p for j=1:chromo_size pop(i,j) = pop_new(i,j); end end clear i; clear j; clear pop_new; clear first; clear last; clear idx; clear mid;  

交叉操作：

%單點交叉操作 %pop_size: 種群大小 %chromo_size: 染色體長度 %cross_rate: 交叉概率 function crossover(pop_size, chromo_size, cross_rate) global pop; for i=1:2:pop_size if(rand < cross_rate) cross_pos = round(rand * chromo_size); if or (cross_pos == 0, cross_pos == 1) continue; end for j=cross_pos:chromo_size temp = pop(i,j); pop(i,j) = pop(i+1,j); pop(i+1,j) = temp; clear i; clear j; clear temp; clear cross_pos;  

變異操作：

%單點變異操作 %pop_size: 種群大小 %chromo_size: 染色體長度 %cross_rate: 變異概率 function mutation(pop_size, chromo_size, mutate_rate) global pop; for i=1:pop_size if rand < mutate_rate mutate_pos = round(rand*chromo_size); if mutate_pos == 0 continue; end pop(i,mutate_pos) = 1 - pop(i, mutate_pos); end end clear i; clear mutate_pos;

打印算法迭代過程：

%打印算法迭代過程 %generation_size: 迭代次數(shù) function plotGA(generation_size) global fitness_avg; x = 1:1:generation_size; y = fitness_avg; plot(x,y)

算法主函數(shù)：

%遺傳算法主函數(shù) %pop_size: 輸入種群大小 %chromo_size: 輸入染色體長度 %generation_size: 輸入迭代次數(shù) %cross_rate: 輸入交叉概率 %cross_rate: 輸入變異概率 %elitism: 輸入是否精英選擇 %m: 輸出最佳個體 %n: 輸出最佳適應(yīng)度 %p: 輸出最佳個體出現(xiàn)代 %q: 輸出最佳個體自變量值 function [m,n,p,q] = GeneticAlgorithm(pop_size, chromo_size, generation_size, cross_rate, mutate_rate, elitism) global G ; %當(dāng)前代 global fitness_value;%當(dāng)前代適應(yīng)度矩陣 global best_fitness;%歷代最佳適應(yīng)值 global fitness_avg;%歷代平均適應(yīng)值矩陣 global best_individual;%歷代最佳個體 global best_generation;%最佳個體出現(xiàn)代 fitness_avg = zeros(generation_size,1); disp "hhee" fitness_value(pop_size) = 0.; best_fitness = 0.; best_generation = 0; initilize(pop_size, chromo_size);%初始化 for G=1:generation_size fitness(pop_size, chromo_size); %計算適應(yīng)度 rank(pop_size, chromo_size); %對個體按適應(yīng)度大小進(jìn)行排序 selection(pop_size, chromo_size, elitism);%選擇操作 crossover(pop_size, chromo_size, cross_rate);%交叉操作 mutation(pop_size, chromo_size, mutate_rate);%變異操作 end plotGA(generation_size);%打印算法迭代過程 m = best_individual;%獲得最佳個體 n = best_fitness;%獲得最佳適應(yīng)度 p = best_generation;%獲得最佳個體出現(xiàn)代 %獲得最佳個體變量值，對不同的優(yōu)化目標(biāo)，此處需要改寫 q = 0.; for j=1:chromo_size if best_individual(j) == 1 q = q+2^(j-1); end end q = -1+q*(3.-(-1.))/(2^chromo_size-1); clear i; clear j;  

2.  案例研究

對上一節(jié)中的函數(shù)進(jìn)行優(yōu)化，設(shè)置遺傳算法相關(guān)參數(shù)，程序如下

function run_ga() elitism = true;%選擇精英操作 pop_size = 20;%種群大小 chromo_size = 16;%染色體大小 generation_size = 200;%迭代次數(shù) cross_rate = 0.6;%交叉概率 mutate_rate = 0.01;%變異概率 [m,n,p,q] = GeneticAlgorithm(pop_size, chromo_size, generation_size, cross_rate, mutate_rate,elitism); disp "最優(yōu)個體" m disp "最優(yōu)適應(yīng)度" n disp "最優(yōu)個體對應(yīng)自變量值" q disp "得到最優(yōu)結(jié)果的代數(shù)" p clear;  

結(jié)果如下：

"最優(yōu)個體"

m =

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

"最優(yōu)適應(yīng)度"

n =

4.0000

"最優(yōu)個體對應(yīng)自變量值"

q =

1.0000

"得到最優(yōu)結(jié)果的代數(shù)"

p =

74

此結(jié)果非常準(zhǔn)確。

算法迭代過程圖形：

從上圖中可以看出，隨著迭代次數(shù)的增加，算法逐漸收斂。

3. 總結(jié)

本文詳細(xì)的介紹了簡單遺傳算法的實現(xiàn)過程，并以一個簡單的函數(shù)優(yōu)化作為案例說明了其應(yīng)用。但是由于該測試函數(shù)過于簡單，在實際的應(yīng)用過程中，還需要對相關(guān)參數(shù)進(jìn)行調(diào)整，使其效率得到更大的提高。

posted on

Powered by:
博客園
Copyright © Alex Yu

  本文關(guān)鍵詞：遺傳算法，由筆耕文化傳播整理發(fā)布。

本文編號：45545