遺傳算法解決完美

用遺傳算法解決二元多峰函數(shù)的優(yōu)化問題實(shí)驗(yàn)?zāi)康?.1了解并掌握遺傳算法的原理，流程以及編碼方式；1.2自編遺傳算法程序?qū)astrigin函數(shù)進(jìn)行優(yōu)化并對(duì)運(yùn)行結(jié)果進(jìn)行分析。1.3利用遺傳算法gatool的圖形用戶界面GUI，進(jìn)彳亍Rastrigin函數(shù)優(yōu)化；實(shí)驗(yàn)條件2.1硬件環(huán)境：Inter(R)Core(TM)DuoCPUT55501.83GHz1.83GHz,2G內(nèi)存2.2軟件環(huán)境：WindowsXP,MATLAB7.0,gatool實(shí)驗(yàn)原理3.1遺傳算法簡(jiǎn)介：遺傳算法(GeneticAlgorithm)是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法，它最初由美國(guó)Michigan大學(xué)J.Holland教授于1975年首先提出來的，并出版了頗有影響的專著《AdaptationinNaturalandArtificialSystems》，GA這個(gè)名稱才逐漸為人所知，J.Holland教授所提出的GA通常為簡(jiǎn)單遺傳算法(SGA)。遺傳算法是一類借鑒生物界的進(jìn)化規(guī)律(適者生存，優(yōu)勝劣汰遺傳機(jī)制)演化而來的隨機(jī)化搜索方法。其主要特點(diǎn)是直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。遺傳算法的這些性質(zhì)，已被人們廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號(hào)處理、自適應(yīng)控制和人工生命等領(lǐng)域。它是現(xiàn)代有關(guān)智能計(jì)算中的關(guān)鍵技術(shù)。遺傳算法是從代表問題可能潛在的解集的一個(gè)種群(population)開始的，而一個(gè)種群則由經(jīng)過基因(gene)編碼的一定數(shù)目的個(gè)體(individual)組成。每個(gè)個(gè)體實(shí)際上是染色體(chromosome)帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn)(即基因型)是某種基因組合，它決定了個(gè)體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡(jiǎn)化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代(generation)演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個(gè)體的適應(yīng)度(fitness)大小選擇(selection)個(gè)體，并借助于自然遺傳學(xué)的遺傳算子(geneticoperators)進(jìn)行組合交叉(crossover)和變異(mutation)，產(chǎn)生出代表新的解集的種群。這個(gè)過程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過解碼(decoding)，可以作為問題近似最優(yōu)解。3.2遺傳算法的基本運(yùn)算過程：初始化:設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器t=0，設(shè)置最大進(jìn)化代數(shù)N，隨機(jī)生成n個(gè)個(gè)體作為初始群體pop。個(gè)體評(píng)價(jià):計(jì)算群體pop(i)中各個(gè)個(gè)體的適應(yīng)度。選擇運(yùn)算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個(gè)體直接遺傳到下一代或通過配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)估基礎(chǔ)上的。交叉運(yùn)算；將交叉算子作用于群體。所謂交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。遺傳算法中起核心作用的就是交叉算子。變異運(yùn)算:將變異算子作用于群體。即是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)。6)群體pop經(jīng)過選擇、交叉、變異運(yùn)算之后得到下一代群體pop。(7)終止條件判斷：以進(jìn)化過程中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出，終止計(jì)算。圖1:遺傳算法流程圖勺最小值4實(shí)驗(yàn)技術(shù)方案4.1自編程白勺最小值4實(shí)驗(yàn)技術(shù)方案4.1自編程白4.1.1Rastrigin函數(shù)具有兩個(gè)獨(dú)立變量的Rastrigin函數(shù)定義為:Ras(%,x2)=20+%2+x22-10(cos2兀x2+cos2兀%)維數(shù)為2,取值區(qū)間為[-5,5;-5,5],最小值為fmin=0。Rastrigin函數(shù)圖形如下：

