遺傳算法及其MATLAB實現(xiàn)遺傳的生物學(xué)基礎(chǔ)遺傳算法的基本思想是基于Darwin進(jìn)化論和Mendel的遺傳學(xué)說的。Darwin進(jìn)化論最重要的是適者生存原理。它認(rèn)為每一物種在發(fā)展中越來越適應(yīng)環(huán)境。物種每個個體的基本特征由后代所繼承，但后代又會產(chǎn)生一些異于父代的新變化。在環(huán)境變化時，只有那些能適應(yīng)環(huán)境的個體特征方能保留下來。Mendel遺傳學(xué)說最重要的是基因遺傳原理。它認(rèn)為遺傳以密碼方式存在細(xì)胞中，并以基因形式包含在染色體內(nèi)。每個基因有特殊的位置并控制某種特殊性質(zhì)；所以，每個基因產(chǎn)生的個體對環(huán)境具有某種適應(yīng)性。因突變和基因雜交可產(chǎn)生更適應(yīng)于環(huán)境的后代。經(jīng)過存優(yōu)去劣的自然淘汰，適應(yīng)性高的基因結(jié)構(gòu)得以保存下來。

遺傳算法的概念遺傳算法是由進(jìn)化論和遺傳學(xué)機理而產(chǎn)生的直接搜索優(yōu)化方法。簡單遺傳算法有編解碼、個體適應(yīng)度評估和遺傳算法三大模塊組成，而遺傳運算又包括染色體復(fù)制、交叉變異等。遺傳算法基本操作流程圖

開始產(chǎn)生初始種群（編碼、解碼）計算個體適應(yīng)度值復(fù)制交配變異滿足終止條件？輸出最優(yōu)解結(jié)束YN1.編碼

遺傳算法的編碼有浮點編碼和二進(jìn)制編碼兩種。二進(jìn)制編碼符合計算機處理信息的原理，能對染色體進(jìn)行遺傳，編譯和突變等操作。設(shè)某一參數(shù)的取值范圍為（L，U），長度為k，則它共有種不同的編碼。000=0→L001=1→L+δ010=2→L+2δ011=3→L+3δ……11111111111111=-1→U2.解碼

解碼的目的是為了將不直觀的二進(jìn)制數(shù)據(jù)還原成十進(jìn)制。設(shè)二進(jìn)制，則對應(yīng)的解碼公式為例：設(shè)有參數(shù)x∈[2，3]，現(xiàn)用4位二進(jìn)制數(shù)對x進(jìn)行編碼，可得條染色體：0000000100100011010001010110011110001001101010111100110111101111任意數(shù)據(jù)代入譯碼公式，如x=0111

x=2+7*=2.4666667

4.復(fù)制運算

復(fù)制運算把當(dāng)前群體中適應(yīng)度較高的個體按某種規(guī)則或模型遺傳到下一代群體中。一般要求適應(yīng)度較高的個體將有更多的機會遺傳到下一代群體中。若設(shè)種群眾個體總數(shù)為N，個體i適應(yīng)度為fi：

?先計算出群體中所有個體的適應(yīng)度的總和∑fk(k=1.2,…,N);

?其次計算出每個個體的相對適應(yīng)度的大小fI/∑fK，它即為每個個體被遺傳到下一代群體中的概率。

?每個概率值組成一個區(qū)域，全部概率值之和為1；

?最后再產(chǎn)生一個0到1之間的隨機數(shù)，依據(jù)該隨機數(shù)出現(xiàn)在上述哪一個概率區(qū)域內(nèi)來確定各個個體被選中的次數(shù)。5．交配

對于選中用于繁殖下一代的個體，隨機地選擇兩個個體的相同位置，按交配概率P。在選中的位置實行交換。這個過程反映了隨機信息交換；目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個體。交配時，可實行單點交配或多點交配。

例如有個體S1=100101S2=010111選擇它們的左邊3位進(jìn)行交配操作，則有S1=010101S2=100111一般而言，交配概率P。取值為0.25—0.75。

6.突變

