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

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

簡(jiǎn)單遺傳算法MATLAB實(shí)現(xiàn)

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

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

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

1. 遺傳算法實(shí)現(xiàn)過(guò)程

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

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

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

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

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

1.1 編碼與解碼

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

從遺傳算法求解的過(guò)程來(lái)看，需要處理好兩個(gè)空間的問(wèn)題，一個(gè)是編碼空間，另一個(gè)是解空間，如下圖所示

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

編碼：

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

解碼：

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

1.2 初始化種群

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

1.3 選擇操作

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

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

輪盤(pán)賭選擇具體算法如下（這里假定種群中個(gè)體是按照適應(yīng)度從小到大進(jìn)行排列的，如果不是，可以按照某種排序算法對(duì)種群個(gè)體進(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);/*隨機(jī)生成一個(gè)隨機(jī)數(shù)，在0和總適應(yīng)度之間，因?yàn)閒itness_table(pop_size)為最后一個(gè)個(gè)體的累積適應(yīng)度，即為總適應(yīng)度*/ first = 1; last = pop_size; mid = round((last+first)/2); idx = -1; /*下面按照排中法選擇個(gè)體*/ 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個(gè)個(gè)體賦給pop，最后一個(gè)為前代最優(yōu)個(gè)體保留*/ end for end for

1.3 交叉操作

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

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

單點(diǎ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 變異操作

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

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

單點(diǎ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 遺傳算法流程

遺傳算法計(jì)算流程圖如下圖所示

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

初始化：

%初始化種群 %pop_size: 種群大小 %chromo_size: 染色體長(zhǎng)度 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;

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

%計(jì)算種群個(gè)體適應(yīng)度，對(duì)不同的優(yōu)化目標(biāo)，此處需要改寫(xiě) %pop_size: 種群大小 %chromo_size: 染色體長(zhǎng)度 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;

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

%對(duì)個(gè)體按適應(yīng)度大小進(jìn)行排序，并且保存最佳個(gè)體 %pop_size: 種群大小 %chromo_size: 染色體長(zhǎng)度 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;

選擇操作：

%輪盤(pán)賭選擇操作 %pop_size: 種群大小 %chromo_size: 染色體長(zhǎng)度 %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;  

交叉操作：

%單點(diǎn)交叉操作 %pop_size: 種群大小 %chromo_size: 染色體長(zhǎng)度 %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;  

變異操作：

%單點(diǎn)變異操作 %pop_size: 種群大小 %chromo_size: 染色體長(zhǎng)度 %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;

打印算法迭代過(guò)程：

%打印算法迭代過(guò)程 %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: 輸入染色體長(zhǎng)度 %generation_size: 輸入迭代次數(shù) %cross_rate: 輸入交叉概率 %cross_rate: 輸入變異概率 %elitism: 輸入是否精英選擇 %m: 輸出最佳個(gè)體 %n: 輸出最佳適應(yīng)度 %p: 輸出最佳個(gè)體出現(xiàn)代 %q: 輸出最佳個(gè)體自變量值 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;%歷代最佳個(gè)體 global best_generation;%最佳個(gè)體出現(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); %計(jì)算適應(yīng)度 rank(pop_size, chromo_size); %對(duì)個(gè)體按適應(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);%打印算法迭代過(guò)程 m = best_individual;%獲得最佳個(gè)體 n = best_fitness;%獲得最佳適應(yīng)度 p = best_generation;%獲得最佳個(gè)體出現(xiàn)代 %獲得最佳個(gè)體變量值，對(duì)不同的優(yōu)化目標(biāo)，此處需要改寫(xiě) 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.  案例研究

對(duì)上一節(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)個(gè)體" m disp "最優(yōu)適應(yīng)度" n disp "最優(yōu)個(gè)體對(duì)應(yīng)自變量值" q disp "得到最優(yōu)結(jié)果的代數(shù)" p clear;  

結(jié)果如下：

"最優(yōu)個(gè)體"

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)個(gè)體對(duì)應(yīng)自變量值"

q =

1.0000

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

p =

74

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

算法迭代過(guò)程圖形：

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

3. 總結(jié)

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

posted on

Powered by:
博客園
Copyright © Alex Yu

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

本文編號(hào)：45545