遺傳算法及其應(yīng)用實(shí)例

PagePageof20fori=1:1:N[a,b]=max(y2);x10(1,i)=x20(1,b);x10(2,i)=x20(2,b);x11(1,i)=x21(1,b);x11(2,i)=x21(2,b);y2(1,b)=-inf;endendx11運(yùn)行結(jié)果顯示，遺傳算法常常在x2+x2，€2附近陷入局部最大，12而難以達(dá)到(x,x)，(0,0)的全局最大點(diǎn)。為此，應(yīng)對(duì)遺傳算法加以改進(jìn)。12之前的遺傳算法存在的一個(gè)缺陷是不能保證搜尋到的最佳個(gè)體可以被遺傳到下一代，因此可能會(huì)錯(cuò)過(guò)全局最優(yōu)點(diǎn)。父子混合選擇遺傳算法(Father-OffspringCombinedSelectionGeneticAlgorithm)對(duì)此加以改進(jìn)，該算法要求上一代的最佳個(gè)體必須被無(wú)條件地遺傳到下一代，因此記錄了到目前為止算法所發(fā)現(xiàn)的最佳個(gè)體，因而適應(yīng)度序列必然具有單調(diào)性，即關(guān)于進(jìn)化代數(shù)是單調(diào)不減的?？梢宰C明的是，該算法是遺傳算法保證收斂的執(zhí)行策略。父子混合選擇遺傳算法的執(zhí)行過(guò)程如下：步1(初始化)隨機(jī)產(chǎn)生M對(duì)母體組成初始種群X(0)，置tJ0。步2(種群進(jìn)化)獨(dú)立地對(duì)X(t)中的N對(duì)母體執(zhí)行交叉,生成中間種群Y(t((由N個(gè)中間個(gè)體組成)。獨(dú)立地對(duì)YW中的每一個(gè)中間個(gè)體執(zhí)行變異，生成子代種群Z(t)。2.3.在父代種群x(t)與子代種群Z(t)的并集X(t)€Z(t)中選擇N對(duì)母體作為新一代父代種群x(t+1)。步3(終止檢驗(yàn))一訃—>—>如果終止準(zhǔn)則滿足，停機(jī)并輸出X(t+1)中的最佳個(gè)體作為問(wèn)題的近似解，否則置t,t+1并轉(zhuǎn)步2。根據(jù)這一算法重新編寫(xiě)程序。>L=32；N=60；T=100;Pc=0.6；Pm=0.02；fori=1:1:Nx0(1,i)=unidrnd(2人L-1)；x0(2,i)=unidrnd(2人L-1)；endfort=1:1:Tfori=1:1:NgrayCode(1,i,:)=num2gray(x0(1,i),L)；grayCode(2,i,:)=num2gray(x0(2,i),L)；endfori=1:1:N/2ifrand()<Pcp=unidrnd(L)；forj=1:1:p-1grayCode(1,i+N,j)=grayCode(1,i,j)；grayCode(2,i+N,j)=grayCode(2,i,j)；grayCode(1,N-i+1+N,j)=grayCode(1,N-i+1,j)；grayCode(2,N-i+1+N,j)=grayCode(2,N-i+1,j)；endforj=p:1:LgrayCode(1,i+N,j)=grayCode(1,N-i+1,j)；grayCode(2,i+N,j)=grayCode(2,N-i+1,j)；grayCode(1,N-i+1+N,j)=grayCode(1,i,j)；grayCode(2,N-i+1+N,j)=grayCode(2,i,j)；endendendfori=N+1:1:2*Nforj=1:1:Lfork=1:1:2ifrand()<PmgrayCode(k,i,j)=1-grayCode(k,i,j);endendendendfori=N+1:1:2*Nx0(1,i)=gray2num(grayCode(1,i,:));x0(2,i)=gray2num(grayCode(2,i,:));endfori=1:1:2*Nx1(1,i)=double(x0(1,i))/(2人L-1)*10-5;x1(2,i)=double(x0(2,i))/(2人L-1)*10-5;temp(1,i)=x1(1,i)人2+x1(2,i)人2;y(1,i)=0.5-(sin(sqrt(temp(1,i)))人2-0.5)/(1+0.001temp(1,i));endfori=1:1:N[a,b]=max(y);x2(:,i)=x0(:,b);y(1,b)=-inf;endfori=1:1:Nx0(:,i)=x2(:,i);endendx1運(yùn)行結(jié)果顯示，該算法已經(jīng)搜索到了近似最優(yōu)解(x,x)€(0,0)12關(guān)于遺傳算法的收斂性問(wèn)題，這里可以給出幾個(gè)結(jié)論供參考。經(jīng)典遺傳算法并不保證全局最優(yōu)收斂，而只能在一定的約束條件下，實(shí)現(xiàn)全局最優(yōu)收斂。經(jīng)典遺傳算法可能出現(xiàn)未成熟收斂問(wèn)題，主要表現(xiàn)在以下兩個(gè)方面：一是群體中所有的個(gè)體都陷于同一適應(yīng)度而停止進(jìn)化；二是接近最優(yōu)解的個(gè)體總是被淘汰，進(jìn)化過(guò)程不收斂。抑制未成熟收斂的對(duì)策有：提高變異概率；調(diào)整選擇概率；維持群體中個(gè)體的多樣性等等。但這些方式都不能確保全局最優(yōu)收斂。但是，如果在每次迭代過(guò)程中保留最優(yōu)個(gè)體，那么就能夠保證其收斂。不過(guò)，保留最優(yōu)個(gè)體的遺傳算法在概率意義下的收斂，并不表明該方法一定具有很快的收斂速度，也不意味著該方法具有更佳的性能，因?yàn)樗赡苄枰L(zhǎng)的時(shí)間，其計(jì)算代價(jià)可能是無(wú)法接受的。在設(shè)計(jì)遺傳算法的編碼方式時(shí)，應(yīng)考慮以下問(wèn)題：（1）對(duì)于問(wèn)題空間的任何一個(gè)點(diǎn)有表達(dá)空間的一個(gè)點(diǎn)與之對(duì)應(yīng)，即問(wèn)題空間的所有可能解都能表示為所設(shè)計(jì)得染色體形式。（2）對(duì)于表達(dá)空間中的任何一個(gè)點(diǎn)都有問(wèn)題空間中的一個(gè)點(diǎn)與之對(duì)應(yīng)，即任何一個(gè)染色體都對(duì)應(yīng)于一個(gè)可能解。（3）問(wèn)題空間和表達(dá)空間一一對(duì)應(yīng)。這三點(diǎn)是編碼方式或策略應(yīng)遵守的普遍準(zhǔn)則，但是，在實(shí)際應(yīng)用中，對(duì)于很多問(wèn)題，很難設(shè)計(jì)出同時(shí)滿足上述三個(gè)性質(zhì)的編碼方案。此時(shí)，首先必須滿足第一個(gè)要求，即在保證所有可能解均可以被表示為染色體形式的前提下，是允許生成無(wú)用解的。最后，我們使用遺傳算法來(lái)解決一個(gè)更為貼近實(shí)際的問(wèn)題——旅行商問(wèn)題（TravellingSalesmanProblem）。問(wèn)題的具體表述如下：一個(gè)旅行商需要訪問(wèn)N個(gè)城市，在任意路線的兩個(gè)城市之間有一個(gè)關(guān)聯(lián)的費(fèi)用（例如公里數(shù)、航空費(fèi)用等）。找出一個(gè)費(fèi)用最少的路徑：從一個(gè)城市出發(fā)，經(jīng)過(guò)所有其他的城市一次且僅一次，然后回到出發(fā)點(diǎn)。這個(gè)問(wèn)題已被證明是NP難題，當(dāng)城市數(shù)量較大時(shí)，使用普通算法將耗費(fèi)大量的時(shí)間，因此我們嘗試使用遺傳算法來(lái)求解。適應(yīng)度評(píng)價(jià)函數(shù)的很直觀：我們要做的是評(píng)估路徑的長(zhǎng)度，然后按照長(zhǎng)度對(duì)路徑進(jìn)行排序，最短的就是最好的。因此，對(duì)于本問(wèn)題的求解，最重要的部分在于編碼方式的確定。假設(shè)我們有9個(gè)城市要訪問(wèn)，編號(hào)為1,2,,9。加入簡(jiǎn)單的用一個(gè)四位二進(jìn)制數(shù)(0001,0010,,1001)來(lái)代表每一個(gè)城市，二進(jìn)制串0001-0010-0011-0100-0101-0110-0111-1000-1001代表按照序號(hào)順序進(jìn)行訪問(wèn)。但問(wèn)題在于，交叉算子與變異算子很難應(yīng)用到這種編碼方式上，一般的交叉算子和變異算子會(huì)產(chǎn)生大量的不可行解，從而影響搜索速度。另一種方式是使用一個(gè)數(shù)字(例如1,2,,9)代表一個(gè)城市，通過(guò)對(duì)這9個(gè)數(shù)字排序構(gòu)造路徑，選擇合適的遺傳算子產(chǎn)生路徑。Davis(1985)提出了有序交叉(OrderCrossover)算子，爭(zhēng)好地解決了這個(gè)問(wèn)題，具體方式如下：有序交叉通過(guò)在一個(gè)雙親的路徑中選擇城市子序列創(chuàng)建子代。首先，選擇兩個(gè)劃分點(diǎn)，用"|"標(biāo)志，劃分點(diǎn)任意插入到雙親路徑中的相同位置，如：p1=(19214657183)p2=(45911876123)兩個(gè)子代和按下面的方法產(chǎn)生。首先，雙親中劃分點(diǎn)中間的部分復(fù)制到后代中：cl€(xxx|4657Ixx)

c2€(xxxI1876Ixx)然后，從一個(gè)雙親路徑的第二個(gè)劃分點(diǎn)開(kāi)始，從另外一個(gè)雙親路徑中來(lái)的城市按相同的順序復(fù)制。當(dāng)字符串的結(jié)尾到達(dá)時(shí)，轉(zhuǎn)從字符串的開(kāi)始處繼續(xù)，最終得到兩個(gè)子代：c1€(239I4657I18)

c2€(392I1876I45)一般來(lái)說(shuō)，對(duì)于TSP問(wèn)題，城市的順序在生成最少花費(fèi)路徑時(shí)非常重要，于是雙親路徑中的順序信息片段傳遞到子代路徑中去時(shí)很關(guān)鍵的。根據(jù)該思路編寫(xiě)程序如下：(測(cè)試數(shù)據(jù)來(lái)自TSPLIB95：rd100.tsp)rd100=importdata('rd100.tsp');cityAmount=100;fori=1:1:cityAmountforj=1:1:cityAmountdistance(i,j)=sqrt((rd100(i,2)-rd100(j,2))人2+(rd100(i,3)-rd100(j,3))人2)；endendL=100;N=200;T=10000;Pc=0.8;Pm=0.15;fori=1:1:Nx(i,:)=randperm(L);endfort=1:1:Tfori=1:1:N/2ifrand()<Pcp1=unidrnd(L);p2=unidrnd(L);ifp1>p2temp=p1;p1=p2;p2=temp;endflag1=zeros(1,L);flag2=zeros(1,L);forj=p1:1:p2x(i+N,j)=x(i,j);flag1(1,x(i,j))=1;x(N-i+1+N,j)=x(N-i+1,j);flag2(1,x(N-i+1,j))=1;endj=p2+1;k=1;while1ifj>Lj=1;endifk==p1k=p2+1;endifk>Lbreak;endifflag1(1,x(N-i+1,j))==0x(i+N,k)=x(N-i+1,j);j=j+1;k=k+1;elsej=j+1;endendj=p2+1;k=1;while1ifj>Lj=1;endifk==p1k=p2+1;endifk>Lbreak;endifflag2(1,x(i,j))==0x(N-i+1+N,k)=x(i,j);j=j+1;k=k+1;elsej=j+1;endendelsex(i+N,:)=x(i,:);x(N-i+1+N,:)=x(N-i+1,:);endendfori=N+1:1:2*Nifrand()<Pmp1=unidrnd(L);p2=unidrnd(L);j=min(p1,p2);k=max(p1,p2);whilej<ktemp=x(i,j);x(i,j)=x(i,k);x(i,k)=temp;j=j+1;k=k-1;endendendfori=1:1:2*Ny(1,i)=distance(x(i,1),x(i,L));forj=1:1:L-1y(1,i)=y(1,i)+distance(x(i,j),x(i,j+1));endendfori=1:1:N[a,b]=min(y);x1(i,:)=x(b,:);y(1,b)=inf;endfori=1:1:Nx(i,:)=x1(i,:);endendanswer=distance(x(1,1),x(1,L));forj=1:1:L-1answer=answer+distance（x（1,j）,x（1,j+1））;endanswer經(jīng)過(guò)幾次嘗試，本算法搜索到的近似最優(yōu)解為8289.4，與測(cè)試數(shù)據(jù)給出的實(shí)際最優(yōu)解7910相比，已經(jīng)較為接近，但差距不小。如果需要繼續(xù)提高算法的運(yùn)行效果，可以對(duì)一些初始化參數(shù)（種群大小，進(jìn)化代數(shù)上限，交叉概率，變異概率等）進(jìn)行調(diào)整，以獲得更佳的搜索能力。總結(jié)：遺傳算法的基本思想是：基于達(dá)爾文進(jìn)化論中的適者生存、優(yōu)勝劣汰的基本原理，按生物學(xué)的方法將問(wèn)題的求解表示成種群中的個(gè)體（用計(jì)算機(jī)編程時(shí)，一般使用二進(jìn)制碼串表示），從而構(gòu)造出一群包括N個(gè)可行解的種群，將它們置于問(wèn)題的環(huán)境中，根據(jù)適者生存原則,對(duì)該種群按照遺傳學(xué)的基本操作，不斷優(yōu)化生成新的種群，這樣一代代地不斷進(jìn)化，最后收斂到一個(gè)最適應(yīng)環(huán)境的最優(yōu)個(gè)體上，求得問(wèn)題的最優(yōu)解。遺傳算法具有以下幾個(gè)