遺傳算法matlab例子

遺傳算法的概念最早是由BagleyJ.D于1967年提出的。后來Michigan大學(xué)的J.H.Holland教授于1975年開始對(duì)遺傳算法（GeneticAlgorithm,GA）的機(jī)理進(jìn)行系統(tǒng)化的研究。遺傳算法是對(duì)達(dá)爾文生物進(jìn)化理論的簡(jiǎn)單模擬，其遵循“適者生存”、“優(yōu)勝略汰”的原理。遺傳算法模擬一個(gè)人工種群的進(jìn)化過程，并且通過選擇、雜交以及變異等機(jī)制，種群經(jīng)過若干代以后，總是達(dá)到最優(yōu)（或近最優(yōu)）的狀態(tài)。自從遺傳算法被提出以來，其得到了廣泛的應(yīng)用，特別是在函數(shù)優(yōu)化、生產(chǎn)調(diào)度、模式識(shí)別、神經(jīng)網(wǎng)絡(luò)、自適應(yīng)控制等領(lǐng)域，遺傳算法更是發(fā)揮了重大的作用，大大提高了問題求解的效率。遺傳算法也是當(dāng)前“軟計(jì)算”領(lǐng)域的重要研究課題。本文首先結(jié)合MATLAB對(duì)遺傳算法實(shí)現(xiàn)過程進(jìn)行詳細(xì)的分析，然后通過1個(gè)實(shí)際的函數(shù)優(yōu)化案例對(duì)其應(yīng)用進(jìn)行探討。1.遺傳算法實(shí)現(xiàn)過程現(xiàn)實(shí)生活中很多問題都可以轉(zhuǎn)換為函數(shù)優(yōu)化問題，所以本文將以函數(shù)優(yōu)化問題作為背景，對(duì)GA的實(shí)現(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可以是一個(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)只取正值，若不滿足，可以將其轉(zhuǎn)換成以下形式，其中C是一個(gè)正常數(shù)。1.1編碼與解碼要實(shí)現(xiàn)遺傳算法首先需要弄清楚如何對(duì)求解問題進(jìn)行編碼和解碼。對(duì)于函數(shù)優(yōu)化問題，一般來說，有兩種編碼方式，一是實(shí)數(shù)編碼，一是二進(jìn)制編碼，兩者各有優(yōu)缺點(diǎn)，二進(jìn)制編碼具有穩(wěn)定性高、種群多樣性大等優(yōu)點(diǎn)，但是需要的存儲(chǔ)空間大，需要解碼過程并且難以理解；而實(shí)數(shù)編碼直接用實(shí)數(shù)表示基因，容易理解并且不要解碼過程，但是容易過早收斂，從而陷入局部最優(yōu)。本文以最常用的二進(jìn)制編碼為例，說明遺傳編碼的過程。從遺傳算法求解的過程來看，需要處理好兩個(gè)空間的問題，一個(gè)是編碼空間，另一個(gè)是解空間，如下圖所示從解空間到編碼空間的映射過程成為編碼過程；從編碼空間到解空間的映射過程成為解碼過程。下面就以求解一個(gè)簡(jiǎn)單的一維函數(shù)f(x)=-(x-1)^2+4,x的取值范圍為[-1,3]最大值為例，來說明編碼及解碼過程。編碼：在編碼之前需要確定求解的精度，在這里，我們?cè)O(shè)定求解的精度為小數(shù)點(diǎn)后四位，即1e-4。這樣可以將每個(gè)自變量xi的解空間劃分為個(gè)等分。以上面這個(gè)函數(shù)為例，即可以將x的解空間劃分為(3-(-1))*1e+4=40000個(gè)等分。使ni滿足，這里ni表示使上式成立的最小整數(shù)，即表示自變量xi的基因串的長(zhǎng)度。因?yàn)?15<40000<216