突變運算是使用基因位進(jìn)行基因突變。假設(shè)突變幾率Pm,即種群內(nèi)所有基因都有Pm的概率進(jìn)行突變，每個基因突變幾率是均等的。因此將產(chǎn)生一系列隨機數(shù)，然后將小于Pm的隨機數(shù)選出，并將其對應(yīng)的基因值翻轉(zhuǎn),即把1變?yōu)?，把0變?yōu)?。變異概率Pm與生物變異極小的情況一致，所以，Pm的取值較小，一般取0.01-0.2。例如有個體S＝101011。對其的第1，4位置的基因進(jìn)行變異，則有S‘=001111。單靠變異不能在求解中得到好處。但是，它能保證算法過程不會產(chǎn)生無法進(jìn)化的單一群體。因為在所有的個體一樣時，交叉是無法產(chǎn)生新的個體的，這時只能靠變異產(chǎn)生新的個體。也就是說，變異增加了全局優(yōu)化的特質(zhì)4復(fù)制概率Ps染色體被復(fù)制的概率（選擇率）：ps=fi/∑fi累積概率∑Pk平均適應(yīng)度：f=∑fi/n5新種群復(fù)制編號初始種群位串參數(shù)值x值目標(biāo)適應(yīng)值f(x)=x2復(fù)制概率率fi/∑fi累積概率下一代個體數(shù)目123401101110000100010011132489169576643610.140.490.060.310.140.630.691.001201總和∑平均值最大值11702935761.000.250.494.01.02.0初始種群參數(shù)計算二、遺傳選擇后的交配池（下劃線部分交叉）交配對象（隨機選擇）交叉位置（隨機選擇）新的種群xf(x)=x2011011100011000

10011214344220110011001110111000012252716144625729256總和∑平均值最大突變?nèi)∽儺惛怕蕄e=0.01，表示每100個體中有一個個體的一位發(fā)生變異。（暫不變異）新的種群，其平均值和最大值都有很大提高。均值：293→439

最大值：576→729

新種群中四個個體，有2個變好：25，25；2個變壞：12，16。三、再遺傳一代編號初始種群位串參數(shù)值x值目標(biāo)適應(yīng)值f(x)=x2復(fù)制概率率fi/∑fi累積概率下一代個體123401100110011101110000122527161446257292560.080.360.420.140.080.440.861.000121總和∑平均值最大000.250.42選擇后的交配池（下劃線部分交叉）交叉對象（隨機選擇）交叉位置（隨機選擇）新的種群xf(x)=x2110011101111011

1000021431133110111100111000

1001127252419729625576361總和∑平均值最大值2291572729例2用matlab實現(xiàn)遺產(chǎn)算法求解：maxf(x)=200e^(-0.05x)sin(x),x∈[-2,2]%子程序：將二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)，函數(shù)名稱存儲為transform2to10.mfunctionx=transform2to10(Population);BitLength=size(Population,2);x=Population(BitLength);fori=1:BitLength-1

x=x+Population(BitLength-i)*power(2,i);end%子程序:對于優(yōu)化最大值或極大值函數(shù)問題，目標(biāo)函數(shù)可以作為適應(yīng)度函數(shù)%函數(shù)名稱存儲為targetfun.mfunctiony=targetfun(x);%目標(biāo)函數(shù)y=200*exp(-0.05*x).*sin(x);%子程序:新種群選擇操作，函數(shù)名稱存儲為selection.mfunctionseln=selection(population,cumsump);%從種群中選擇兩個個體fori=1:2 r=rand;%產(chǎn)生一個隨機數(shù)

prand=cumsump-r; j=1; whileprand(j)<0 j=j+1; end seln(i)=j;%選中個體的序號end%子程序：判斷遺傳運算是否進(jìn)行交叉或變異，函數(shù)名稱存儲為IfCroIfMut.mfunctionpcc=IfCroIfMut(mutORcro);test(1:100)=0;l=round(100*mutORcro);test(1:1)=1;n=round(rand*99)+1;pcc=test(n);Fitvalue,cumsump]=fitnessfun(population);Generation=1;whileGeneration<Generationnmax+1forj=1:2:popsize%選擇操作

seln=selection(population,cumsump);%交叉操作

scro=crossover(population,seln,pcrossover);scnew(j,:)=scro(1,:);scnew(j+1,:)=scro(2,:);%變異操作

smnew(j,:)=mutation(scnew(j,:),pmutation);smnew(j+1,:)=mutation(scnew(j+1,:),pmutation);endpopulation=smnew;%產(chǎn)生了新的種群

