遺傳算法matlab例子

遺傳算法的概念最早是由BagleyJ.D于1967年提出的。后來Michigan大學的J.H.Holland教授于1975年開始對遺傳算法（GeneticAlgorithm,GA）的機理進行系統(tǒng)化的研究。遺傳算法是對達爾文生物進化理論的簡單模擬，其遵循“適者生存”、“優(yōu)勝略汰”的原理。遺傳算法模擬一個人工種群的進化過程，并且通過選擇、雜交以及變異等機制，種群經過若干代以后，總是達到最優(yōu)（或近最優(yōu)）的狀態(tài)。自從遺傳算法被提出以來，其得到了廣泛的應用，特別是在函數(shù)優(yōu)化、生產調度、模式識別、神經網絡、自適應控制等領域，遺傳算法更是發(fā)揮了重大的作用，大大提高了問題求解的效率。遺傳算法也是當前“軟計算”領域的重要研究課題。本文首先結合MATLAB對遺傳算法實現(xiàn)過程進行詳細的分析，然后通過1個實際的函數(shù)優(yōu)化案例對其應用進行探討。1.遺傳算法實現(xiàn)過程現(xiàn)實生活中很多問題都可以轉換為函數(shù)優(yōu)化問題，所以本文將以函數(shù)優(yōu)化問題作為背景，對GA的實現(xiàn)過程進行探討。大部分函數(shù)優(yōu)化問題都可以寫成求最大值或者最小值的形式，為了不是一般性，我們可以將所有求最優(yōu)值的情況都轉換成求最大值的形式，例如，求函數(shù)f(x)的最大值，若是求函數(shù)f(x)的最小值，可以將其轉換成g(x)=-f(x)，然后求g(x)的最大值，這里x可以是一個變量，也可是是一個由k個變量組成的向量,

x=(x1,x2,…,xk)。每個xi,

i=1,2,…,k,其定義域為Di，Di=[ai,bi]。一般規(guī)定f(x)在其定義域內只取正值，若不滿足，可以將其轉換成以下形式，其中C是一個正常數(shù)。1.1編碼與解碼要實現(xiàn)遺傳算法首先需要弄清楚如何對求解問題進行編碼和解碼。對于函數(shù)優(yōu)化問題，一般來說，有兩種編碼方式，一是實數(shù)編碼，一是二進制編碼，兩者各有優(yōu)缺點，二進制編碼具有穩(wěn)定性高、種群多樣性大等優(yōu)點，但是需要的存儲空間大，需要解碼過程并且難以理解；而實數(shù)編碼直接用實數(shù)表示基因，容易理解并且不要解碼過程，但是容易過早收斂，從而陷入局部最優(yōu)。本文以最常用的二進制編碼為例，說明遺傳編碼的過程。從遺傳算法求解的過程來看，需要處理好兩個空間的問題，一個是編碼空間，另一個是解空間，如下圖所示從解空間到編碼空間的映射過程成為編碼過程；從編碼空間到解空間的映射過程成為解碼過程。下面就以求解一個簡單的一維函數(shù)f(x)=-(x-1)^2+4,x的取值范圍為[-1,3]最大值為例，來說明編碼及解碼過程。編碼：在編碼之前需要確定求解的精度，在這里，我們設定求解的精度為小數(shù)點后四位，即1e-4。這樣可以將每個自變量xi的解空間劃分為個等分。以上面這個函數(shù)為例，即可以將x的解空間劃分為(3-(-1))*1e+4=40000個等分。使ni滿足，這里ni表示使上式成立的最小整數(shù)，即表示自變量xi的基因串的長度。因為215<40000<216