，這里ni取16。例如00101就表示一個(gè)解空間中的基因串。表示所有自變量x=(x1,x2,…,xk)的二進(jìn)制串的總長(zhǎng)度稱為一個(gè)染色體(Chromosome)的長(zhǎng)度或者一個(gè)個(gè)體(Individual)的長(zhǎng)度，。編碼過程一般在實(shí)現(xiàn)遺傳算法之前需要指定。解碼：解碼即將編碼空間中的基因串翻譯成解空間中的自變量的實(shí)際值的過程。對(duì)于二進(jìn)制編碼而言，每個(gè)二進(jìn)制基因串都可以這樣翻譯成一個(gè)十進(jìn)制實(shí)數(shù)值，。例如基因串00101，可以翻譯為，這里二進(jìn)制基因串轉(zhuǎn)變成十進(jìn)制是從左至右進(jìn)行的。1.2初始化種群在開始遺傳算法迭代過程之前，需要對(duì)種群進(jìn)行初始化。設(shè)種群大小為pop_size，每個(gè)染色體或個(gè)體的長(zhǎng)度為chromo_size，種群的大小決定了種群的多樣性，而染色體的長(zhǎng)度則是由前述的編碼過程決定的。一般隨機(jī)生成初始種群，但是如果知道種群的實(shí)際分布，也可以按照此分布來生成初始種群。假設(shè)生成的初始種群為(v1,v2,…,vpop_size)。1.3選擇操作選擇操作即從前代種群中選擇個(gè)體到下一代種群的過程。一般根據(jù)個(gè)體適應(yīng)度的分布來選擇個(gè)體。以初始種群(v1,v2,…,vpop_size)為例，假設(shè)每個(gè)個(gè)體的適應(yīng)度為(fitness(v1),fitness(v2),…,fitness(vpop_size))，一般適應(yīng)度可以按照解碼的過程進(jìn)行計(jì)算。以輪盤賭的方式選擇個(gè)體，如下圖隨機(jī)轉(zhuǎn)動(dòng)一下輪盤，當(dāng)輪盤停止轉(zhuǎn)動(dòng)時(shí)，若指針指向某個(gè)個(gè)體，則該個(gè)體被選中。很明顯，具有較高適應(yīng)度的個(gè)體比具有較低適應(yīng)度的個(gè)體更有機(jī)會(huì)被選中。但是這種選擇具有隨機(jī)性，在選擇的過程中可能會(huì)丟失掉比較好的個(gè)體，所以可以使用精英機(jī)制，將前代最優(yōu)個(gè)體直接選到下一代中。輪盤賭選擇具體算法如下（這里假定種群中個(gè)體是按照適應(yīng)度從小到大進(jìn)行排列的，如果不是，可以按照某種排序算法對(duì)種群個(gè)體進(jìn)行重排）：SelectionAlgorithmvarpop,pop_new;/*pop為前代種群，pop_new為下一代種群*/varfitness_value,fitness_table;/*fitness_value為種群的適應(yīng)度，fitness_table為種群累積適應(yīng)度*/fori=1:pop_sizer=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)ifr>fitness_table(mid)first=mid;elseifr<fitness_table(mid)last=mid;elseidx=mid;break;endifmid=round((last+first)/2);if(last-first)==1idx=last;break;endifendwhileforj=1:chromo_sizepop_new(i,j)=pop(idx,j);endforendfor/*是否精英選擇*/ifelitismp=pop_size-1;elsep=pop_size;endiffori=1:pforj=1:chromo_sizepop(i,j)=pop_new(i,j);/*若是精英選擇，則只將pop_new前pop_size-1個(gè)個(gè)體賦給pop，最后一個(gè)為前代最優(yōu)個(gè)體保留*/endforendfor1.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)交叉具體算法如下：Crossoveralgorithmfori=1:2:pop_sizeif(rand<cross_rate)/*cross_rate為交叉概率*/cross_pos=round(rand*chromo_size);/*交叉位置*/ifor(cross_pos==0,cross_pos==1)continue;/*若交叉位置為0或1，則不進(jìn)行交叉*/endifforj=cross_pos:chromo_sizepop(i,j)<->pop(i+1,j);/*交換*/endforendifendfor1.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)變異的具體算法描述如下：Mutationalgorithmfori=1:pop_sizeifrand<mutate_rate/*mutate_rate為變異概率*/mutate_pos=round(rand*chromo_size);/*變異位置*/ifmutate_pos==0continue;/*若變異位置為0，則不進(jìn)行變異*/endifpop(i,mutate_pos)=1-pop(i,mutate_pos);/*將變異位置上的數(shù)字至反*/endifendfor1.5遺傳算法流程遺傳算法計(jì)算流程圖如下圖所示1.6MATLAB程序?qū)崿F(xiàn)初始化：%初始化種群%pop_size:種群大小%chromo_size:染色體長(zhǎng)度functioninitilize(pop_size,chromo_size)globalpop;fori=1:pop_sizeforj=1:chromo_sizepop(i,j)=round(rand);endendcleari;clearj;計(jì)算適應(yīng)度：（該函數(shù)應(yīng)該根據(jù)具體問題進(jìn)行修改，這里優(yōu)化的函數(shù)是前述的一維函數(shù)）%計(jì)算種群個(gè)體適應(yīng)度，對(duì)不同的優(yōu)化目標(biāo)，此處需要改寫%pop_size:種群大小%chromo_size:染色體長(zhǎng)度functionfitness(pop_size,chromo_size)globalfitness_value;globalpop;globalG;fori=1:pop_sizefitness_value(i)=0.;endfori=1:pop_sizeforj=1:chromo_sizeifpop(i,j)==1fitness_value(i)=fitness_value(i)+2^(j-1);endendfitness_value(i)=-1+fitness_value(i)*(3.-(-1.))/(2^chromo_size-1);fitness_value(i)=-(fitness_value(i)-1).^2+4;endcleari;clearj;對(duì)個(gè)體按照適應(yīng)度大小進(jìn)行排序：%對(duì)個(gè)體按適應(yīng)度大小進(jìn)行排序，并且保存最佳個(gè)體%pop_size:種群大小%chromo_size:染色體長(zhǎng)度functionrank(pop_size,chromo_size)globalfitness_value;globalfitness_table;globalfitness_avg;globalbest_fitness;globalbest_individual;globalbest_generation;globalpop;globalG;fori=1:pop_sizefitness_table(i)=0.;endmin=1;temp=1;temp1(chromo_size)=0;fori=1:pop_sizemin=i;forj=i+1:pop_sizeiffitness_value(j)<fitness_value(min);min=j;endendifmin~=itemp=fitness_value(i);fitness_value(i)=fitness_value(min);fitness_value(min)=temp;fork=1:chromo_sizetemp1(k)=pop(i,k);pop(i,k)=pop(min,k);pop(min,k)=temp1(k);endendendfori=1:pop_sizeifi==1fitness_table(i)=fitness_table(i)+fitness_value(i);elsefitness_table(i)=fitness_table(i-1)+fitness_value(i);endendfitness_tablefitness_avg(G)=fitness_table(pop_size)/pop_size;iffitness_value(pop_size)>best_fitnessbest_fitness=fitness_value(pop_size);best_generation=G;forj=1:chromo_sizebest_individual(j)=pop(pop_size,j);endendcleari;clearj;cleark;clearmin;cleartemp;cleartemp1;選擇操作：%輪盤賭選擇操作%pop_size:種群大小%chromo_size:染色體長(zhǎng)度%cross_rate:是否精英選擇functionselection(pop_size,chromo_size,elitism)globalpop;globalfitness_table;fori=1:pop_sizer=rand*fitness_table(pop_size);first=1;last=pop_size;mid=round((last+first)/2);idx=-1;while(first<=last)&&(idx==-1)ifr>fitness_table(mid)first=mid;elseifr<fitness_table(mid)last=mid;elseidx=mid;break;endmid=round((last+first)/2);if(last-first)==1idx=last;break;endendforj=1:chromo_sizepop_new(i,j)=pop(idx,j);endendifelitismp=pop_size-1;elsep=pop_size;endfori=1:pforj=1:chromo_sizepop(i,j)=pop_new(i,j);endendcleari;clearj;clearpop_new;clearfirst;clearlast;clearidx;clearmid;