%計算新種群的適應(yīng)度

[Fitvalue,cumsump]=fitnessfun(population);%記錄當(dāng)前代最好的適應(yīng)度和平均適應(yīng)度

[fmax,nmax]=max(Fitvalue);fmean=mean(Fitvalue);ymax(Generation)=fmax;[ymean(Generation)=fmean;%記錄當(dāng)前代的最佳染色體個體

x=transform2to10(population(nmax,:));%自變量取值范圍是[-22]，需要把經(jīng)過遺傳運算的最佳染色體整合到[-22]區(qū)間

xx=boundsbegin+x*(boundsend-boundsbegin)/(power((boundsend),BitLength)-1);xmax(Generation)=xx;Generation=Generation+1;endGeneration=Generation-1;%顯示結(jié)果Bestpoplation=xxBesttargetfunvalue=targetfun(xx)%繪制經(jīng)過遺傳運算后的適應(yīng)度曲線。一般的，如果進(jìn)化過程中種群的平均適應(yīng)度與最大適應(yīng)度在曲線上有相互%趨同的形態(tài)，表示算法收斂進(jìn)行的很順利，沒有出現(xiàn)震蕩；在這種前提下，最大適應(yīng)度個體連續(xù)若干代都沒有發(fā)生進(jìn)化表明種群已經(jīng)成熟%作圖figure(1);hand1=plot(1:Generation,ymax);set(hand1,'linestyle','-','linewidth',1.8,'marker','*','markersize',6)holdon;hand2=plot(1:Generation,ymean);set(hand2,'color','r','linestyle','-','linewidth',1.8,'marker','h','markersize',6)xlabel('進(jìn)化代數(shù)');ylabel('最大/平均適應(yīng)度');xlim([1Generationnmax]);legend('最大適應(yīng)度','平均適應(yīng)度');boxoff;holdoff;MATLAB遺傳算法工具箱GA工具箱——GAToolboxGA的計算過程流程圖編碼和種群生成種群適應(yīng)度估計選擇交叉變異GA的特點GA是對問題參數(shù)的編碼組進(jìn)行計算，而不是針對參數(shù)本身。GA的搜索是從問題解的編碼組開始搜索，而不是從單個解開始。GA使用目標(biāo)函數(shù)值（適應(yīng)度）這一信息進(jìn)行搜索，而不需導(dǎo)數(shù)等其他信息。GA算法使用的選擇，交叉，變異這三個算子都是隨機操作而不是確定規(guī)則

工具箱核心函數(shù)的用法⑴函數(shù)ga的語法格式為[x,fval,reason]=ga(@fitnessfun,nvars,options)其中x為經(jīng)過遺傳進(jìn)化以后自變量最佳染色體返回值；fval為最佳染色體的適應(yīng)度；reason為算法停止的原因；·fitnessfun為適應(yīng)度句柄函數(shù)；nvars為目標(biāo)函數(shù)自變量的個數(shù)；options為算法的屬性設(shè)置，該屬性是通過函數(shù)gaoptimset賦予的。⑵函數(shù)gaoptimset函數(shù)gaoptimset的語法格式為Options=gaoptimset(‘propertyName1’,’propertyValue1’,’propertyName2’,’propertyValue2’,’propertyName3’,’propertyValue3’……)函數(shù)gaoptimset的功能是設(shè)置遺傳算法的參數(shù)和句柄函數(shù)。函數(shù)gaoptimset常用的11種屬性屬性名默認(rèn)值實現(xiàn)功能PopinitRange[0，1]初始種群生成區(qū)間PopulationSize20種群規(guī)模CrossoverFraction0.8交配概率MigrationFraction0.2變異概率Genertations100超過進(jìn)化代數(shù)時算法停止TimeLimitinf超過運算時間限制時算法停止FitnessLimit-inf最佳個體小于等于適應(yīng)度闕值時算法停止StallgenLimit50超過連續(xù)代數(shù)不進(jìn)化則算法停止StalltimeLimit20超過連續(xù)時間不進(jìn)化則算法停止InitialPopulation[]初始化種群PlotFens[]繪圖函數(shù)，可供選擇的有·gaplotbestf，·gapotbestindnv等程序設(shè)計范例

求解目標(biāo)函數(shù)

此函數(shù)在[-30，