圖2：Rastrigin函數(shù)圖形RaSirjgin函數(shù)圖形:4.1.2編碼方式對(duì)給定上下界和求解精度，利用函數(shù)length=ceil(log2((up-low)/prec+1))求得單個(gè)變量的編碼長(zhǎng)度，在此題中2個(gè)變量的上下界一樣，故編碼長(zhǎng)度也一樣用encode函數(shù)隨機(jī)產(chǎn)生n個(gè)長(zhǎng)度為2Xlength的二進(jìn)制代碼作為初始種群的個(gè)體用decode函數(shù)將個(gè)體的二進(jìn)制代碼解碼得出x1,乂2,代入fun函數(shù)求得函數(shù)值，根據(jù)Boltzmann選擇，T=999求得個(gè)函數(shù)值的適應(yīng)度，累加適應(yīng)度構(gòu)成一個(gè)賭輪，即在面積為一的賭輪中，函數(shù)值越小的個(gè)體被選中的概率越大。保存每一代的最小值為fmin。執(zhí)行select函數(shù)利用賭輪選擇n個(gè)新個(gè)體作為新的種群。執(zhí)行crossover函數(shù)，當(dāng)產(chǎn)生的隨機(jī)數(shù)小于交叉概率時(shí)，選擇一個(gè)個(gè)體，對(duì)選擇的兩個(gè)個(gè)體隨機(jī)產(chǎn)生一個(gè)位置作為交叉點(diǎn)，將其后面的代碼進(jìn)行交換。執(zhí)行mutation函數(shù)，當(dāng)產(chǎn)生的隨機(jī)數(shù)小于變異概率時(shí)，選擇一個(gè)個(gè)體，隨機(jī)產(chǎn)生一個(gè)位置作為變異點(diǎn)，將該點(diǎn)的編碼置1或置0。重復(fù)執(zhí)行解碼，求適應(yīng)度，選擇，交叉，變異幾個(gè)步驟直到完成N代演化。運(yùn)行結(jié)束輸出最小函數(shù)值fmin為最終優(yōu)化值。4.1.3運(yùn)行結(jié)果分析(1)當(dāng)n=20，N=100，prco=0.4，pmut=0.1時(shí)，運(yùn)行結(jié)果如下。

表1：n=20,N=100,prco=0.4,pmut=0.1時(shí)，運(yùn)行結(jié)果運(yùn)行次數(shù)12345（x1，x2）0.90771.00901.9040-0.0353-1.9939-0.0309-0.9945-0.9939-1.9871-0.0251fmin3.49275.63454.17231.99024.1058Rastrigin函數(shù)的當(dāng)前最小值與迭代次數(shù)的示意圖圖3Rastrigin函數(shù)的當(dāng)前最小值與迭代次數(shù)的示意圖22181614A12108642010和304U5060708090100gen由表1和圖3我們可以一看出，遺傳算法求解此時(shí)已經(jīng)陷入局部最小值，求解的值和全局最小值fmin=0相差甚遠(yuǎn)，所以我們要對(duì)種群數(shù)量n、迭代次數(shù)N、交叉概率prco以及變異率pmut進(jìn)行調(diào)整。（2）n，N不變，prco，pmut變化，運(yùn)行5次平均fmin運(yùn)行結(jié)果如下。