交叉操作：%單點(diǎn)交叉操作%pop_size:種群大小%chromo_size:染色體長(zhǎng)度%cross_rate:交叉概率functioncrossover(pop_size,chromo_size,cross_rate)globalpop;fori=1:2:pop_sizeif(rand<cross_rate)cross_pos=round(rand*chromo_size);ifor(cross_pos==0,cross_pos==1)continue;endforj=cross_pos:chromo_sizetemp=pop(i,j);pop(i,j)=pop(i+1,j);pop(i+1,j)=temp;endendendcleari;clearj;cleartemp;clearcross_pos;

變異操作：%單點(diǎn)變異操作%pop_size:種群大小%chromo_size:染色體長(zhǎng)度%cross_rate:變異概率functionmutation(pop_size,chromo_size,mutate_rate)globalpop;fori=1:pop_sizeifrand<mutate_ratemutate_pos=round(rand*chromo_size);ifmutate_pos==0continue;endpop(i,mutate_pos)=1-pop(i,mutate_pos);endendcleari;clearmutate_pos;打印算法迭代過程：%打印算法迭代過程%generation_size:迭代次數(shù)functionplotGA(generation_size)globalfitness_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)globalG;%當(dāng)前代globalfitness_value;%當(dāng)前代適應(yīng)度矩陣globalbest_fitness;%歷代最佳適應(yīng)值globalfitness_avg;%歷代平均適應(yīng)值矩陣globalbest_individual;%歷代最佳個(gè)體globalbest_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);%初始化forG=1:generation_sizefitness(pop_size,chromo_size);%計(jì)算適應(yīng)度rank(pop_size,chromo_size);%對(duì)個(gè)體按適應(yīng)度大小進(jìn)行排序selection(pop_size,chromo_size,eli