，這里ni取16。例如00101就表示一個解空間中的基因串。表示所有自變量x=(x1,x2,…,xk)的二進制串的總長度稱為一個染色體(Chromosome)的長度或者一個個體(Individual)的長度，。編碼過程一般在實現(xiàn)遺傳算法之前需要指定。解碼：解碼即將編碼空間中的基因串翻譯成解空間中的自變量的實際值的過程。對于二進制編碼而言，每個二進制基因串都可以這樣翻譯成一個十進制實數(shù)值，。例如基因串00101，可以翻譯為，這里二進制基因串轉變成十進制是從左至右進行的。1.2初始化種群在開始遺傳算法迭代過程之前，需要對種群進行初始化。設種群大小為pop_size，每個染色體或個體的長度為chromo_size，種群的大小決定了種群的多樣性，而染色體的長度則是由前述的編碼過程決定的。一般隨機生成初始種群，但是如果知道種群的實際分布，也可以按照此分布來生成初始種群。假設生成的初始種群為(v1,v2,…,vpop_size)。1.3選擇操作選擇操作即從前代種群中選擇個體到下一代種群的過程。一般根據(jù)個體適應度的分布來選擇個體。以初始種群(v1,v2,…,vpop_size)為例，假設每個個體的適應度為(fitness(v1),fitness(v2),…,fitness(vpop_size))，一般適應度可以按照解碼的過程進行計算。以輪盤賭的方式選擇個體，如下圖隨機轉動一下輪盤，當輪盤停止轉動時，若指針指向某個個體，則該個體被選中。很明顯，具有較高適應度的個體比具有較低適應度的個體更有機會被選中。但是這種選擇具有隨機性，在選擇的過程中可能會丟失掉比較好的個體，所以可以使用精英機制，將前代最優(yōu)個體直接選到下一代中。輪盤賭選擇具體算法如下（這里假定種群中個體是按照適應度從小到大進行排列的，如果不是，可以按照某種排序算法對種群個體進行重排）：SelectionAlgorithmvarpop,pop_new;/*pop為前代種群，pop_new為下一代種群*/varfitness_value,fitness_table;/*fitness_value為種群的適應度，fitness_table為種群累積適應度*/fori=1:pop_sizer=rand*fitness_table(pop_size);/*隨機生成一個隨機數(shù)，在0和總適應度之間，因為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;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個個體賦給pop，最后一個為前代最優(yōu)個體保留*/endforendfor1.3交叉操作交叉操作是對任意兩個個體進行的（在這里我們實現(xiàn)的算法是直接對相鄰的兩個個體進行的）。隨機選擇兩個個體，如下圖所示然后隨機生成一個實數(shù)0<=r<=1,如果r<cross_rate，0<cross_rate<1為交叉概率，則對這兩個個體進行交叉，否則則不進行。如果需要進行交叉，再隨機選擇交叉位置(rand*chromo_size)，如果等于0或者1，將不進行交叉。否則將交叉位置以后的二進制串進行對換（包括交叉位置）。（注意：有時候還可以進行多點交叉，但是這里只討論單點交叉的情況）單點交叉具體算法如下：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，則不進行交叉*/endifforj=cross_pos:chromo_sizepop(i,j)<->pop(i+1,j);/*交換*/endforendifendfor1.4變異操作變異操作是對單個個體進行的。首先生成一個隨機實數(shù)0<=r<=1,如果r<mutate_rate，則對此個體進行變異操作，0<mutate_rate<1為變異概率，一般為一個比較小的實數(shù)。對每一個個體，進行變異操作，如下圖所示如個體需要進行變異操作，首先需要確定變異位置(rand*chromo_size)，若為0則不進行變異，否則則對該位置的二進制數(shù)字進行變異：1變成0,0變成1.（當然也可以選擇多點進行變異）單點變異的具體算法描述如下：Mutationalgorithmfori=1:pop_sizeifrand<mutate_rate/*mutate_rate為變異概率*/mutate_pos=round(rand*chromo_size);/*變異位置*/ifmutate_pos==0continue;/*若變異位置為0，則不進行變異*/endifpop(i,mutate_pos)=1-pop(i,mutate_pos);/*將變異位置上的數(shù)字至反*/endifendfor1.5遺傳算法流程遺傳算法計算流程圖如下圖所示1.6MATLAB程序實現(xiàn)初始化：%初始化種群%pop_size:種群大小%chromo_size:染色體長度functioninitilize(pop_size,chromo_size)globalpop;fori=1:pop_sizeforj=1:chromo_sizepop(i,j)=round(rand);endendcleari;clearj;計算適應度：（該函數(shù)應該根據(jù)具體問題進行修改，這里優(yōu)化的函數(shù)是前述的一維函數(shù)）%計算種群個體適應度，對不同的優(yōu)化目標，此處需要改寫%pop_size:種群大小%chromo_size:染色體長度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;對個體按照適應度大小進行排序：%對個體按適應度大小進行排序，并且保存最佳個體%pop_size:種群大小%chromo_size:染色體長度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:染色體長度%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;

交叉操作：%單點交叉操作%pop_size:種群大小%chromo_size:染色體長度%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;

變異操作：%單點變異操作%pop_size:種群大小%chromo_size:染色體長度%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:輸入染色體長度%generation_size:輸入迭代次數(shù)%cross_rate:輸入交叉概率%cross_rate:輸入變異概率%elitism:輸入是否精英選擇%m:輸出最佳個體%n:輸出最佳適應度%p:輸出最佳個體出現(xiàn)代%q:輸出最佳個體自變量值function[m,n,p,q]=GeneticAlgorithm(pop_size,chromo_size,generation_size,cross_rate,mutate_rate,elitism)globalG;%當前代globalfitness_value;%當前代適應度矩陣globalbest_fitness;%歷代最佳適應值globalfitness_avg;%歷代平均適應值矩陣globalbest_individual;%歷代最佳個體globalbest_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);%初始化forG=1:generation_sizefitness(pop_size,chromo_size);%計算適應度rank(pop_size,chromo_size);%對個體按適應度大小進行排序selection(pop_size,chromo_size,eli