表2：n=20,N=100,prco,pmu變化時(shí)，運(yùn)行結(jié)果pmutprco0.20.40.60.15.37564.17234.59510.24.86496.65543.65750.34.63172.06463.30320.43.33852.07473.58860.53.98981.48962.78700.61.73222.11382.8853圖4：n=20，N=100，prco=0.6，pmu=0.6時(shí)，運(yùn)行結(jié)果圖Rastrigin函數(shù)的當(dāng)前最小值與迭代祓數(shù)的示意10'+.■8：--6-—4-hili'Illi-+-24+t+HH+HHillllllillli-W-H-l---H+-11111111111010和30405060708090100gen由表2和圖4我們可以一看出：當(dāng)增加交叉率時(shí)，遺傳算法求解的最小值得到了進(jìn)一步的改善；當(dāng)變異率增大時(shí)，遺傳算法求解的最小值也得到了很大程度的改善。所以我們適當(dāng)?shù)脑龃蠼徊媛屎妥儺惵蕰r(shí)，可以比較有效的跳出局部最優(yōu)解，更好的逼近最優(yōu)解。(3)prco=0.6，pmut=0.6，n，N變化，運(yùn)行5次平均fmin運(yùn)行結(jié)果如下。表3：prco=0.7，pmut=0.6，n，N變化時(shí)，運(yùn)行結(jié)果Nn1002003004001000.31930.36190.43420.15392000.43740.16130.10950.10753000.54920.09600.10330.08504000.44220.14190.04300.0670圖5：n=400，N=400prco=0.7，pmu=0.6時(shí)，運(yùn)行結(jié)果圖Rastrigin函數(shù)的當(dāng)前最小值與迭代衩數(shù)的示意圖3：2a1.510.50050100150200250300350400gen由表3和圖5我們可以一看出：當(dāng)增加種群個(gè)數(shù)時(shí)，遺傳算法求解的最小值更加逼近全局最小值。并且對(duì)于n>300時(shí)，繼續(xù)增加n對(duì)結(jié)果影響不大，只增加運(yùn)行所需要的時(shí)間；當(dāng)?shù)螖?shù)增大時(shí)，遺傳算法求解的最小值也得到了很大程度的改善。并且由圖4可以看出當(dāng)N>100時(shí)，繼續(xù)增加N對(duì)結(jié)果影響不大，只增加運(yùn)行所需要的時(shí)間。所以我們選擇n=200，N=100，prco=0.7,pmut=0.6，可以更好的逼近最優(yōu)解。4.2運(yùn)用遺傳算法gatool的圖形用戶界面GUI對(duì)Rastrigin函數(shù)優(yōu)化4.2.1gatool使用介紹：⑴Fitnessfunction:欲求最小值的目標(biāo)函數(shù)。輸入輸入適應(yīng)度函數(shù)的形式為@fitnessfun，其中fitnessfun.m是計(jì)算適應(yīng)度函數(shù)的M文件。符號(hào)@產(chǎn)生一個(gè)對(duì)于函數(shù)fitnessfun的函數(shù)句柄。圖形界面如圖6所示。圖6：遺傳算法工具圖形界面（2）Numberofvariable:適應(yīng)度函數(shù)輸入向量的長(zhǎng)度。單擊“Start”按鈕，運(yùn)行遺傳算法，將在“Statusandresult”窗口中顯示出相應(yīng)的運(yùn)行結(jié)果。在“Option”窗格中可以改變遺傳算法的選項(xiàng)。為了查看窗格中所列出的各類選項(xiàng)，可以單擊與之相連的符號(hào)“+”。4.2.2運(yùn)行g(shù)atool對(duì)Rastrigin函數(shù)進(jìn)行優(yōu)化（1）在命令行鍵入gatool，打開遺傳算法工具。（2）在遺傳算法工具相應(yīng)的欄目中，輸入“@rastriginsfcn”：在“Numberofvariable”文本框中，輸入“2”。（3）選擇復(fù)選框中的最佳適應(yīng)度和最佳個(gè)體的圖形選項(xiàng)（4）單擊“Start”按鈕，運(yùn)行遺傳算法。4.2.3結(jié)果分析有說明可知gatool默認(rèn)種群為20，迭代次數(shù)為100。運(yùn)行五次其結(jié)果如下：表4：gatool運(yùn)行結(jié)果運(yùn)行次數(shù)12345fmin0.00310.99500.00200.00640.0027圖7：第一次運(yùn)行每代適應(yīng)度函數(shù)最佳值與平局值的對(duì)數(shù)圖形Beet:0.00315Mean:0.07698510101010101010050Beet:0.00315Mean:0.07698510101010101010050GenerationstoplllnITiA籍illLULZ圖8：第二次運(yùn)行每代適應(yīng)度函數(shù)最佳值與平局值的對(duì)數(shù)圖形Best:0.99503Mean:1.0379102030405060708090100Generation111三EAEIJIlllLIlLZstop圖9：第三次運(yùn)行每代適應(yīng)度函數(shù)最佳值與平局值的對(duì)數(shù)圖形Best:0.0020445Mean:0.033263stoplllr-E'■.=■*111111一LL-圖10：stoplllr-E'■.=■*111111一LL-Best:0.0027253Mean:0.01260710■IO'31111111111stop■102030405060708090100stopij'eneration圖11：第五次運(yùn)行每代適應(yīng)度函數(shù)最佳值與平局值的對(duì)數(shù)圖形102當(dāng)一E>ssitiuilz10'3Best:102當(dāng)一E>ssitiuilz10'3Best:0.0064006Mean:0.02155410110G1疽10'2102030405060708090100ijenerationstop用gatool的運(yùn)行結(jié)果和自編程n=20，N=100，prco=0.4，pmut=0.1時(shí)，運(yùn)彳亍結(jié)果對(duì)比可以看出：在同樣的設(shè)定參數(shù)下gatool的運(yùn)算精度和時(shí)間效率比自編程序要高很多，所以我們自己編寫的遺傳算法還有很大的改進(jìn)空間，需要不斷地改進(jìn)。5附件遺傳算法代碼：gat.mfunction[]=fun(n,N,pcro,pmut)%遺傳算法主函數(shù)%用以實(shí)現(xiàn)求給定函數(shù)fun在給定區(qū)間[low,up]上的極大值%pcro交叉概率,pmut變異概率,N為迭代次數(shù),n為種群low=-5;%區(qū)間下限up=5;%區(qū)間上限T=999;%Boltzmann選擇prec=0.0001;%要求結(jié)果精度length二ceil(log2((up-low)/prec+1));%求得單個(gè)變量編碼長(zhǎng)度pop二encode(length,n);%用解碼函數(shù)求得初始種群，n為種群個(gè)體個(gè)數(shù)fmin=inf;%最優(yōu)解x1min=0;x2min=0;gen=0;%代數(shù)初始化forgen=0:Nfval=zeros(1,n);%初始化函數(shù)值fit=zeros(1,n);%初始化適應(yīng)度pp1=zeros(1,n);%Boltzmann選擇fori=1:n[x1,x2]=decode(pop(i,:),low,up,length);%利用解碼函數(shù)解碼個(gè)體fval(i)=fun(x1,x2);%求個(gè)體的函數(shù)值iffval(i)<fmin%精英保留fmin=fval(i);x1min=x1;

x2min=x2;end%精英保留endplot(gen,fmin,'r+');holdon;pause(1/N*5);xlabel('gen');ylabel('y');title('Rastrigin函數(shù)的當(dāng)前最小值與迭代次數(shù)的示意圖’);fori=1:npp1(i)=1/exp(fval(i)/T);endpp2二sum(pp1);fit二pp1/pp2;%個(gè)體的適應(yīng)度q(1)=fit(1);fori=2:n%累加個(gè)體適應(yīng)度形成賭輪%選擇%交叉%累加個(gè)體適應(yīng)度形成賭輪%選擇%交叉%變異%輸出最小值以及此時(shí)的自變量endpop二select(pop,q,n);pop二crossover(pop,pcro,n,length);pop二mutation(pop,pmut,n,length);%下一代endfmin,xmin=[x1min,x2min]cro.mfunctionpopnew二crossover(pop,pcro,n,length)%交叉函數(shù)%pcro為交叉概率k=1;i=0；while(k<=n)rk=rand();ifrk<pcrob(i+1)=k;i=i+1;endk=k+1;ifi==2pos二ceil(rand()*length);%隨機(jī)產(chǎn)生交叉點(diǎn)fori=pos:lengthc=pop(b(1),i);pop(b(1),i)=pop(b(2),i);%對(duì)x1的交叉點(diǎn)之后的編碼進(jìn)行交換pop(b(2),i)=c;endpos=ceil(rand()*length)+length;%隨機(jī)產(chǎn)生交叉點(diǎn)fori=pos:2*lengthc=pop(b(1),i);pop(b(1),i)=pop(b(2),i);%對(duì)x2的交叉點(diǎn)之后的編碼進(jìn)行交換pop(b(2),i)=c;endi=0;endendpopnew=pop;enco.mfunctionpop二encode(length,n)%編碼函數(shù)pop二randint(n,2*length);%產(chǎn)生初始種群，2變量，故乘2deco.mfunction[x1,x2]=decode(a,l